leetcode 21. 合并两个有序链表

leetcode 21. 合并两个有序链表合并两个有序链表

题目

给定两个有序链表 list1 和 list2，将它们合并成一个有序链表。合并后的链表应由两个输入链表的节点组成。

返回合并后链表的头。你不能修改列表。请输出结果为新链表的头部。

解题思路

为了合并两个有序链表，我们使用一个哑节点 preHead 来存储新链表的头，以及一个 tail 指针来表示新链表的尾部。然后我们通过比较 list1 和 list2 当前节点的值，选择较小的节点追加到新链表的尾部，直到其中一个链表为空。最后，我们将非空链表的剩余部分连接到新链表的尾部。

代码

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode preHead = new ListNode(-1);
        ListNode tail = preHead;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next; // Move the tail to the new end
        }

        // Connect the remaining part of list1 or list2 to the merged list
        if (list1 != null) {
            tail.next = list1;
        } else {
            tail.next = list2;
        }

        return preHead.next;
    }
}