[LeetCode]题解（python）：023-Merge k Sorted Lists

题目来源:

　　https://leetcode.com/problems/merge-k-sorted-lists/

题意分析：

　　给定k个有序的链表，将这些链表整合成一个新的有序链表。

题目思路：

　　前面我们已经给出了两个有序链表整合的做法。这里，我们不妨用归并排序的想法，把n个链表看成 n/2 和n - n/2的整合，直到n/2 <= 1。时间复杂度是 O(n * （2^log k）) = O(n * k).

代码（python）：

 1 # Definition for singly-linked list.
 2 # class ListNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution(object):
 8     def mergeTwolists(self,l1,l2):
 9         """
10         :type l1: ListNode
11         :type l2: ListNode
12         :rtype: ListNode
13         """
14         ans = ListNode(0)
15         tmp = ans
16         if l1 == None and l2 == None:
17             return None
18         while l1 !=None or l2 != None:
19             if l1 == None:
20                 while l2 != None:
21                     tmp.val = l2.val
22                     l2 = l2.next
23                     if l2 == None:
24                         break
25                     tmp.next = ListNode(0)
26                     tmp = tmp.next
27                 break
28             if l2 == None:
29                 while l1 != None:
30                     tmp.val = l1.val
31                     l1 = l1.next
32                     if l1 == None:
33                         break
34                     tmp.next = ListNode(0)
35                     tmp = tmp.next
36                 break
37             if l1.val <= l2.val:
38                 tmp.val = l1.val
39                 l1 = l1.next
40             else:
41                 tmp.val = l2.val
42                 l2 = l2.next
43             tmp.next = ListNode(0)
44             tmp = tmp.next
45         return ans
46     def mergeKLists(self, lists):
47         """
48         :type lists: List[ListNode]
49         :rtype: ListNode
50         """
51         size = len(lists)
52         if size == 0:
53             return None
54         if size == 1:
55             return lists[0]
56         n = size // 2
57         tmp1 = self.mergeKLists(lists[:n])
58         tmp2 = self.mergeKLists(lists[n:])
59         return self.mergeTwolists(tmp1,tmp2)
60

View Code

转载请注明出处：http://www.cnblogs.com/chruny/p/4872905.html