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

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

题目描述:输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

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

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

题目描述

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

解法 1: 迭代法

设置一个“哨兵节点”叫 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;
}
#

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×