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 listif (list1 != null) {tail.next = list1;} else {tail.next = list2;}return preHead.next;}
}