🌟 Introduction
Merging multiple sorted linked lists is a very popular problem in data structures and algorithms. If you have several lists where each one is already sorted, the goal is to merge them into one single sorted linked list while keeping the order intact. This problem is common in coding interviews, competitive programming, and real-world applications like combining search results or merging logs in large systems.
In this article, we’ll explore different ways to merge k sorted linked lists. We will explain each method step by step, share examples, discuss its advantages and disadvantages, and finally identify the most efficient solution.
🧮 Method 1. Brute Force (Concatenate and Sort)
How It Works
This is the simplest method. You take all the elements from all k linked lists, put them into one array, sort the array, and then create a new linked list from the sorted elements.
Example
Suppose you have three linked lists:
List1: 1 → 4 → 5
List2: 1 → 3 → 4
List3: 2 → 6
First, combine them into one array → [1, 4, 5, 1, 3, 4, 2, 6].
Then, sort the array → [1, 1, 2, 3, 4, 4, 5, 6].
Finally, build a new linked list → 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6 ✅
Pros and Cons
✅ Very easy to implement and understand.
❌ Sorting the entire array is time-consuming → O(N log N) where N is the total number of elements.
This method is fine for small datasets but inefficient for larger ones.
🏗️ Method 2/.Compare One by One
How It Works
In this method, you maintain pointers for each linked list. At each step, you compare the first (head) elements of all lists and pick the smallest one to add to the result. You then move the pointer forward in that list.
Example
For lists: (1, 1, 2), the smallest is 1. Add 1 to the result. Next comparison: (4, 1, 2) → pick 1 again. Continue until all lists are empty.
Pros and Cons
✅ No need for extra memory apart from the new linked list.
❌ Very slow if k is large because you compare across all k lists every time.
Time Complexity = O(kN), which becomes inefficient when k is big.
This method is okay when k is very small, but not practical for larger values of k.
⚡ Method 3. Using a Min-Heap (Most Efficient in Practice)
How It Works
A Min-Heap (priority queue) is a data structure that helps you quickly find the smallest element. By using a heap, you can efficiently merge the lists.
Insert the first node (head) of each list into the Min-Heap.
Remove the smallest element from the heap and add it to the merged result.
If the removed element has a next node, insert it into the heap.
Keep repeating until the heap is empty.
Example
For the three lists:
List1: 1 → 4 → 5
List2: 1 → 3 → 4
List3: 2 → 6
Start with heap = [1, 1, 2].
Extract 1 → result = [1], insert 4 → heap = [1, 2, 4].
Extract 1 → result = [1, 1], insert 3 → heap = [2, 4, 3].
Continue until heap is empty.
Final result = 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6 ✅
Pros and Cons
✅ Very efficient for large k.
✅ Time Complexity = O(N log k).
✅ Widely used in coding interview solutions and practical systems.
❌ Requires extra memory for the heap (O(k)).
Join the conversation! Your thoughts help the community grow.