Post

Leetcode 23. Merge k Sorted Lists

Explanation for Leetcode 23 - Merge k Sorted Lists, and its solution in Python.

Posted
By Hyeonu(Eric) Kim
1 min read

Problem

Leetcode 23 - Merge k Sorted Lists

Example:

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

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

Input: lists = []
Output: []

Input: lists = [[]]
Output: []

Approach

We can first think of solution smaller ‘what if there were only 2 lists’ then we can simply solve this by comparing list1 and list2’s values and merge them. This can be our helper function, and we can iterate through the whole lists

First we’ll have 6 linked lists in a list for example, then 3 after merging 2 each, then finally 1 linked list.

Visualization of the Approach:

1
2
3
4
5
6
7
8
9
10
11

lists = [[1,4,5],[1,3,4],[2,6]]
list1 = [1,4,5]
list2 = [1,3,4]
merged = [1,1,3,4,4,5]

lists = [[1,1,3,4,4,5], [2,6]]
list1 = [1,1,3,4,4,5]
list2 = [2,6]
merged = [1,1,2,3,4,4,5,6]

thus return [1,1,2,3,4,4,5,6]

Here is the Python code for the solution:

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

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists or len(lists) == 0:
            return None
        
        while len(lists) > 1:
            mergedList = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i+1] if (i+1) < len(lists) else None
                mergedList = self.mergeList(l1, l2)
            lists = mergedList
        
        return lists[0]

    def mergeList(self, l1, l2):
        dummy = ListNode(0)
        curr = dummy
        while l1 and l2:
            if l1.val < l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        
        if l1:
            curr.next = l1
        if l2:
            curr.next = l2
        return dummy.next

Time Complexity and Space Complexity

Time Complexity: $O(n log k)$ where $n$ is total number of nodes $k$ is total number of lists

Space Complexity: $O(k)$

Leetcode, Linked List, Hard
Leetcode Python Study Linked List Hard
This post is licensed under CC BY 4.0 by the author.