TIC
The Interns Company

Merge k Sorted Lists

HardAcceptance: 48.2%
Linked ListDivide and ConquerHeap (Priority Queue)Merge Sort

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.

Constraints:

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

Input Format:

  • An array of k linked-lists lists, each linked-list is sorted in ascending order

Output Format:

  • A single sorted linked-list that is the result of merging all k linked-lists

Examples:

Example 1:

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

Example 2:

Input:

lists = []

Output:

[]

Explanation:

There are no linked-lists to merge.

Example 3:

Input:

lists = [[]]

Output:

[]

Explanation:

There is one empty linked-list to merge.

Solutions

Priority Queue (Min Heap) Approach

Time: O(N logk) where N is the total number of nodes and k is the number of linked lists
Space: O(k) for the priority queue

Use a priority queue to efficiently find the smallest element among all current nodes of the lists.

Divide and Conquer Approach

Time: O(N logk) where N is the total number of nodes and k is the number of linked lists
Space: O(logk) for the recursion stack

Recursively merge pairs of lists until there is only one list left.

Brute Force Approach

Time: O(N*k) where N is the total number of nodes and k is the number of linked lists
Space: O(1) extra space (not counting the output list)

Merge all linked lists one by one, building up the final result list.

Algorithm Walkthrough

Example input:

Step-by-step execution:

  1. Input: lists = [[1,4,5],[1,3,4],[2,6]]
  2. Priority Queue Approach:
  3. Initialize a min heap: []
  4. Add first nodes from each list: [(1,0), (1,1), (2,2)]
  5. Initialize dummy node and tail pointer
  6. While heap is not empty:
  7. Extract minimum node (1,0)
  8. Add to result list: tail.next = 1
  9. Add next node from same list: [(1,1), (2,2), (4,0)]
  10. Extract minimum node (1,1)
  11. Add to result list: tail.next = 1
  12. Add next node from same list: [(2,2), (3,1), (4,0)]
  13. Extract minimum node (2,2)
  14. Add to result list: tail.next = 2
  15. Add next node from same list: [(3,1), (4,0), (6,2)]
  16. Extract minimum node (3,1)
  17. Add to result list: tail.next = 3
  18. Add next node from same list: [(4,0), (4,1), (6,2)]
  19. Extract minimum node (4,0)
  20. Add to result list: tail.next = 4
  21. Add next node from same list: [(4,1), (5,0), (6,2)]
  22. Extract minimum node (4,1)
  23. Add to result list: tail.next = 4
  24. No more nodes from this list
  25. Extract minimum node (5,0)
  26. Add to result list: tail.next = 5
  27. No more nodes from this list
  28. Extract minimum node (6,2)
  29. Add to result list: tail.next = 6
  30. No more nodes from this list
  31. Heap is empty, return result list: [1,1,2,3,4,4,5,6]

Hints

Hint 1
Compare the heads of all the linked lists and select the smallest value as the next node in the merged list.
Hint 2
Use a Min Heap (Priority Queue) to efficiently find the smallest among k nodes.
Hint 3
Consider using the divide and conquer approach by merging lists two at a time.
Hint 4
Build upon the solution for the 'Merge Two Sorted Lists' problem.

Video Tutorial

Merge K Sorted Lists - Heap and Divide & Conquer Approaches

YouTube•Learn the Merge k Sorted Lists solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the merging process as nodes are selected from k lists and appended to the result list.

Key visualization elements:

  • current heap state
  • selected node
  • merged list so far

Similar Questions

Merge Two Sorted Lists

Easy

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Asked By

AmazonMicrosoftFacebookGoogleAppleUberLinkedInTwitter

Implementation Notes

This problem extends the idea of 'Merge Two Sorted Lists' to k lists. Both priority queue and divide and conquer approaches have the same time complexity, but the priority queue solution is often more intuitive for interviews. The brute force approach is less efficient but still worth understanding for simpler cases.