【Day 87 】2024-07-03 - 23.合并 K 个排序链表

[azl397985856]

23.合并 K 个排序链表

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/merge-k-sorted-lists/

前置知识

• 堆
• 链表
• 分而治之

  题目描述

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

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

 

示例 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

[lxy1108]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        prehead = ListNode()
        pointer = prehead
        while True:
            minnode = None
            minidx = -1
            # print(lists)
            for i,head in enumerate(lists):
                if head is not None:
                    if minnode is None or head.val<minnode.val:
                        minnode = head
                        minidx = i
            if minnode is None:
                break
            pointer.next = minnode
            lists[minidx] = minnode.next
            pointer = pointer.next

        return prehead.next

[CathyShang]

ListNode.__lt__ = lambda a, b: a.val < b.val
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        cur = dummy = ListNode()
        h = [head for head in lists if head] # 初始化把k个链表的头节点放入将成为堆的list
        heapify(h) # 堆化：成为堆
        while h: # 当堆不为空
            node = heappop(h) 
            if node.next: # 不是尾节点
                heappush(h, node.next) 
            cur.next = node # 合并
            cur = cur.next # 指向下一节点
        return dummy.next

[Dtjk]

class Solution { public: struct cmp { bool operator()(ListNode a, ListNode b) { return a->val > b->val; // 小根堆 } };

ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, cmp> q;

    for (ListNode *list : lists) 
        if (list != nullptr)
            q.push(list);

    ListNode *dummy = new ListNode(0), *tail = dummy;
    while (!q.empty()) {
        ListNode *cur = q.top(); q.pop();
        tail->next = cur;
        tail = tail->next;
        if (cur->next != nullptr) //if (cur->next)
            q.push(cur->next);
    }

    return dummy->next;
}

};