Posted 2024-08-20Algorithm / C++ / job6 minutes read (About 832 words)0 visits

<Data Structures/Algorithms> leetcode hot100 - 23. Merge k Sorted Lists

[LeetCode Hot 100] 23. Merge k Sorted Lists

Merging two linked lists is straightforward: use two pointers pointing to the two lists and move the pointer with the smaller value each time.

However, here we have k lists. If we use k pointers and move the smallest one each time, we would need to traverse all k pointers to find the minimum each time, which is too inefficient.

Finding the minimum among k elements is a perfect scenario for using a heap. About heap knowledge, see here.

We use a min-heap here because we want the smallest element each time. The heap top is a pointer to a current node in one of the lists. After taking the heap top, we move that pointer to the next node and put it back into the heap. This is conveniently done by replacing the heap top and adjusting down.

Below is the complete code. I took a shortcut by using sorting to build the heap.

/**
 * 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:
    void adjustDown(vector<ListNode*>& heap){
        int parent = 0;
        while(2 * parent + 1 < heap.size()){
            int lchild = 2 * parent + 1;
            int minChild = lchild;
            if(lchild + 1 < heap.size()){
                int rchild = lchild + 1;
                minChild = heap[lchild]->val < heap[rchild]->val ? lchild : rchild;
            }
            if(heap[parent]->val < heap[minChild]->val){
                return;
            }
            swap(heap[parent], heap[minChild]);
            parent = minChild;
        }
        return;
    }
    void headPop(vector<ListNode*>& heap){
        swap(heap[0], heap[heap.size() - 1]);
        heap.pop_back();
        adjustDown(heap);
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*> heap;
        for(auto& head : lists){
            if(head) heap.push_back(head);
        }
        // Use sorting to simulate heap construction
        sort(heap.begin(), heap.end(), [](ListNode* a, ListNode* b){return a->val < b->val;});
        ListNode dummy(0);
        ListNode* cur = &dummy;
        while(heap.size() > 0){
            cur->next = new ListNode(heap[0]->val);
            cur = cur->next;
            if(heap[0]->next == nullptr){
                headPop(heap);
            } else {
                heap[0] = heap[0]->next;
                adjustDown(heap);
            }
            cout<<heap.size()<<endl;
        }
        return dummy.next;
    }
};

中文原文

[LeetCode hot 100] 23. 合并k个升序链表

题目链接

如果是合并两个链表那没得说，两个指针分别指向两个链表，每次把小的那个后移。

但是这里是k个，如果用k个指针，每次移动最小的，那么每次都需要遍历一遍找到最小的那个，时间复杂度太高了。

从k个里面找最小，这个情景很适合使用【堆】这种结构。关于堆的知识点传送门

这里使用小根堆，因为每次要获得最小的，那么小根堆取堆顶就能很轻松地完成这个工作。堆顶是一个指针，指向某个链表的遍历位置，当取了堆顶之后，需要将遍历指针向后移动一位，并且重新加入到堆中，这里就是把堆顶替换掉，然后向下调整，最为方便。

下面是完整代码，其中我偷了点懒，建堆就直接用排序代替了。

/**
 * 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:
    void adjustDown(vector<ListNode*>& heap){
        int parent = 0;
        while(2 * parent + 1 < heap.size()){
            int lchild = 2 * parent + 1;
            int minChild = lchild;
            if(lchild + 1 < heap.size()){
                int rchild = lchild + 1;
                minChild = heap[lchild]->val < heap[rchild]->val ? lchild : rchild;
            }
            if(heap[parent]->val < heap[minChild]->val){
                return;
            }
            swap(heap[parent], heap[minChild]);
            parent = minChild;
        }
        return;
    }
    void headPop(vector<ListNode*>& heap){
        swap(heap[0], heap[heap.size() - 1]);
        heap.pop_back();
        adjustDown(heap);
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*> heap;
        for(auto& head : lists){
            if(head) heap.push_back(head);
        }
        //这里用排序实现了建堆，效果是一样的
        sort(heap.begin(), heap.end(), [](ListNode* a, ListNode* b){return a->val < b->val;});
        ListNode dummy(0);
        ListNode* cur = &dummy;
        while(heap.size() > 0){
            cur->next = new ListNode(heap[0]->val);
            cur = cur->next;
            if(heap[0]->next == nullptr){
                headPop(heap);
            } else {
                heap[0] = heap[0]->next;
                adjustDown(heap);
            }
            cout<<heap.size()<<endl;
        }
        return dummy.next;
    }
};