leecode刷题（27）-- 合并k个排序链表

希希里之海

发布于 2019-05-15 10:32:07

3700

发布于 2019-05-15 10:32:07

文章被收录于专栏：weixuqin 的专栏weixuqin 的专栏

leecode刷题（27）-- 合并k个排序链表

合并k个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

思路

以前做过合并两个有序链表的问题，所以刚开始想到的解法与之类似，我们可以先合并两个有序链表，再用合并的新链表去合并第三个链表：

1->1->3->4->4->5
1->1->2->3->4->4->5->6

其实如果我们学习过堆相关的知识，还可以用最小堆来解决这个问题：

读取所有链表值
构造一个最小堆（python中有 headp 方法，java中有 PriorityQueue 方法
根据最小堆构造一个链表

代码如下

python 描述

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

from heapq import heapify, heappop

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        
        # 读取所有节点值
        h = []
        for node in lists:
            while node:
                h.append(node.val)
                node = node.next

        if not h:
            return None
        
        # 构造一个最小堆
        heapify(h)  # 转换为最小堆

        # 构造链表
        root = ListNode(heappop(h))
        curnode = root
        while h:
            nextnode = ListNode(heappop(h))
            curnode.next = nextnode
            curnode = nextnode
        return root

java 描述

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 读取所有节点值
        List<Integer> h = new ArrayList();
        for (ListNode node: lists) {
            while (node != null) {
                h.add(node.val);
                node = node.next;
            }
        }

        // 构造一个最小堆
        if (!h.isEmpty())   return null;
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue();
        // 将元素添加进最小堆中
        for (Integer h1: h) {
            priorityQueue.offer(h1);
        }

        //构造链表
        ListNode root = priorityQueue.poll();
        ListNode curNode = root;
        while (!priorityQueue.isEmpty()) {
            ListNode nextNode = priorityQueue.poll();
            curNode.next = nextNode;
            curNode = nextNode;
        }
        return root;
    }
}