23.合并K个升序链表

链接：23.合并K个升序链表
难度：Hard
标签：链表、分治、堆（优先队列）、归并排序
简介：给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

题解 1 - javascript

• 编辑时间：2020-04-26
• 执行用时：384ms
• 内存消耗：44.78MB
• 编程语言：javascript
• 解法介绍：归并排序。

var mergeKLists = function (lists) {
    if (lists.length === 0) return null;
    if (lists.length === 1) return lists[0];
    let resNode;
    for (const node of lists) {
        if (node === null) continue;
        if (resNode === undefined) resNode = node;
        else resNode = add(resNode, node);
    }
    return resNode===undefined?null:resNode;
};
function add(node1, node2) {
    let tempNode1 = node1;
    let tempNode2 = node2;
    let resNode;
    let tempNode3;
    while (tempNode1 !== null || tempNode2 !== null) {
        let minNode;
        if (tempNode1 === null) {
            minNode = tempNode2;
            tempNode2 = tempNode2.next;
        } else if (tempNode2 === null) {
            minNode = tempNode1;
            tempNode1 = tempNode1.next;
        } else if (tempNode1.val < tempNode2.val) {
            minNode = tempNode1;
            tempNode1 = tempNode1.next;
        } else {
            minNode = tempNode2;
            tempNode2 = tempNode2.next;
        }
        if (resNode === undefined) {
            tempNode3 = resNode = minNode;
        } else {
            tempNode3.next = minNode;
            tempNode3 = tempNode3.next;
        }
    }
    return resNode;
}

题解 2 - typescript

• 编辑时间：2021-05-13
• 执行用时：220ms
• 内存消耗：48.3MB
• 编程语言：typescript
• 解法介绍：归并排序。

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  lists = lists.filter(list => list !== null);
  const len = lists.length;
  if (len === 0) return null;
  const merge = (start: number, end: number): ListNode | null => {
    console.log(start, end);
    if (start > end) return null;
    if (start === end) return lists[start];
    const mid = (start + end) >> 1;
    const list1 = merge(start, mid);
    const list2 = merge(mid + 1, end);
    if (list1 === null) return list2;
    if (list2 === null) return list1;
    const first = new ListNode(0);
    let temp = first;
    let p1: ListNode | null = list1;
    let p2: ListNode | null = list2;
    while (p1 && p2) {
      if (p1.val <= p2.val) {
        temp.next = p1;
        temp = temp.next;
        p1 = p1.next;
      } else {
        temp.next = p2;
        temp = temp.next;
        p2 = p2.next;
      }
    }
    if (p1) temp.next = p1;
    if (p2) temp.next = p2;
    return first.next;
  };
  return merge(0, len - 1);
}}

题解 3 - cpp

• 编辑时间：2023-08-12
• 执行用时：16ms
• 内存消耗：12.67MB
• 编程语言：cpp
• 解法介绍：堆存储每个头节点。

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *head = new ListNode(), *p = head;
        auto cmp = [&](ListNode* n1, ListNode* n2) {
            return n2->val < n1->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q(cmp);
        for (auto &node : lists) {
            if (node) q.push(node);
        }
        while (q.size()) {
            auto node = q.top();
            q.pop();
            p->next = node;
            p = p->next;
            if (node->next) q.push(node->next);
        }
        return head->next;
    }
};

题解 4 - python

• 编辑时间：2023-08-12
• 执行用时：136ms
• 内存消耗：19.82MB
• 编程语言：python
• 解法介绍：同上。

ListNode.__lt__ = lambda a, b: a.val < b.val
    class Solution:
        def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
            head = ListNode()
            p = head
            q = []
            for node in lists:
                if node:
                    print(node)
                    heappush(q, node)
    
            while len(q):
                node = heappop(q)
                p.next = node
                p = p.next
                if node.next:
                    heappush(q, node.next)
            return head.next

题解 5 - rust

• 编辑时间：2023-08-12
• 执行用时：4ms
• 内存消耗：3.25MB
• 编程语言：rust
• 解法介绍：同上。

use std::cmp::{Ord, Ordering, PartialOrd};
impl Ord for ListNode {
    fn cmp(&self, other: &Self) -> Ordering {
        other.val.cmp(&self.val)
    }
}
impl PartialOrd for ListNode {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        other.val.partial_cmp(&self.val)
    }
}
impl Solution {
    pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        let mut head = Some(Box::new(ListNode::new(0)));
        let mut p = head.as_mut().unwrap();
        let mut q = std::collections::BinaryHeap::new();
        for node in lists {
            if let Some(node) = node {
                q.push(node);
            }
        }
        while let Some(mut node) = q.pop() {
            let next = node.next.take();
            p.next = Some(node);
            p = p.next.as_mut().unwrap();
            if let Some(next) = next {
                q.push(next);
            }
        }
        head.unwrap().next
    }
}