Merge k sorted lists#

Levels: level-5

Data structures: linkedlist, heap

Practice Link#

Description#

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

Example#

1Input:
2[
3  1->4->5,
4  1->3->4,
5  2->6
6]
7Output: 1->1->2->3->4->4->5->6

Python Solution#

 1class ListNode(object):
 2    def __init__(self, x):
 3        self.val = x
 4        self.next = None
 5
 6
 7class Solution(object):
 8    # This O(N*log k). Divide and conquer
 9    def mergeKLists(self, lists):
10        """
11        :type lists: List[ListNode]
12        :rtype: ListNode
13        """
14        amount = len(lists)
15        interval = 1
16        while interval < amount:
17            for i in range(0, amount - interval, interval * 2):
18                lists[i] = self.merge2Lists(lists[i], lists[i + interval])
19            interval *= 2
20        return lists[0] if amount > 0 else lists
21
22    def merge2Lists(self, l1, l2):
23        head = point = ListNode(0)
24        while l1 and l2:
25            if l1.val <= l2.val:
26                point.next = l1
27                l1 = l1.next
28            else:
29                point.next = l2
30                l2 = l1
31                l1 = point.next.next
32            point = point.next
33        if not l1:
34            point.next = l2
35        else:
36            point.next = l1
37        return head.next