题目

剑指 Offer 25. 合并两个排序的链表

思路1

• 其实就是归并排序中将两个数组合并成一个有序数组
• 因为两个链表的元素已经是递增了（必要条件），所以我们可以遍历两个链表，判断两个节点的大小关系，然后交替前进，合并到一个新的链表中
• 因为需要返回一个合并后的新链表，同时我们也无法判断l1、l2两个链表的值大小，因此我们可以创建一个虚拟头节点dummy，相当于用来标识这个链表，这样最后的结果就是虚拟头节点的下一个节点dummy.next了

代码

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建一个虚拟头节点
        ListNode dummy = new ListNode(-1);
        ListNode temp = dummy;

        // 就是归并排序里的将两个数组合并成一个有序数组
        // 要保证这两个链表都是有效的，及不为空
        // 如何判断大小进行合并，注意这里要重新创建节点
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                temp.next = new ListNode(l1.val);
                temp = temp.next;
                l1 = l1.next;
            } else {
                temp.next = new ListNode(l2.val);
                temp = temp.next;
                l2 = l2.next;
            }
        }
        // 判断两个链表是否都遍历完
        while (l1 != null) {
            temp.next = new ListNode(l1.val);
            temp = temp.next;
            l1 = l1.next;
        }
        while (l2 != null) {
            temp.next = new ListNode(l2.val);
            temp = temp.next;
            l2 = l2.next;
        }

        // 答案就是虚拟头节点的next下一个节点
        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：\(O(M+N)\)，M、N分别为l1、l2两个链表的长度
• 空间复杂度：\(O(1)\)