Sorting Spree

February 23, 2025 - 3 minutes read - 596 words

LC23 - Merge k Sorted Lists

Problem Statement

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.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

Smelling like merge sort in the air?

We know each list is already in sorted order. Does it remind us of the merge step from a classic merge-sort algorithm?

Let’s start by implementing a function that can merge two sorted linked lists together and return a newly built sorted list.

    def mergeTwoLists(self, list_1, list_2):
        node_1, node_2 = list_1, list_2
        merged_list = ListNode(0)
        merged = merged_list

        while node_1 and node_2:
            if node_1.val < node_2.val:
                merged.next = ListNode(node_1.val)
                node_1 = node_1.next
            else:
                merged.next = ListNode(node_2.val)
                node_2 = node_2.next
            #print(str(merged.val))
            merged = merged.next
            
        if node_1:
            merged.next = node_1
        if node_2:
            merged.next = node_2

        return merged_list.next

Great! Now, let’s merge the first two lists together. The resulting list will be merged with the third one and so on.

My mistake at this step is the list iteration: implementing the above suggestion results in doing a lot of redundant work. In the example of an input consisting of 6 initial lists, the first list is re-ordered sequentially 5 times! Time complexity is O(n * (k-1)) where k is the number of linked lists and n the number of nodes across those linked lists.

The smarter way of approaching this iteration is sort lists 2-by-2 until there is only 1 left. This divides the work done by 2 everytime, reducing the k-1 to logk. This results in time complexity of O(nlogk) and space complexity of O(n+logk).


# 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[Optional[ListNode]]) -> Optional[ListNode]:
        if len(lists) < 1: 
            return None

        if len(lists) == 1 and not lists[0]:
            return None
        
        # Bad way of doing it
        #res_list = lists[0]

        # for i in range(1, len(lists)):
        #   res_list = self.mergeTwoLists(res_list, lists[i])
        #return res_list
        
        # Better way of merging the lists
        res_list = lists
        
        while len(res_list) > 1:
            merged_list = []
            for i in range(0, len(res_list), 2):
                list_1 = res_list[i]
                list_2 = res_list[i+1] if i+1 < len(res_list) else None
                merged_list.append(self.mergeTwoLists(list_1, list_2))
            res_list = merged_list
 
        return res_list[0]

Easier approach using a heap

Using a heap data structure in my opinion is actually much easier. Iterating through the linked lists and putting the values in a minHeap takes care of the sorting for us in O(logn) where n is the number of elements in the heap.

Then, we can create the resulting linked list by popping each value out of the minHeap. The overall time complexity of this solution is O(nlogn) where n is the number of nodes across all linked lists. Space-wise, we’re landing at O(n).

class Solution:    
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if len(lists) < 1: 
            return None

        if len(lists) == 1 and not lists[0]:
            return None

        minHeap = []
        merged_list = ListNode(0)
        curr = merged_list

        for eachList in lists:
            node = eachList
            while node:
                heapq.heappush(minHeap, node.val)
                node = node.next
        
        while minHeap:
            curr_node = ListNode(heapq.heappop(minHeap))
            curr.next = curr_node
            curr = curr.next

        return merged_list.next

Which solution is most efficient depends on the input profile.

Where n total number of nodes is significantly larger than k - a few large lists, the merge-sort approach will perform better.

However, when k total number of linked lists is larger than n - many small lists, the heap solution might be preferred.

Algos
Python