23. Merge K Sorted Lists - Explanation

Description

You are given an array of k linked lists lists, where each list is sorted in ascending order.

Return the sorted linked list that is the result of merging all of the individual linked lists.

Example 1:

Input: lists = [[1,2,4],[1,3,5],[3,6]]

Output: [1,1,2,3,3,4,5,6]

Example 2:

Input: lists = []

Output: []

Example 3:

Input: lists = [[]]

Output: []

Constraints:

0 <= lists.length <= 1000
0 <= lists[i].length <= 100
-1000 <= lists[i][j] <= 1000

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n * k) time and O(1) space, where k is the total number of lists and n is the total number of nodes across all lists.

Hint 1

A brute-force solution would involve storing all n nodes in an array, sorting them, and converting the array back into a linked list, resulting in an O(nlogn) time complexity. Can you think of a better way? Perhaps consider leveraging the idea behind merging two sorted linked lists.

Hint 2

We can merge two sorted linked lists without using any extra space. To handle k sorted linked lists, we can iteratively merge each linked list with a resultant merged list. How can you implement this?

Hint 3

We iterate through the list array with index i, starting at i = 1. We merge the linked lists using mergeTwoLists(lists[i], lists[i - 1]), which returns the head of the merged list. This head is stored in lists[i], and the process continues. Finally, the merged list is obtained at the last index, and we return its head.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

The simplest way to merge all linked lists is to ignore the list structure, collect every value, sort them, and then rebuild a single sorted linked list.
This doesn’t use any clever merging logic — it is purely based on gathering and sorting.
It’s easy to implement but not efficient because sorting dominates the runtime.

Algorithm

Create an empty list nodes.
For each linked list:
- Traverse it and append every node’s value to nodes.
Sort the nodes list.
Create a new linked list:
- Use a dummy head.
- For each value in the sorted list, create a new node and attach it.
Return the head of the new merged linked list.

# 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]:
        nodes = []
        for lst in lists:
            while lst:
                nodes.append(lst.val)
                lst = lst.next
        nodes.sort()

        res = ListNode(0)
        cur = res
        for node in nodes:
            cur.next = ListNode(node)
            cur = cur.next
        return res.next

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

2. Iteration

Intuition

We repeatedly pick the smallest head node among all the lists and attach it to our result list.
At every step:

Look at the first node of each non-empty list.
Choose the one with the smallest value.
Move that list’s pointer forward.
Append the chosen node to our merged list.

This is similar to merging k sorted arrays by always picking the smallest available element.

Algorithm

Create a dummy node to build the merged list.
Set a pointer cur to the dummy.
Repeat:
- Search through all lists to find the list whose current node has the smallest value.
- If no list has remaining nodes (all are empty), stop.
- Attach the smallest node to cur.next.
- Move cur forward.
- Move the chosen list’s pointer to its next node.
Return the merged list starting from 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 mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        res = ListNode(0)
        cur = res

        while True:
            minNode = -1
            for i in range(len(lists)):
                if not lists[i]:
                    continue
                if minNode == -1 or lists[minNode].val > lists[i].val:
                    minNode = i

            if minNode == -1:
                break
            cur.next = lists[minNode]
            lists[minNode] = lists[minNode].next
            cur = cur.next

        return res.next

Time & Space Complexity

Time complexity: $O(n * k)$
Space complexity: $O(1)$

Where $k$ is the total number of lists and $n$ is the total number of nodes across $k$ lists.

3. Merge Lists One By One

Intuition

Instead of merging all k lists at once, we can merge them one by one.

First merge list 0 and list 1 → get a sorted list.
Then merge that result with list 2.
Then merge that result with list 3.
Repeat until all lists are merged.

Each merge operation is just like the standard “merge two sorted linked lists” problem:

Compare the heads.
Attach the smaller one.
Move that list’s pointer forward.
Continue until one list is empty, then attach the rest of the other list.

Algorithm

If the list of lists is empty, return null (or equivalent).
For each list from index 1 to k - 1:
- Merge lists[i - 1] and lists[i] into a single sorted list.
- Store the merged result back into lists[i].
After the loop, lists[k - 1] will contain the fully merged list.
Return lists[k - 1].

Merging two lists (mergeList(l1, l2)):

Create a dummy node and a tail pointer starting at the dummy.
While both l1 and l2 are non-empty:
- Compare l1.val and l2.val.
- Attach the smaller node to tail.next.
- Move that list’s pointer forward.
- Move tail forward.
If one list still has remaining nodes, attach it to tail.next.
Return dummy.next as the merged head.

# 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) == 0:
            return None

        for i in range(1, len(lists)):
            lists[i] = self.mergeList(lists[i - 1], lists[i])

        return lists[-1]

    def mergeList(self, l1, l2):
        dummy = ListNode()
        tail = dummy

        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        if l1:
            tail.next = l1
        if l2:
            tail.next = l2
        return dummy.next

Time & Space Complexity

Time complexity: $O(n * k)$
Space complexity: $O(1)$

Where $k$ is the total number of lists and $n$ is the total number of nodes across $k$ lists.

4. Heap

Intuition

We want to always pick the smallest current node among all k lists as efficiently as possible.

Instead of scanning all heads every time (which is slow), we can use a min-heap (priority queue):

Push the head of each non-empty list into the heap.
The heap always gives us the node with the smallest value on top.
We pop that node, attach it to our result list, and then push its next node (if it exists) into the heap.
Repeat until the heap is empty.

This way, at every step we choose the globally smallest node in O(log k) time, where k is the number of lists.

Algorithm

Create a min-heap (priority queue).
For each non-empty linked list:
- Push its head node into the heap (keyed by node value).
Create a dummy node to start the result list, and a pointer cur pointing to it.
While the heap is not empty:
- Pop the node with the smallest value from the heap.
- Attach this node to cur.next, and move cur forward.
- If this node has a next node, push that next node into the heap.
When the heap is empty, all nodes have been merged in sorted order.
Return dummy.next as the head of the merged list.

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

class NodeWrapper:
    def __init__(self, node):
        self.node = node

    def __lt__(self, other):
        return self.node.val < other.node.val

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

        res = ListNode(0)
        cur = res
        minHeap = []

        for lst in lists:
            if lst is not None:
                heapq.heappush(minHeap, NodeWrapper(lst))

        while minHeap:
            node_wrapper = heapq.heappop(minHeap)
            cur.next = node_wrapper.node
            cur = cur.next

            if node_wrapper.node.next:
                heapq.heappush(minHeap, NodeWrapper(node_wrapper.node.next))

        return res.next

Time & Space Complexity

Time complexity: $O(n \log k)$
Space complexity: $O(k)$

Where $k$ is the total number of lists and $n$ is the total number of nodes across $k$ lists.

5. Divide And Conquer (Recursion)

Intuition

Instead of merging all k lists at once or one by one in order, we can use a divide and conquer strategy, similar to how merge sort works.

Idea:

Split the list of linked lists into two halves.
Recursively merge the left half into one sorted list.
Recursively merge the right half into one sorted list.
Finally, merge these two sorted lists into a single sorted list.

By always merging pairs of lists, we reduce the total work compared to merging k lists sequentially.
Each merge of two lists is linear in their total length, and we do about log k levels of merging.

This makes the approach both clean and efficient.

Algorithm

Base Cases
- If the input list lists is empty, return null.
- Use a recursive function divide(lists, l, r):
  - If l > r, return null.
  - If l == r, return lists[l] (only one list to return).
Divide Step
- Compute mid = (l + r) // 2.
- Recursively compute:
  - left = divide(lists, l, mid)
  - right = divide(lists, mid + 1, r)
Conquer Step (merge two lists)
- Merge left and right using the standard merge two sorted linked lists routine:
  - Create a dummy node and use a curr pointer.
  - While both lists are non-empty:
    - Attach the smaller node to curr.next.
    - Move that list’s pointer forward.
    - Move curr forward.
  - Attach any remaining nodes from either list.
- Return the merged list.
Final Answer
- Call divide(lists, 0, len(lists) - 1) and return the resulting list.

This approach efficiently merges k sorted linked lists in a structured, recursive way.

# 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):
        if not lists or len(lists) == 0:
            return None
        return self.divide(lists, 0, len(lists) - 1)

    def divide(self, lists, l, r):
        if l > r:
            return None
        if l == r:
            return lists[l]

        mid = l + (r - l) // 2
        left = self.divide(lists, l, mid)
        right = self.divide(lists, mid + 1, r)

        return self.conquer(left, right)

    def conquer(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
        else:
            curr.next = l2

        return dummy.next

Time & Space Complexity

Time complexity: $O(n \log k)$
Space complexity: $O(\log k)$

Where $k$ is the total number of lists and $n$ is the total number of nodes across $k$ lists.

6. Divide And Conquer (Iteration)

Intuition

This is the same idea as divide and conquer, but done iteratively instead of using recursion.

We repeatedly merge the lists in pairs:

In one pass:
- Merge list 0 and list 1 → get M0
- Merge list 2 and list 3 → get M1
- Merge list 4 and list 5 → get M2
- … and so on.
After this pass, we have fewer lists (about half as many).
Repeat this process on the new list of merged lists until only one list remains.

Each pairwise merge is just the usual merge of two sorted linked lists.
By always merging lists two at a time, the total work is efficient and structured, similar to the merge step in merge sort.

Algorithm

If lists is empty, return null.
While the number of lists is greater than 1:
- Create an empty list mergedLists.
- Loop over lists in steps of 2:
  - Let l1 = lists[i].
  - Let l2 = lists[i + 1] if it exists, otherwise None.
  - Merge l1 and l2 using mergeList and append the result to mergedLists.
- Set lists = mergedLists.
When the loop ends, lists[0] is the fully merged sorted list. Return it.

Merging two lists (mergeList(l1, l2)):

Create a dummy node and a tail pointer pointing to it.
While both l1 and l2 are non-empty:
- Attach the smaller of l1 and l2 to tail.next.
- Move the chosen list’s pointer forward.
- Move tail forward.
Attach any remaining nodes from l1 or l2 to tail.next.
Return dummy.next as the merged head.

# 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 not lists or len(lists) == 0:
            return None

        while len(lists) > 1:
            mergedLists = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if (i + 1) < len(lists) else None
                mergedLists.append(self.mergeList(l1, l2))
            lists = mergedLists
        return lists[0]

    def mergeList(self, l1, l2):
        dummy = ListNode()
        tail = dummy

        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next

        if l1:
            tail.next = l1
        if l2:
            tail.next = l2

        return dummy.next

Time & Space Complexity

Time complexity: $O(n \log k)$
Space complexity: $O(k)$

Where $k$ is the total number of lists and $n$ is the total number of nodes across $k$ lists.