剑指offer - 合并两个排序的链表

设置一个“哨兵节点”叫 preHead，这会让代码写起来非常“清爽”。整体流程如下：

• 如果 pHead1 和 pHead2，均没遍历完：
  • 如果 pHead1.val <= pHead2.val，那么当前 node 的 next 指向 pHead1。并且移动 pHead1 指针。
  • 否则，当前 node 的 next 指向 pHead2，移动 pHead2 指针。
  • 移动 node 指针
  • 继续循环
• 否则，结束循环：
  • 如果 pHead1 未遍历完，node 的 next 指向 pHead1
  • 如果 pHead2 未遍历玩，node 的 next 指向 pHead2

时间复杂度是 O(N)，空间复杂度是 O(1)。代码如下：

// 原文地址：https://xxoo521.com/2020-01-12-merge-two-sorted-lists/
// ac地址：https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337/

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function Merge(pHead1, pHead2) {
    if (!pHead1) {
        return pHead2;
    } else if (!pHead2) {
        return pHead1;
    }

    let preHead = new ListNode(-1);
    let node = preHead;

    while (pHead1 && pHead2) {
        if (pHead1.val <= pHead2.val) {
            node.next = pHead1;
            pHead1 = pHead1.next;
        } else {
            node.next = pHead2;
            pHead2 = pHead2.next;
        }
        node = node.next;
    }

    if (pHead1) {
        node.next = pHead1;
    } else if (pHead2) {
        node.next = pHead2;
    }

    return preHead.next;
}

🔍 关注公众号“心谭博客” / 👉 前往 xxoo521.com

查看更多前端与算法的系列文章，获得更好阅读体验