【Day 87 】2023-01-26 - 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

[Ryanbaiyansong]

···

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]:

多路归并

    dummy = ListNode(0)
    cur = dummy 
    minHeap = [] # pair(value, index)
    for i, h in enumerate(lists):
        if h:
            heappush(minHeap, (lists[i].val, i))

    while minHeap:
        v, idx = heappop(minHeap)
        node = ListNode(v)
        cur.next = node 
        cur = cur.next 
        if lists[idx].next:
            lists[idx] = lists[idx].next
            heappush(minHeap, (lists[idx].val, idx))

    return dummy.next

···

[snmyj]

class Solution {
public:
    ListNode* twoMerge(ListNode* a,ListNode* b){
        if(a||!b) return a?a:b;
        ListNode h,*tail=&h,*pa=a,*pb=b;

        while(pa&&pb){
            if(pa->val<pb->val) {
                tail->next=pa;
                pa=pa->next;
            }
            else {
                tail->next=pb;
                pb=pb->next;
            }
            tail=tail->next;
        }
         tail->next=pa?pa:pb;
         return h.next; 
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* ans;
        for(int i=0;i<lists.size();i++) ans=twoMerge(ans,lists[i+1]);
        return ans;

    }
};

[klspta]

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> q = new PriorityQueue<>((a, b) -> a.val - b.val);
        ListNode res = new ListNode();
        ListNode cur = res;

        for(ListNode listNode : lists){
            if(listNode != null){
                q.offer(listNode);
            }
        }

        while(!q.isEmpty()){
            ListNode tmp = q.poll();
            cur.next = tmp;
            cur = cur.next;
            if(tmp.next != null){
                q.offer(tmp.next);
            }
        }

        return res.next;
    }
}

[FlipN9]

/**
    k 个链表 长度为 N

    Approach 1: MinHeap      7ms 48%

    TC: O(nk * logk)        pq 插入删除 O(log k), nk 个点
    SC: O(k) for pq         pq 中元素的个数不会超过 k 个
*/
class Solution1 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // 优先级队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
            lists.length, (a, b)->(Integer.compare(a.val, b.val)));
        // 将 k 个链表的头结点加入最小堆
        for (ListNode head : lists) {
            if (head != null) 
                pq.add(head);
        }
        while (!pq.isEmpty()) {
            // 获取最小节点，接到结果链表中
            ListNode node = pq.poll();
            p.next = node;
            // 将node.next重新加入pq
            if (node.next != null) {
                pq.add(node.next);
            }
            // p 指针不断前进
            p = p.next;
        }
        return dummy.next;
    }
}

/**
    Approach 2: Divide & Conquer    1ms 100%
    TC: O(nk * logk)    log k 层, 每一层 kn 个节点参与合并
    SC: O(log k)        log k 层 栈空间
*/
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null; 
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        int mid = start + (end - start) / 2;
        ListNode left = merge(lists, start, mid);
        ListNode right = merge(lists, mid + 1, end);
        return merge2Lists(left, right);
    }

    private ListNode merge2Lists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 == null ? l2 : l1;
        return dummy.next;
    }
}

[bookyue]

code

1. dive and conquer
2. minHeap

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        return mergeKLists(lists, 0, lists.length - 1);
    }

    private ListNode mergeKLists(ListNode[] lists, int begin, int end) {
        if (begin >= end) return lists[begin];

        int mid = (begin + end) >>> 1;
        var left = mergeKLists(lists, begin, mid);
        var right = mergeKLists(lists, mid + 1, end);
        return mergeList(left, right);
    }

    private ListNode mergeList(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(-1);
        var cur = dummy;

        while (left != null && right != null) {
            if (right.val < left.val) {
                cur.next = right;
                right = right.next;
            } else {
                cur.next = left;
                left = left.next;
            }
            cur = cur.next;
        }

        cur.next = left != null ? left : right;

        return dummy.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        var pq = new PriorityQueue<ListNode>(Comparator.comparingInt(a -> a.val));

        ListNode dummy = new ListNode(-1);
        for (var head : lists) pq.offer(head);

        var cur = dummy;
        while (!pq.isEmpty()) {
            cur.next = pq.poll();
            cur = cur.next;
            if (cur.next != null) pq.offer(cur.next);
        }

        return dummy.next;
    }

[mayloveless]

思路

1. 小顶堆

代码

var mergeKLists = function(lists) {
    if (lists == null || lists.length == 0) {
        return null
    }
    let k = lists.length
    let minQ = new MinPriorityQueue({priority: node => node.val })
    for (let i = 0; i < k; ++i) {
        if (lists[i] != null) {
            minQ.enqueue(lists[i])
        }
    }
    let head = new ListNode()
    let tail = head
    while (!minQ.isEmpty()) {
        let curNode = minQ.dequeue().element
        tail.next = curNode
        tail = tail.next

        if (curNode.next != null) {
            minQ.enqueue(curNode.next)
        }
    }
    return head.next
};

复杂度

时间O（kn*logk） 插入一次logk，kn次数 空间O（k）

[Abby-xu]

import heapq class Solution: #three lists def mergeKLists(self, lists: List[ListNode]) -> ListNode: ListNode.lt = lambda self, other: self.val < other.val h = [] head = tail = ListNode(0) for i in lists: if i: heapq.heappush(h, i) while h: node = heapq.heappop(h) tail.next = node tail = tail.next if node.next: heapq.heappush(h, node.next) return head.next ''' considering k lists and n being the maximum list size, there are total number of n.k nodes at each point of time we are only storing maximum of k nodes in the queue. After storing k nodes in the queue, now to insert a new node in the queue, time complexity is O( log(k) ) --> comes from time complexity of inserting node in priority queue. And since we are doing this for total of n.k nodes, it gives total time complexity = n.k.log(k) Time complexity: O( n.k.log(k) ) -> O(nlogK) Space complexity: O(k), only k nodes are stored at a time '''

[RestlessBreeze]

code

ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
    if ((!a) || (!b)) return a ? a : b;
    ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
    while (aPtr && bPtr) {
        if (aPtr->val < bPtr->val) {
            tail->next = aPtr; aPtr = aPtr->next;
        } else {
            tail->next = bPtr; bPtr = bPtr->next;
        }
        tail = tail->next;
    }
    tail->next = (aPtr ? aPtr : bPtr);
    return head.next;
}

[Jetery]

class Solution {
public:
    struct cmp { //结构体 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;
    }
};

[Alexno1no2]

# 利用堆的数据结构

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        import heapq #调用堆
        minHeap = []
        for listi in lists: 
            while listi:
                heapq.heappush(minHeap, listi.val) #把listi中的数据逐个加到堆中
                listi = listi.next
        head = ListNode(0) #构造虚节点
        p = head
        while minHeap:
            p.next = ListNode(heapq.heappop(minHeap)) #依次弹出最小堆的数据
            p = p.next
        return head.next 

[tiandao043]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };

    priority_queue <Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for(auto node:lists)
        if(node)q.push({node->val,node});
        ListNode head,*tail=&head;
        while(!q.empty()){
            auto f=q.top();q.pop();
            tail->next=f.ptr;
            tail=tail->next;
            if(f.ptr->next)q.push({f.ptr->next->val,f.ptr->next});
        }
        return head.next;
    }
};

归并

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists,0,lists.size()-1);       
    }
     ListNode* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if((!a) || (!b)) return a?a:b;
        ListNode head,*tail=&head,*aPtr=a,*bPtr=b;
        while(aPtr&&bPtr){
            if(aPtr->val<bPtr->val){
                tail->next=aPtr;aPtr=aPtr->next;
            }
            else{
                tail->next=bPtr;bPtr=bPtr->next;
            }
            tail=tail->next;
        }
        tail->next=(aPtr?aPtr:bPtr);
        return head.next;
    }
};

[Elsa-zhang]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def merge2list(self, l1, l2):
        node1, node2 = l1, l2
        ans = ListNode(-1)
        cur = ans
        while node1 and node2:
            if node1.val<=node2.val:
                cur.next = node1
                node1 = node1.next
            else:
                cur.next = node2
                node2 = node2.next
            cur = cur.next

        cur.next = node1 if node1!=None else node2
        return ans.next

    def merge(self, lists, l, r):
        if l == r:
            return lists[l]
        mid = (l+r)//2
        l1 = self.merge(lists, l, mid)
        l2 = self.merge(lists, mid+1, r)
        return self.merge2list(l1, l2)

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        n = len(lists)
        l, r = 0, n-1
        return self.merge(lists, l, r)

[whoam-challenge]

class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: import heapq dummy = ListNode(0) p = dummy head = [] for i in range(len(lists)): if lists[i] : heapq.heappush(head, (lists[i].val, i)) lists[i] = lists[i].next while head: val, idx = heapq.heappop(head) p.next = ListNode(val) p = p.next if lists[idx]: heapq.heappush(head, (lists[idx].val, idx)) lists[idx] = lists[idx].next return dummy.next