聖地亞歌

Leetcode P0023"Merge k Sorted Lists" 题解

2020/08/18 Leetcode

博文中会简要介绍Leetcode P0023题目分析及解题思路。

“Merge k Sorted Lists”是一道原型题，使用优先级队列（堆）来解决。p0021是其简化版。

Given an array of linked-lists lists, each linked list is sorted in ascending order.

Merge all the linked-lists into one sort linked-list and return it.

这道题的思路比较直接，时间复杂度是O(nlogk)。通过使用堆算法和数据结构，不断获取当前k个链表中的具有最小值的结点，然后将其连在新链表末尾，并且将其指针向后移动一格，将指针新指向的结点加入堆中，此时根据堆的特性，堆会进行上移或者下移来保证堆顶（也就是队列头）始终是当前堆中的具有最小值的结点。

下一个循环继续拿出堆顶元素，重复上述操作，直到堆为空。

以下是Java的题解代码实现。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0)
            return null;
        
        Queue<ListNode> pQueue = new PriorityQueue<>(new Comparator<>() {
            @Override
            public int compare(ListNode l1, ListNode l2) {
                return l1.val-l2.val;
            }
        });
        
        ListNode dummy = new ListNode(0, null);
        ListNode tail = dummy;
        
        for (ListNode node: lists) {
            if (node != null)
                pQueue.offer(node);
        }
        
        while (!pQueue.isEmpty()) {
            ListNode itr = pQueue.poll();
            if (itr.next != null)
                pQueue.offer(itr.next);
            
            tail.next = itr;
            tail = tail.next;
        }
        
        return dummy.next;
    }
}

关于C++中的优先级队列写法，主要有如下三种：

首先，priority_queue的模板是:
priority_queue<Type, Container, Typename> pq([lambda], [container]);

1. 写仿函数传入Typename:
    struct Comparator {
        bool operator() (x, y) {...}
    };

2. 直接在对应Type的类中重载operator<。必须写成友元函数或者常量成员函数

3. 写成lambda表达式:
    auto comparator = [](x, y) -> bool {...};
    在Typename传入decltype(comparator)，并在[lambda]参数上传入comparator，即传入写好的lambda

以下是C++的题解代码实现。

/**
 * 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 NodeComparator {
        bool operator() (ListNode *l1, ListNode *l2) {
            return l1->val > l2->val;
        }
    };
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0)
            return NULL;
        
        // Lambda
        // auto node_comp = [](ListNode *l1, ListNode *l2) -> bool {
        //     return l1->val > l2->val;
        // };
        
        // priority_queue<ListNode*, vector<ListNode*>, decltype(node_comp)> heap(node_comp);
        
        // 仿函数
        priority_queue<ListNode*, vector<ListNode*>, NodeComparator> heap;
        
        ListNode *dummy = new ListNode(0);
        ListNode *tail = dummy;
        for (ListNode *node: lists) {
            if (node != NULL)
                heap.push(node);
        }
        
        while (!heap.empty()) {
            ListNode *temp = heap.top();
            heap.pop();
            if (temp->next != NULL) 
                heap.push(temp->next);
            
            tail->next = temp;
            tail = tail->next;
        }
        
        return dummy->next;
    }
};

Search

    Table of Contents