Teaching Kids Programming – Divide and Conquer Algorithm to Merge K Sorted Linked List

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1-4-5,
1-3-4,
2-6
]
merging them into one sorted list:
1-1-2-3-4-4-5-6

Example 2:
Input: lists = []
Output: []

Example 3:
Input: lists = [[]]
Output: []

Algorithm Re-cap: Merge Two Sorted Linked List

We have learned the O(M+N) algorithm to merge two sorted list: Teaching Kids Programming – Merging Two Sorted List. Merging Two Sorted Linked Lists is no much different.

We can follow the linked list using two pointers, compare one by one, and link the smaller one. And append the remaining linked list (the longer segment) at last:

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def merge(self, a: ListNode, b: ListNode) -> ListNode:
        if a is None:
            return b
        if b is None:
            return a
        dummy = ListNode(-1)
        p = dummy
        while a and b:
            if a.val < b.val:
                p.next = a
                a = a.next
            else:
                p.next = b
                b = b.next
            p = p.next
        if a:
            p.next = a
        if b:
            p.next = b
        return dummy.next  

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def merge(self, a: ListNode, b: ListNode) -> ListNode:
        if a is None:
            return b
        if b is None:
            return a
        dummy = ListNode(-1)
        p = dummy
        while a and b:
            if a.val < b.val:
                p.next = a
                a = a.next
            else:
                p.next = b
                b = b.next
            p = p.next
        if a:
            p.next = a
        if b:
            p.next = b
        return dummy.next  

Divide and Conquer to Merge K sorted list

We can divide the list of linked list into two havles, and recursively merge them. If the number of the linked list to merge is less or equal to two, we know how to merge them (see above two sorted linked list).

Top-down Recursion, and then merged linked list again is merged into a bigger sorted list until we have a entire linked list that is sorted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        l = len(lists)
        if l == 0:
            return None
        if l == 1:
            return lists[0]
        if l == 2:
            return self.merge(lists[0], lists[1])
        mid = l // 2        
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])
        return self.merge(left, right)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        l = len(lists)
        if l == 0:
            return None
        if l == 1:
            return lists[0]
        if l == 2:
            return self.merge(lists[0], lists[1])
        mid = l // 2        
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])
        return self.merge(left, right)

The time complexity of divide and conquer is O(K) because we still need to merge K times and combining the above merging two sorted list O(N) the time complexity of merging K Sorted Linked List is O(KN) where N is the number of nodes in each list.

There are other algorithms (better) to merge K sorted linked list: How to Merge k Sorted Lists using Recursive Divide and Conquer Algorithms?

–EOF (The Ultimate Computing & Technology Blog) —