Heading

23.合并 K 个升序链表 (opens new window)

Tags: algorithms airbnb amazon facebook google linkedin microsoft twitter uber linked-list divide-and-conquer heap

Langs: c cpp csharp golang java javascript kotlin php python python3 ruby rust scala swift typescript

• algorithms
• Hard (53.39%)
• Likes: 964
• Dislikes: -
• Total Accepted: 180.9K
• Total Submissions: 338.5K
• Testcase Example: '[[1,4,5],[1,3,4],[2,6]]'

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

 

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

/*
 * @lc app=leetcode.cn id=23 lang=javascript
 *
 * [23] 合并 K 个升序链表
 * 递归
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
  if (lists.length === 0) {
    return null
  }

  return lists.reduce((acc, item) => {
    const dummy = new ListNode()
    let p = dummy
    let l1 = acc
    let l2 = item
    while (l1 && l2) {
      if (l1.val <= l2.val) {
        p.next = l1
        l1 = l1.next
      } else {
        p.next = l2
        l2 = l2.next
      }
      p = p.next
    }
    p.next = l1 ? l1 : l2
    return dummy.next
  })
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=23 lang=javascript
 *
 * [23] 合并K个升序链表
 * 非递归
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
    if (lists.length < 1) return null;
    if (lists.length === 1) return lists[0];

    const hair = new ListNode(0, lists.shift());
    let p = hair, q, r;
    while (lists.length) {
        q = lists.shift();
        while (q) {
            if (p.next === null) {
                p.next = q;
                break;
            } else if (q.val <= p.next.val) {
                r = q.next;
                q.next = p.next;
                p.next = q;
                q = r;
            } else {
                p = p.next;
            }
        }
        p = hair;
    }
    return hair.next
};
// @lc code=end

/*
 * @lc app=leetcode.cn id=23 lang=javascript
 *
 * [23] 合并 K 个升序链表
 * 非递归
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
    if (lists.length === 0) {
      return null
    }
  
    return lists.reduce((acc, item) => {
      const dummy = new ListNode()
      let p = dummy
      let l1 = acc
      let l2 = item
      while (l1 && l2) {
        if (l1.val <= l2.val) {
          p.next = l1
          l1 = l1.next
        } else {
          p.next = l2
          l2 = l2.next
        }
        p = p.next
      }
      p.next = l1 ? l1 : l2
      return dummy.next
    })
  }
  // @lc code=end