题解 | #合并k个已排序的链表#

合并k个已排序的链表

http://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6

算法思想一：辅助数组

解题思路

主要采用将列表中的链表结点值遍历存储到辅助数组中，再对数组进行排序，根据排序后的数组元素一次构建新链表

1、遍历列表，分别将每一个链表的元素值存储到数组tmp中

2、对tmp进行排序

3、依次遍历数组元素创新新链表

代码展示：

Python版本

class Solution:
    def mergeKLists(self , lists ):
        # write code here
        # 将所有链表元素存放到list中，排序后再转换为链表
        tmp = []
        for head in lists:
            while head:
                # 将链表结点存放到tmp中
                tmp.append(head.val)
                head = head.next
        if not tmp:
            return None
        # tmp进行排序
        tmp.sort()
        res = ListNode(-1)
        cur = res
        # 根据tmp生成新的链表
        for i in range(len(tmp)):
            cur.next = ListNode(tmp[i])
            cur = cur.next
        return res.next

复杂度分析

时间复杂度O(NlogN)：N表示列表中所有链表的结点数量，首先遍历所有结点O(N)，排序O(NlogN)

空间复杂度O(N)：辅助数组空间

算法思想二：顺序合并

解题思路

1、将k个链表配对并将同一对中的链表进行合并（采用顺序合并的方法）

2、第一轮合并后，k个链表合并成了 k/2 个链表，平均长度 2n/k ，然后是 k/4、k/8...等等

3、重复这一过程，知道获取最终的有序链表

图解：

代码展示：

JAVA版本

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayListlists) {
        // 采用分治进行合并链表
        return mergeList( lists , 0 , lists.size() - 1 );
    }
    // 分治进行链表两两合并
    public ListNode mergeList(ArrayListlists , int L ,int R){
        
        if(L == R){
            return lists.get(L);
        }
        if(L > R){
            return null;
        }
        
        int mid = L + ((R - L) >> 1);
        return merge( mergeList(lists,L,mid) , mergeList(lists,mid+1,R));
    }
    
    // 合并两个链表，对比合并
    public ListNode merge(ListNode l1 , ListNode l2){
        
        if(l1 == null || l2 == null){
            return l1 == null ? l2 : l1;
        }
        
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        
        while( l1 != null && l2 != null){
            
            if(l1.val < l2.val){ cur.next = l1; l1 = l1.next; }else{ cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = (l1 == null ? l2 : l1); return dummy.next; } }

复杂度分析

时间复杂度O(Nlogk)：N表示列表中所有链表的结点数量，K表示链表的数量

空间复杂度O(logk)：递归会使用到 O(logk) 空间代价的栈空间

算法思想三：优先队列

解题思路

使用优先队列去存储所有链表。按照链表头结点值，进行从小到大的排序，最小的头结点的链表在堆顶。
1、每次将堆顶的链表取出
2、将头结点从取出的链表上去除，并插在所需目标链表的尾部。
3、将取出的链表放回堆中。若链表为null，则不放回。
重复1，2，3过程，直到堆为空，循环终止。

代码展示：

Python版本

import heapq

class Solution:
    def mergeKLists(self , lists ):
        # write code here
        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