Merge K Sorted Linked Lists Into One
Solve this ProblemHard25–30 min
Topics
Linked ListDivide and ConquerTwo Pointers
Companies
Practice:GFG ↗AmazonGoogleMicrosoftAdobe
Given an array of
k linked lists, each already sorted in non-decreasing order, merge all of them into one sorted linked list and return its head.
This is a direct extension of merging two sorted lists (see "Merge Two Sorted Linked Lists Into One") — the question is how to combine k of them without doing needlessly repeated work. A divide and conquerDivide and Conquer MergeSplit the k lists in half, recursively reduce each half down to a single sorted list, then merge those two results with an ordinary two-list merge. Halving at every level means each node only participates in about log k merges total, instead of up to k merges if lists were combined one at a time into a growing result. approach splits the array of lists in half, recursively merges each half down to one list, and combines the two halves with the same two-pointer splice used for two lists — turning k lists into one in O(N log k) instead of the O(N·k) that merging them one at a time would cost.
Test Case 1:
Input:lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output:[1, 1, 2, 3, 4, 4, 5, 6]
Explanation:Every value from all 3 lists, merged into one sorted list.
Test Case 2:
Input:lists = [[]]
Output:[]
Explanation:A single, empty list — nothing to merge.
Test Case 3:
Input:lists = [[], [1], [2, 3]]
Output:[1, 2, 3]
Explanation:An empty list among several is just skipped — it contributes nothing.
Constraints
- ◆
1 ≤ k (number of lists) ≤ 10 - ◆
0 ≤ number of nodes in each list ≤ 20 - ◆
-10⁴ ≤ node value ≤ 10⁴ - ◆
Each individual list is already sorted in non-decreasing order
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public Node mergeKLists(List<Node> lists) { |
| 3 | return merge(lists, 0, lists.size() - 1); |
| 4 | } |
| 5 | |
| 6 | private Node merge(List<Node> lists, int lo, int hi) { |
| 7 | if (lo > hi) { |
| 8 | return null; |
| 9 | } |
| 10 | if (lo == hi) { |
| 11 | return lists.get(lo); |
| 12 | } |
| 13 | int mid = lo + (hi - lo) / 2; |
| 14 | Node left = merge(lists, lo, mid); |
| 15 | Node right = merge(lists, mid + 1, hi); |
| 16 | return mergeTwoLists(left, right); |
| 17 | } |
| 18 | |
| 19 | private Node mergeTwoLists(Node list1, Node list2) { |
| 20 | Node dummy = new Node(0); |
| 21 | Node tail = dummy; |
| 22 | while (list1 != null && list2 != null) { |
| 23 | if (list1.val <= list2.val) { |
| 24 | tail.next = list1; |
| 25 | list1 = list1.next; |
| 26 | } else { |
| 27 | tail.next = list2; |
| 28 | list2 = list2.next; |
| 29 | } |
| 30 | tail = tail.next; |
| 31 | } |
| 32 | tail.next = (list1 != null) ? list1 : list2; |
| 33 | return dummy.next; |
| 34 | } |
| 35 | } |
| 36 |
[1,4]
[1,3]
[0]
0
1
2
↑lo
↑hi
Variables
lo
0hi
2CALCULATE
Kick off the recursion: merge the full range of all 3 lists, indices 0 to 2.
Step 1 / 20
Approach & Solutions
Brute Force — Collect Every Value, Sort, Rebuild
GoodWalk every list in turn, copying every value into one array. Sort that array from scratch, then build a brand-new list from it. Correct, but it throws away the fact that each of the k lists was already individually sorted — it re-sorts everything as if the values had arrived in no particular order at all.
Time
O(N log N), where N is the total number of nodes across all k listsSpace
O(N)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node mergeKLists(List<Node> lists) {
9 List<Integer> vals = new ArrayList<>();
10 for (Node head : lists) {
11 Node curr = head;
12 while (curr != null) {
13 vals.add(curr.val);
14 curr = curr.next;
15 }
16 }
17 Collections.sort(vals);
18 Node dummy = new Node(0);
19 Node tail = dummy;
20 for (int v : vals) {
21 tail.next = new Node(v);
22 tail = tail.next;
23 }
24 return dummy.next;
25 }
26}Optimal — Divide and Conquer, Pairwise Merge
OptimalMerging two sorted lists is already solved (see "Merge Two Sorted Linked Lists Into One") — the trick is to reduce k lists down to that. Split the array of lists in half, recursively merge each half down to a single list, then merge those two results together with the same two-pointer splice used for two lists. Halving the problem at every level keeps the total work O(N log k), instead of the O(N·k) that merging the lists one at a time into a growing result would cost.
Time
O(N log k), where N is the total number of nodes and k is the number of listsSpace
O(log k) recursion stackJava
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node mergeKLists(List<Node> lists) {
9 return merge(lists, 0, lists.size() - 1);
10 }
11
12 private Node merge(List<Node> lists, int lo, int hi) {
13 if (lo > hi) {
14 return null;
15 }
16 if (lo == hi) {
17 return lists.get(lo);
18 }
19 int mid = lo + (hi - lo) / 2;
20 Node left = merge(lists, lo, mid);
21 Node right = merge(lists, mid + 1, hi);
22 return mergeTwoLists(left, right);
23 }
24
25 private Node mergeTwoLists(Node list1, Node list2) {
26 Node dummy = new Node(0);
27 Node tail = dummy;
28 while (list1 != null && list2 != null) {
29 if (list1.val <= list2.val) {
30 tail.next = list1;
31 list1 = list1.next;
32 } else {
33 tail.next = list2;
34 list2 = list2.next;
35 }
36 tail = tail.next;
37 }
38 tail.next = (list1 != null) ? list1 : list2;
39 return dummy.next;
40 }
41}