合并K个排序链表

中英题面

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

Mergeksorted linked lists and return it as one sorted list. Analyze and describe its complexity.

示例:

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

Example:

　　Input:
　　[
　　  1->4->5,
　　  1->3->4,
　　  2->6
　　]
　　Output: 1->1->2->3->4->4->5->6  <br /><br /><br /><br />

算法

分治并结合归并排序思想。

时间复杂度：

O(NlogK)

空间复杂度：

O(logK)

代码

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def mergeKLists(self, lists):
         """
         :type lists: List[ListNode]
         :rtype: ListNode
         """
         if (not lists):
             return None
         if (len(lists) == 1):
             return lists[0]
         mid = len(lists) // 2
         hen = self.mergeKLists(lists[: mid])
         tai = self.mergeKLists(lists[mid :])
         if (not hen):
             return tai
         if (not tai):
             return hen
         if (hen.val > tai.val):
             hen, tai = tai, hen
         i = hen
         while (tai):
             if (i.next):
                 if (i.next.val > tai.val):
                     tai.next, i.next, tai = i.next, tai, tai.next
                 i = i.next
             else:
                 i.next = tai
                 break
         return hen