23. Merge k Sorted Lists
Merge _k_ sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
1 2 3 4 5 6 7
| Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6
|
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
|
class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ if not lists: return None start = 0 end = len(lists) - 1 while start != end or end != 0: if start >= end: start = 0 else: lists[start] = self.mergeTwoLists(lists[start], lists[end]) start += 1 end -= 1 return lists[0]
def mergeTwoLists(self, l1, l2): current = head = ListNode(0) while l1 and l2: if l1.val <= l2.val: current.next = l1 l1 = l1.next else: current.next = l2 l2 = l2.next current = current.next current.next = l1 or l2 return head.next
|