题目

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

示例 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 均按 非递减顺序 排列

解法

迭代法

思路：固定将链表2的元素逐个插入到链表1中

遍历链表2的元素，在链表1中找第一个比该元素大的，将链表元素插入到链表1这个位置之前疾苦

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 固定连接顺序，链表2一个一个插入到链表1
        // 在链表1中找第一个比2当前元素大的，将链表2这个元素插入到这个元素之前
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        ListNode node1 = null, preNode1 = list1, node2 = list2;
        while (node2 != null && preNode1 != null) {
            if (preNode1.val >= node2.val) {
                if (node1 == null) {
                    ListNode temp = node2.next;
                    node1 = node2;
                    node1.next = preNode1;
                    node2 = temp;
                    // 头插进来，作为起始点
                    list1 = node1; 
                } else {
                    node1.next = node2;
                    node2 = node2.next;
                    node1.next.next = preNode1;
                    node1 = node1.next;
                }
            } else {
                node1 = preNode1;
                preNode1 = preNode1.next;
            }
        }
        if (preNode1 == null) {
            // 链表1先遍历完了，说明链表2有剩下的元素，比链表1最大的要大，直接连在后面
            node1.next = node2;
        }
        return list1;
    }
}

小结

本题难度较低，如果同时将两个对象作为思考的主体如果比较复杂的话，不妨试一下将职责分散出去，比如本题固定链表1是被插入的目标，链表2是需要被逐个插入链表2的。