Problem

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.

Examples

Example 1:

 graph TB
 classDef darkMode fill:transparent,stroke:#ff8c00,stroke-width:2px,font-weight:bold,font-size:14px;
 
	subgraph In[" "]
		L1(1):::darkMode --> L2(4):::darkMode --> L3(5):::darkMode
		L4(1):::darkMode --> L5(3):::darkMode --> L6(4):::darkMode
		L7(2):::darkMode --> L8(6):::darkMode
	end
 
	subgraph Out[" "]
		A(1):::darkMode --> B(1):::darkMode --> C(2):::darkMode --> D(3):::darkMode --> E(4):::darkMode --> F(4):::darkMode --> G(5):::darkMode --> H(6):::darkMode
	end
	
	In -->|"Merge"| Out
 linkStyle default stroke:#ff8c00,stroke-width:2px;
  
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

Similar Problems

Merge 2 Sorted Linked Lists

Solution

This problem is marked hard, depending on how we solve this problem. This is

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Using merge 2 lists solution sequentially

We have already solved Merge Two Sorted Lists. The naive approach involves merging the k sorted linked lists by iteratively merging two lists at a time. This approach is simple but less efficient compared to the optimal solution. Here’s how it works:

  1. Sequentially Merge Two Lists at a Time:
    • Start with the first two linked lists.
    • Merge them into a single sorted list.
    • Continue merging the result with the next linked list, until all k lists are merged.
  2. Merge Two Sorted Lists:
    • Use the technique for merging two sorted linked lists.
    • Compare the values at the current nodes of both lists, and append the smaller node to the result list.
    • Move to the next node in the list that contributed the smaller node.
    • Repeat until both lists are fully merged.

Code

 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

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        
        for (ListNode l : lists) {
            ans = mergeTwoLists(ans, l);
        }
        
        return ans;
    }
    
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode ans = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                ans.next = l1;
                l1 = l1.next;
            } else {
                ans.next = l2;
                l2 = l2.next;
            }
            ans = ans.next;
        }
        
        ans.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        def mergeTwoLists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
            dummy = ListNode(-1)
            ans = dummy
            
            while l1 and l2:
                if l1.val < l2.val:
                    ans.next = l1
                    l1 = l1.next
                else:
                    ans.next = l2
                    l2 = l2.next
                ans = ans.next
            
            ans.next = l1 if l1 else l2
            return dummy.next
        
        ans = None
        for l in lists:
            ans = mergeTwoLists(ans, l)
        
        return ans

Complexity

  • ⏰ Time complexity: O(n*k). Each merge operation takes O(n) where n is the total number of nodes across all linked lists. Merging k linked lists sequentially results in: O(nk) This is due to k - 1 merge operations.
  • 🧺 Space complexity: O(1). This approach uses no additional data structures apart from the output linked list nodes.

Method 2 - Using Merge sort Divide and Conquer (recursive)

This is similar to Merge Sort Algorithm#Method 1 - Recursive Top Down Merge Sort solution, resembling method 3’s iterative approach.

Code

 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
34
35
36
37
38
39

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return mergeSort(lists, 0, lists.length - 1);
    }
    
    private ListNode mergeSort(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        if (start > end) {
            return null;
        }
        
        int mid = (start + end) / 2;
        ListNode left = mergeSort(lists, start, mid);
        ListNode right = mergeSort(lists, mid + 1, end);
        
        return mergeTwoLists(left, right);
    }
    
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode ans = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                ans.next = l1;
                l1 = l1.next;
            } else {
                ans.next = l2;
                l2 = l2.next;
            }
            ans = ans.next;
        }
        
        ans.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}
 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

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        def mergeTwoLists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
            dummy = ListNode(-1)
            ans = dummy
            
            while l1 and l2:
                if l1.val < l2.val:
                    ans.next = l1
                    l1 = l1.next
                else:
                    ans.next = l2
                    l2 = l2.next
                ans = ans.next
            
            ans.next = l1 if l1 else l2
            return dummy.next
        
        def mergeSort(lists: List[Optional[ListNode]], start: int, end: int) -> Optional[ListNode]:
            if start == end:
                return lists[start]
            if start > end:
                return None
            
            mid = (start + end) // 2
            left = mergeSort(lists, start, mid)
            right = mergeSort(lists, mid + 1, end)
            
            return mergeTwoLists(left, right)
        
        return mergeSort(lists, 0, len(lists) - 1)

Complexity

  • ⏰ Time complexity: O(n log k)
  • 🧺 Space complexity: O(k)

Method 3 - Using merge 2 lists solution in a merge sort way

We have already solved Merge Two Sorted Linked Lists, that merges 2 sorted lists. We can also club Merge Sort Algorithm#Method 2 - Iterative or Bottom up Merge Sort.

So, we will keep on merging 2 lists at a time, till we have 1 list remaining.

So, initially we will have k/2 lists remaining, then k/4 and finally after some time 1 remaining. We take O(n) time to merging 2 sorted lists, finally we have time complexity of O(n * log k).

1
2

T(N) = 2 T(K/2) + N
T(N) = O (N log K)

Code

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

public ListNode mergeKLists(ListNode[] lists) {
	if (lists == null || lists.length == 0)
		return null;

	int k = lists.length;

	while(k>=1){
		// pick 1 list from start, another for end.
		for(int i = 0; i < k/2; i++){
			ListNode l1 = lists[i];
			ListNode l2 = lists[k-i-1];
			lists[i] = mergeTwoLists(l1, l2);
		}
		// we have to now process remaining k/2 list
		k = k /2;
	}

	return lists[0];
}
 
1
2
3
4
5
6
7
8
9

public ListNode mergeKLists(ListNode[] lists) {
	if(lists==null || lists.length==0) return null;
	
	for(int step = 1; step < lists.length; step <<= 1) {
		for(int i = 0; i < lists.length-step; i += 2*step)
			lists[i] = mergeTwoLists(lists[i], lists[i+step]);
	}
	return lists[0];
}

Complexity

  • ⏰ Time complexity: O(n log k)
  • 🧺 Space complexity: O(1)

Cons: Does in place modification.

Method 4 - Using Min Heap

We should add heads of all k sorted lists. At every instant, you need the minimum of the head of all the k linked list. Once you know the minimum, you can push the node to your answer list, and move over to the next node in that linked list.

The simplest solution is using PriorityQueue as min heap. The elements of the priority queue are ordered according to their natural ordering, or by a comparator provided at the construction time (in this case).

Code

 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

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare(a.val, b.val) // Compare nodes by their value
        );
        
        // Add the head nodes of all lists to the priority queue
        for (ListNode head : lists) {
            if (head != null) {
                minHeap.add(head);
            }
        }
        
        ListNode dummy = new ListNode(-1);
        ListNode ans = dummy;
        
        while (!minHeap.isEmpty()) {
            // Extract the smallest node
            ListNode node = minHeap.poll();
            ans.next = node;
            ans = ans.next;
            
            // If the node has a next element, add it to the heap
            if (node.next != null) {
                minHeap.add(node.next);
            }
        }
        
        return dummy.next;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def mergeKLists(self, lists: List[Optional['ListNode']]) -> Optional['ListNode']:
        # Create a min-heap
        min_heap: List[Tuple[int, int, ListNode]] = []
        
        # Add the head nodes of all linked lists to the heap (value, index, node)
        for i, head in enumerate(lists):
            if head:
                heapq.heappush(min_heap, (head.val, i, head))
        
        dummy = ListNode(-1)
        ans = dummy

        while min_heap:
            # Extract the smallest node (value, index, node)
            _, i, node = heapq.heappop(min_heap)
            ans.next = node
            ans = ans.next

            # If the extracted node has a next node, insert its next node into the heap
            if node.next:
                heapq.heappush(min_heap, (node.next.val, i, node.next))

        return dummy.next

Complexity

  • ⏰ Time complexity: O(log(k) * n), k is number of list and n is number of total elements.
  • 🧺 Space complexity: O(k)