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

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

题目描述

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

解法:迭代

设置一个“哨兵节点”叫 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)。代码如下:

// ac地址:https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
// 原文地址:https://xxoo521.com/2020-01-12-merge-two-sorted-lists/

/**
 * @param {ListNode} pHead1
 * @param {ListNode} pHead2
 * @return {ListNode}
 */
var mergeTwoLists = function(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

×