剑指Offer题解 - Day25

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

力扣题目链接[1]

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

「示例 1：」

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

「限制：」

0 <= 链表长度 <= 1000

思路：

按照题目要求，是将两个有序的链表合并为一个有序的链表。考虑使用双指针的方法进行求解。

首先我们需要创建一个新链表的伪头部节点。然后当两个链表l1和l2 的当前节点都不为空的时候，进行比较节点值的大小，将较小的节点赋值给新链表。当l1或者l2 为空时跳出循环，并将两个链表的剩余部分直接赋值给新链表，因为剩余链表的值也是有序并且比前面的值都更大。

双指针

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    let link = new ListNode(null); // 新链表的伪头部节点
    let cur = link; // 指向新链表的当前节点
    while(l1 && l2) {
        if (l1.val <= l2.val) { // 将较小节点赋值给当前节点的next
            cur.next = l1;
            l1 = l1.next; // l1向前走一步
        } else {
            cur.next = l2;
            l2 = l2.next; // l2向前走一步
        }
        cur = cur.next; // 当前节点向前走一步
    }
    cur.next = l1 ?? l2; // 将剩余链表赋值给当前节点的next
    return link.next; // 返回伪头部节点的next
};

• 「时间复杂度 O(m + n)」。
• 「空间复杂度 O(1)」。

分析：

创建一个新链表的伪头部节点，用来承载当前节点的指针指向。

因为我们不知道l1和l2 链表的长度，因为循环条件要确保两个链表的当前值都不为空。循环里主要是将较小节点赋值给当前节点的next ，同时新旧链表都向前进一步，进入一下次循环。

循环结束后，势必有一个链表为空。那么判断不为空的链表，将剩余节点赋值给当前节点的next 。就算两个链表同时为空，next的指向也是null 。

最后不能直接返回link，因为存在一个伪头部节点，需要返回下一个节点，也就是link.next 。

总结

处理链表问题，优先考虑使用双指针进行解决。

本题的复杂度方面，由于需要需要遍历两个链表并合并，因此时间复杂度是O(m + n) ；维护了常数大小的变量，因此时间复杂度是O(1)。

参考资料

[1]力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vq98s/