Merge K Sorted Linked Lists

92.2k
0

Given an array lists containing the heads of k singly linked lists, merge every node into one linked list sorted in non-decreasing order. Every input list is already sorted in non-decreasing order. Return the head of the merged list.

Example 1

Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Explanation: The smallest available values appear in the order 1, 1, 2, 3, 4, 4, 5, 6, so the merged linked list follows the same order.

Example 2

Input: lists = []
Output: []
Explanation: An empty collection contains no nodes, so the merged head is empty.

Brute Force Approach

The simplest way is to collect all node values from the k sorted linked lists into one array. Once all values are available together, sorting the array directly gives the final merged order.

After sorting, build a new linked list using these values. This approach is easy to understand, but it does not use the fact that the input lists are already sorted.

Algorithm

  • Create an empty array named values to store all node values.

  • Traverse every linked list and add each node value to values, because every element must appear in the final merged list.

  • Sort values in non-decreasing order so all elements are arranged correctly.

  • Create a dummy node and keep a tail pointer, because this makes building the new list simpler.

  • Traverse the sorted values array:

    • Create a new node for each value.

    • Attach it after tail.

    • Move tail to the newly created node.

  • Return dummy.next because it points to the first node of the merged sorted list.

Dry Run

merge-k-sorted-lists-brute-force

merge-k-sorted-lists-brute-force

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int val;
ListNode* next;
// Creates one linked-list node.
ListNode(int value) {
val = value;
next = nullptr;
}
};
class Solution {
private:
// Builds a linked list from fixed values.
ListNode* buildList(vector<int> values) {
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;
// Append every value in the supplied order.
for (int value : values) {
tail->next = new ListNode(value);
tail = tail->next;
}
return dummy->next;
}
// Prints all values in one linked list.
void printList(ListNode* head) {
ListNode* current = head;
// Print nodes from head to tail.
while (current != nullptr) {
cout << current->val;
current = current->next;
// Add separators only between adjacent values.
if (current != nullptr) {
cout << " ";
}
}
cout << endl;
}
public:
// Merges all lists by sorting every value.
ListNode* mergeKLists(vector<ListNode*>& lists) {
// Store every node value for global sorting.
vector<int> values;
// Visit every list because every node is required.
for (ListNode* head : lists) {
ListNode* current = head;
// Collect values until the current list ends.
while (current != nullptr) {
values.push_back(current->val);
current = current->next;
}
}
// Arrange all collected values in final order.
sort(values.begin(), values.end());
// Use a dummy node to simplify first insertion.
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;
// Build a fresh list from the sorted values.
for (int value : values) {
tail->next = new ListNode(value);
tail = tail->next;
}
// Skip the temporary dummy node in the result.
return dummy->next;
}
// Runs the given example.
void run() {
vector<ListNode*> lists = {
buildList({1, 4, 5}),
buildList({1, 3, 4}),
buildList({2, 6})
};
printList(mergeKLists(lists));
}
};
// Driver code
int main() {
Solution obj;
obj.run();
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), where N is the total number of nodes across all linked lists. Collecting and rebuilding visit all N nodes, while sorting the N collected values dominates the running time.

Space Complexity: O(N), because the values array and the newly created result list require storage proportional to the total number of nodes.

Better Approach

The input lists are already sorted, so sorting all values again wastes useful information. Instead, merge two sorted lists at a time and keep the merged result sorted after every step.

Each merge reuses the existing nodes and needs no extra values array. However, the growing merged list may be traversed again for every new list, so the total work can become large when many lists are present.

Algorithm

  • Initialize merged = null so the first list can become the starting result.

  • Process each linked list one by one and merge it with merged, because both lists are already sorted.

  • For each two-list merge, create a dummy node and a tail pointer to simplify attaching nodes.

  • Compare the current nodes of both lists:

    • Attach the node with the smaller value because it must come next in sorted order.

    • Move only the pointer of the chosen node.

    • Move tail forward after attaching the node.

  • When one list becomes empty, attach the remaining part of the other list because it is already sorted.

  • Update merged with the newly merged list after each step.

  • Return merged after all input lists have been processed.

Dry Run

merge-k-sorted-lists-better

merge-k-sorted-lists-better

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int val;
ListNode* next;
// Creates one linked-list node.
ListNode(int value) {
val = value;
next = nullptr;
}
};
class Solution {
private:
// Merges two sorted linked lists in place.
ListNode* mergeTwo(ListNode* first, ListNode* second) {
// Use a dummy node to simplify first attachment.
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;
// Compare heads while both lists contain nodes.
while (first != nullptr && second != nullptr) {
// Choose first when the first value is smaller.
if (first->val <= second->val) {
tail->next = first;
first = first->next;
} else {
tail->next = second;
second = second->next;
}
tail = tail->next;
}
// Append the sorted suffix still containing nodes.
if (first != nullptr) {
tail->next = first;
} else {
tail->next = second;
}
return dummy->next;
}
// Builds a linked list from fixed values.
ListNode* buildList(vector<int> values) {
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;
// Append every value in the supplied order.
for (int value : values) {
tail->next = new ListNode(value);
tail = tail->next;
}
return dummy->next;
}
// Prints all values in one linked list.
void printList(ListNode* head) {
ListNode* current = head;
// Print nodes from head to tail.
while (current != nullptr) {
cout << current->val;
current = current->next;
// Add separators only between adjacent values.
if (current != nullptr) {
cout << " ";
}
}
cout << endl;
}
public:
// Merges lists from left to right.
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* merged = nullptr;
// Grow one sorted result with each input list.
for (ListNode* head : lists) {
merged = mergeTwo(merged, head);
}
return merged;
}
// Runs the given example.
void run() {
vector<ListNode*> lists = {
buildList({1, 4, 5}),
buildList({1, 3, 4}),
buildList({2, 6})
};
printList(mergeKLists(lists));
}
};
// Driver code
int main() {
Solution obj;
obj.run();
return 0;
}

Complexity Analysis

Time Complexity: O(N × k), a node already present in the growing result can be scanned again during many later merges in the worst case.

Space Complexity: O(1), iterative pointer relinking uses only a dummy node and a few pointers beyond the returned list.

Optimal Approach

Since every linked list is already sorted, the next node in the merged list must be the smallest among the current list heads. A min-heap helps find this node quickly without checking all k lists every time.

Keep only one active node from each list in the heap. After removing the smallest node, add its next node from the same list. This keeps the heap size at most k and builds the merged list in sorted order.

Algorithm

  • Create a min-heap ordered by node value so the smallest current node is always available at the top.

  • Insert the head of every non-empty linked list because each head is the smallest remaining node from that list.

  • Create a dummy node and keep a tail pointer to simplify building the merged list.

  • While the heap is not empty:

    • Remove the smallest node from the heap because it must be the next node in sorted order.

    • Attach this node after tail.

    • Move tail to the attached node.

    • If the removed node has a next node, insert that next node into the heap because it becomes the new candidate from the same list.

  • Return dummy.next because it points to the first node of the completely merged sorted list.

Dry Run

Merge k Sorted List Optimal

Merge k Sorted List Optimal

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int val;
ListNode* next;
// Creates one linked-list node.
ListNode(int value) {
val = value;
next = nullptr;
}
};
class Solution {
private:
class Compare {
public:
// Gives smaller values higher heap priority.
bool operator()(ListNode* first, ListNode* second) {
return first->val > second->val;
}
};
// Builds a linked list from fixed values.
ListNode* buildList(vector<int> values) {
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;
// Append every value in the supplied order.
for (int value : values) {
tail->next = new ListNode(value);
tail = tail->next;
}
return dummy->next;
}
// Prints all values in one linked list.
void printList(ListNode* head) {
ListNode* current = head;
// Print nodes from head to tail.
while (current != nullptr) {
cout << current->val;
current = current->next;
// Add separators only between adjacent values.
if (current != nullptr) {
cout << " ";
}
}
cout << endl;
}
public:
// Merges all lists with a min-heap.
ListNode* mergeKLists(vector<ListNode*>& lists) {
// Keep one active node from each non-empty list.
priority_queue<
ListNode*, vector<ListNode*>, Compare
> minHeap;
// Insert every available list head as a candidate.
for (ListNode* head : lists) {
// Empty lists provide no heap candidate.
if (head != nullptr) {
minHeap.push(head);
}
}
// Use a dummy node to simplify first attachment.
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;
// Extract the smallest remaining candidate.
while (!minHeap.empty()) {
ListNode* smallest = minHeap.top();
minHeap.pop();
tail->next = smallest;
tail = tail->next;
// Add the next candidate from the same list.
if (smallest->next != nullptr) {
minHeap.push(smallest->next);
}
}
// End the result after the final selected node.
tail->next = nullptr;
return dummy->next;
}
// Runs the given example.
void run() {
vector<ListNode*> lists = {
buildList({1, 4, 5}),
buildList({1, 3, 4}),
buildList({2, 6})
};
printList(mergeKLists(lists));
}
};
// Driver code
int main() {
Solution obj;
obj.run();
return 0;
}

Complexity Analysis

Time Complexity: O(N log k), every node enters and leaves a heap containing at most k active nodes once.

Space Complexity: O(k), the min-heap stores at most one active node from each input list.

Interview follow-up Questions

Yes. Every node must remain in the result, so equal values from different lists appear as separate nodes.

Heap

Read Similar Blogs

Heap

Find K Pairs with Smallest Sums

Given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k , form every index-pair [firstIndex, secondIndex] . The sum of an index-pair is nums1[firstIndex] + nums2[se...

61.1k
Heap

Introduction to Heap

Imagine an emergency room with several waiting patients. The patient needing the most urgent care is treated first, even if another patient arrived earlier. The next choice depends on priority, not...

72.8k
Heap

Meeting Rooms II

Given an array intervals , where every entry [start, end] represents one meeting, find the minimum number of conference rooms needed to hold every meeting without a scheduling conflict. An end time...

57.7k
Comments0