一道编程题——合并K个有序链表

题目描述与分析

合并 k 个已排序的链表并将其作为一个已排序的链表返回。这与之前遇到的合并两个有序链表为同类型的题目。

这里提供两种方法：

1. 很显然，合并多个有序链表是合并两个有序链表的拓展情况，因此，可以用合并两个链表的方法，依次两两合并，使得链表最终为1。合并过程类似归并排序的归并过程。
2. 设置一个大小为K的最小堆，堆中的节点为K个链表的头节点，每次取出最小值（堆顶），然后将这个最小值的下一个节点加入链表（如果有的话），直到堆为空。

一般数据结构堆的实现方式采用优先队列，队列中的元素有一个优先值，每次pop元素的时候，会取出优先值最小的元素。加入新元素的时候也会重新排序。

优先队列中元素排列顺序采用堆的层次遍历，由于堆中的父节点均小于子节点，这在优先队列中的表现形式为第一个元素（堆顶）小于第二个元素（左子）和第三个元素（右子）。第K个元素小于第2K和第2K+1个元素。（这里指的是第几个元素，由于很多编程语言中队列首元素从0开始，左右孩子节点计算起来略有不同）

代码实现

python实现

归并

# 迭代，两两合并
class Solution:
    def mergeKLists(self , lists ):
        # write code here
        if not lists:return None
        # 每次取队首两个链表合并，合并之后加入到队尾
        while(len(lists)>1):
            first_link = lists.pop(0)
            second_link = lists.pop(0)
            merged_link = self.merge(first_link, second_link)
            # 返回值不是None则加入到队尾
            if merged_link:
                lists.append(merged_link)
        if not lists:return None
        return lists[0]
    
    # 两两链表合并
    def merge(self, link1, link2):
        if (not link1) and (not link2):
            return None
        root = ListNode(0)
        tmp = root
        while(link1 and link2):
            if link1.val <=link2.val:
                tmp.next = link1
                link1 = link1.next
            else:
                tmp.next = link2
                link2 = link2.next
            tmp = tmp.next
        tmp.next = link1 if link1 else link2
        return root.next

有序数组

class Solution:
    def mergeKLists(self , lists ):
        # write code here
        queue = [link for link in lists if link]
        if not queue:
            return None
        # 这里用有序数组替代了最小堆
        queue.sort(key=lambda x:x.val)
        # 建立一个虚拟首节点
        root = ListNode(0)
        tmp = root
        while queue:
            # 取最小值，加入到有序链表
            tmp.next = queue.pop(0)
            tmp = tmp.next
            if tmp.next:
                queue.append(tmp.next)
                queue.sort(key=lambda x:x.val)
        return root.next

C++实现

归并

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.size() == 0) return nullptr;
        ListNode* root = lists[0];
        for(int i=1; i < lists.size();i++){
            root = merge(root, lists[i]);
        }
        return root;
    }
    // 合并两个有序链表，返回新链表的头节点 
    ListNode* merge(ListNode* l1, ListNode* l2){
        if(l1==NULL)return l2;
        if(l2==NULL)return l1;
        ListNode* root = new ListNode(0);
        ListNode* tmp = root;
        while(l1!=NULL && l2!=NULL){
            if(l1 -> val <= l2 -> val){
                tmp -> next = l1;
                l1 = l1 -> next;
            }
            else{
                tmp -> next = l2;
                l2 = l2 -> next;
            }
            tmp = tmp->next;
        }
        if(l1!=NULL) tmp -> next = l1;
        else tmp -> next = l2;
        return root -> next;
    }
};

堆

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode L(0);
        ListNode *p = &L;
        vector<ListNode *> v;
         
        int n = lists.size();
        for(int i=0;i<n;i++)
            if(lists[i] != NULL)
                v.push_back(lists[i]);
        // 建堆
        make_heap(v.begin(),v.end(),cmp);
        while(v.size())
        {
            // 取堆中最小元素
            p -> next = v.front();
            pop_heap(v.begin(),v.end(),cmp);
            v.pop_back();
            p = p -> next;
            if(p -> next)
            {
                v.push_back(p -> next);
                push_heap(v.begin(),v.end(),cmp);
            }
        }
        return L.next;
    }
    static bool cmp(ListNode *L1,ListNode *L2)
    {
        return L1 -> val > L2 -> val;
    }
};