21. 合并两个有序链表：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。_将两个升序链表合并为一个新的升序链表并返回

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

思路

使用迭代的思想解决：

1. 新建一个节点prehead，初始值为-1；再新建一个节点pre执行prehead
2. 在对链表的操作中，链表的头节点head往往会发生移动，这样我们将难以找到最终链表的头指针，故我们需要提前设置一个哨兵节点 prehead，这可以在最后让我们比较容易地返回最终的链表
3. 遍历时，需要判断两个链表谁大谁小，小的存放到pre中，并将小的向后移动一位
4. 遍历结束后，l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
5. 返回值是prehead.next后面的内容

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //初始化一个节点值为-1的空节点，设置为头指针
        ListNode prehead = new ListNode(-1);
        //pre和prehead指向同一个结点，改变pre指向的链表结点时，prehead也会改变
        ListNode pre = prehead;
        //遍历需要合并的两个指针
        while(list1 != null && list2 != null){
            //比较list1和list2的值的大小
            if(list1.val < list2.val){
                //list1小于list2，将list1的值添加到指针后面
                pre.next = list1;
                //将list1后移一位
                list1 = list1.next;
            }else{
                pre.next = list2;
                list2 = list2.next;
            }
            //不管将哪一个元素接在了后面，都需要把pre向后移一位
            //后移一位后存放新的结点内容
            pre = pre.next;
        }
        // 合并后 list1 和 list2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        pre.next = list1 == null ? list2 : list1;
        return prehead.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

代码说明

注释。。。