#23

Hard

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Merge k Sorted Lists

Merge k Sorted Lists requires efficiently combining multiple sorted linked lists into one using pointers and priority queues.

linked list divide and conquer heap priority queue merge sort

Problem Statement

You are given an array of k sorted linked lists, each in ascending order. Your task is to merge all the linked lists into one single sorted linked list and return its head.

Each linked list may be empty, and the total number of nodes across all lists will not exceed 10,000. Ensure your solution handles edge cases efficiently and maintains proper pointer integrity during merging.

Examples

Example 1

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

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

The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted linked list: 1->1->2->3->4->4->5->6

Example 2

Input: lists = []

Output: []

Example details omitted.

Example 3

Input: lists = [[]]

Output: []

Example details omitted.

Constraints

k == lists.length
0 <= k <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 104.

Solution Approach

Min-Heap (Priority Queue) Approach

Insert the head of each non-empty linked list into a min-heap. Repeatedly extract the smallest node from the heap, append it to the merged list, and if that node has a next, push it into the heap. This ensures the merged list remains sorted with time complexity O(N log k), where N is the total number of nodes.

Divide and Conquer Merge

Recursively merge pairs of lists until one list remains. This approach reduces the number of merge operations per level, giving a time complexity of O(N log k). It relies on careful pointer manipulation to avoid breaking the linked list chains during pairwise merges.

Iterative Pairwise Merge

Iterate through the list array and merge two lists at a time, updating the array with merged results. While simpler, it may be less efficient for large k because repeated merging can increase pointer adjustments, leading to higher constant factors in runtime.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the approach: min-heap gives O(N log k), divide and conquer also O(N log k), and iterative pairwise merges can approach O(kN) in worst cases. Space complexity varies: heap requires O(k) extra space, recursive divide and conquer uses O(log k) call stack, and iterative merges can be O(1) if done in place.

What Interviewers Usually Probe

Check if you are correctly maintaining all pointers during merges.
Consider edge cases like empty lists or lists with duplicate values.
Clarify which merging strategy optimizes both runtime and memory usage.

Common Pitfalls or Variants

Common pitfalls

Losing references to remaining nodes when reassigning pointers.
Not handling empty linked lists, causing null pointer errors.
Assuming all lists have equal lengths, leading to logic errors in merges.

Follow-up variants

Merge k sorted arrays instead of linked lists using the same heap or divide-and-conquer logic.
Merge k nearly-sorted lists where each list has only a small number of out-of-order nodes.
Merge k descending sorted linked lists into ascending order by reversing first or using a max-heap.

FAQ

What is the best approach to merge k sorted linked lists efficiently?

Using a min-heap ensures O(N log k) time and handles pointer updates safely. Divide and conquer merging is another optimal approach.

How do I handle empty linked lists in Merge k Sorted Lists?

Skip empty lists when inserting into the heap or during pairwise merges, ensuring you don't dereference null pointers.

Is recursive divide-and-conquer safer than iterative merging?

It reduces total merge operations and keeps pointers manageable, but you must watch recursion stack limits for large k.

Can I merge arrays using the same strategy?

Yes, heap and divide-and-conquer logic applies to arrays with similar complexity, but pointer handling translates to index management.

Why do duplicate values in lists affect pointer manipulation?

Duplicates require careful next-pointer updates to maintain list integrity; forgetting them can skip nodes or create cycles.

terminal

Solution

Solution 1: Priority Queue (Min Heap)

We can create a min heap $pq$ to maintain the head nodes of all linked lists. Each time, we take out the node with the smallest value from the min heap, add it to the end of the result linked list, and then add the next node of this node to the heap. Repeat the above steps until the heap is empty.

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[Optional[ListNode]]) -> Optional[ListNode]:
        setattr(ListNode, "__lt__", lambda a, b: a.val < b.val)
        pq = [head for head in lists if head]
        heapify(pq)
        dummy = cur = ListNode()
        while pq:
            node = heappop(pq)
            if node.next:
                heappush(pq, node.next)
            cur.next = node
            cur = cur.next
        return dummy.next

Continue Practicing

#148 sort list #912 sort an array #109 convert sorted list to binary search tree