Merge k Sorted Lists solution and explanation
Deloitte
9 more videos on this problem
Merge K Sorted Lists - Leetcode 23 - PythonNeetCode · 10:34 · 306K views
L25. Merge K Sorted Lists | Multiple Approachestake U forward · 30:02 · 147K views
Merge K sorted lists | Leetcode #23Techdose · 22:21 · 84K views
Merge k Sorted Lists - (Leetcode - 23) - (Google, Amazon, Microsoft..) : Explanation ➕ Live CodingcodestorywithMIK · 26:58 · 31K views
Merge K Sorted Linked Lists - Leetcode 23 - Heaps (Python)Greg Hogg · 10:07 · 20K views
Merge k Sorted Lists | Live Coding with Explanation | Leetcode - 23Algorithms Made Easy · 8:08 · 19K views
MERGE K SORTED LISTS | LEETCODE 23 | PYTHON OPTIMAL SOLUTIOCracking FAANG · 19:33 · 6K views
Merge k Sorted Lists - LeetCode #23 with python programmingCodingNinja · 9:24 · 6K views
LeetCode 23: Merge k Sorted Lists - Interview Prep Ep 26Fisher Coder · 25:03 · 5K views
Merge k Sorted Lists | LeetCode 23 | C++Knowledge Center · 15:48 · 5K views
The problem
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.
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: []
Example 3:
Input: lists = [[]] Output: []
Constraints:
k == lists.length0 <= k <= 1040 <= lists[i].length <= 500-104 <= lists[i][j] <= 104lists[i]is sorted in ascending order.- The sum of
lists[i].lengthwill not exceed104.
Approach overview
Problem Overview: You receive k sorted linked lists and must merge them into one sorted linked list. The final list must preserve sorted order while efficiently handling all nodes across the input lists.
Approach 1: Sequential Merge (O(Nk) time, O(1) space)
The simplest idea merges lists one at a time. Start with the first list, merge it with the second, then merge the result with the third, and continue until all lists are processed. Each merge operation works like the classic merge step in merge sort, comparing node values and appending the smaller one to the result. The problem is repeated work: nodes from earlier lists get compared again every time a new list is merged. With N total nodes and k lists, the overall cost grows to O(Nk). This approach is easy to implement but inefficient when k is large.
Approach 2: Merge Using a Min-Heap (O(N log k) time, O(k) space)
A more scalable solution keeps track of the smallest current node across all lists using a min-heap. Push the head of every list into a heap keyed by node value. Repeatedly extract the smallest node, append it to the result list, and insert the next node from the same list into the heap. The heap size never exceeds k, so each push or pop costs O(log k). Since every one of the N nodes is inserted and removed exactly once, the total complexity becomes O(N log k) with O(k) extra space. This approach heavily relies on the heap (priority queue) data structure to efficiently track the smallest candidate node.
Approach 3: Divide and Conquer (O(N log k) time, O(log k) space)
This method applies the same strategy used by divide and conquer algorithms. Pair up lists and merge them in parallel: first merge list 1 with list 2, list 3 with list 4, and so on. After one pass, the number of lists halves. Repeat the process until only one list remains. Each level processes all N nodes, and there are log k levels of merging, leading to O(N log k) time complexity. Space usage is O(log k) if implemented recursively due to the call stack. The benefit is that each node participates in far fewer comparisons than in the sequential merge approach.
Recommended for interviews: The min-heap solution is the most commonly expected answer because it demonstrates knowledge of priority queues and efficient multi-way merging. The divide and conquer approach is equally optimal and often preferred when interviewers want to test algorithmic reasoning around recursive merging. Showing the sequential merge idea first demonstrates baseline understanding, while moving to the O(N log k) strategies shows strong optimization skills.
Approach 1: Merge Using a Min-Heap
This approach utilizes a min-heap (priority queue) to efficiently merge k sorted linked lists. The heap will help us identify the minimum element among the lists efficiently.
- Initial step involves inserting the head of each list into the min-heap.
- Then, continuously extract the smallest element from the min-heap and append it to the merged list.
- If there’s a next element in the list from which the node was extracted, push that into the min-heap.
This ensures that the smallest elements are appended to the resulting list in sorted order.
import heapq
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
# For min-heap comparison
def __lt__(self, other):
return self.val < other.val
class Solution:
def mergeKLists(self, lists):
if not lists or len(lists) == 0:
return None
heap = []
for l in lists:
if l:
heapq.heappush(heap, l)
dummy = ListNode(0)
current = dummy
while heap:
node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, node.next)
return dummy.nextimport java.util.PriorityQueue;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);
ListNode dummy = new ListNode(0);
ListNode current = dummy;
for (ListNode l : lists) {
if (l != null) {
queue.add(l);
}
}
while (!queue.isEmpty()) {
ListNode node = queue.poll();
current.next = node;
current = current.next;
if (node.next != null) {
queue.add(node.next);
}
}
return dummy.next;
}
}The Python solution uses the built-in heapq module which provides an efficient priority queue implementation. Each ListNode is wrapped so that it is comparable based on its val, allowing the heap operations to work correctly. The solution maintains a heap of size k, thus ensuring efficient merging.
Time Complexity: O(N log k), where N is the total number of nodes and k is the number of linked lists. Each insertion and extraction from the heap takes log k time, and there are N nodes in total.
Space Complexity: O(k), due to the heap that at most stores one node from each list.
Approach 2: Divide and Conquer
This approach follows the divide-and-conquer methodology to merge the lists incrementally.
- Recursively divide the array of lists into two halves until you have single lists to merge.
- Then, merge the two halves by recursively calling and merging further down the line, akin to a merge sort process.
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return nullptr;
return mergeKLists(lists, 0, lists.size() - 1);
}
private:
ListNode* mergeKLists(vector<ListNode*>& lists, int left, int right) {
if (left == right) return lists[left];
int mid = (right + left) / 2;
ListNode* l1 = mergeKLists(lists, left, mid);
ListNode* l2 = mergeKLists(lists, mid + 1, right);
return mergeTwoLists(l1, l2);
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* last = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
last->next = l1;
l1 = l1->next;
} else {
last->next = l2;
l2 = l2->next;
}
last = last->next;
}
last->next = l1 ? l1 : l2;
return dummy.next;
}
};function ListNode(val) {
this.val = val;
this.next = null;
}
var mergeKLists = function(lists) {
if (!lists.length) return null;
return partition(lists, 0, lists.length - 1);
};
function partition(lists, start, end) {
if (start === end) return lists[start];
const mid = Math.floor((start + end) / 2);
const left = partition(lists, start, mid);
const right = partition(lists, mid + 1, end);
return mergeTwoLists(left, right);
}
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
while (l1 && l2) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 || l2;
return dummy.next;
}The C++ solution uses a divide-and-conquer strategy to break down the problem into smaller instances, which are solved recursively. The two halves of the list array are merged progressively, much like the merge step in merge sort.
Time Complexity: O(N log k), where N is the total number of nodes and k is the number of lists.
Space Complexity: O(log k) for recursion stack space.
Approach 3: 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.
The time complexity is O(n times log k), and the space complexity is O(k). Here, n is the total number of all linked list nodes, and k is the number of linked lists given in the problem.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
const pq = new PriorityQueue<ListNode>((a, b) => a.val - b.val);
lists.filter(head => head).forEach(head => pq.enqueue(head));
const dummy: ListNode = new ListNode();
let cur: ListNode = dummy;
while (!pq.isEmpty()) {
const node = pq.dequeue();
cur.next = node;
cur = cur.next;
if (node.next) {
pq.enqueue(node.next);
}
}
return dummy.next;
}/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode MergeKLists(ListNode[] lists) {
PriorityQueue<ListNode, int> pq = new PriorityQueue<ListNode, int>();
foreach (var head in lists) {
if (head != null) {
pq.Enqueue(head, head.val);
}
}
var dummy = new ListNode();
var cur = dummy;
while (pq.Count > 0) {
var node = pq.Dequeue();
cur.next = node;
cur = cur.next;
if (node.next != null) {
pq.Enqueue(node.next, node.next.val);
}
}
return dummy.next;
}
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
pq := hp{}
for _, head := range lists {
if head != nil {
pq = append(pq, head)
}
}
heap.Init(&pq)
dummy := &ListNode{}
cur := dummy
for len(pq) > 0 {
cur.Next = heap.Pop(&pq).(*ListNode)
cur = cur.Next
if cur.Next != nil {
heap.Push(&pq, cur.Next)
}
}
return dummy.Next
}
type hp []*ListNode
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(*ListNode)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
use std::cmp::Ordering;
use std::collections::BinaryHeap;
impl PartialOrd for ListNode {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for ListNode {
fn cmp(&self, other: &Self) -> Ordering {
self.val.cmp(&other.val).reverse()
}
}
impl Solution {
pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
let mut pq = lists
.into_iter()
.filter_map(|head| head)
.collect::<BinaryHeap<_>>();
let mut head = None;
let mut cur = &mut head;
while let Some(node) = pq.pop() {
cur = &mut cur.insert(Box::new(ListNode::new(node.val))).next;
if let Some(next) = node.next {
pq.push(next);
}
}
head
}
}# Definition for singly-linked list.
class ListNode {
public $val;
public $next;
public function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
class Solution {
/**
* @param ListNode[] $lists
* @return ListNode
*/
function mergeKLists($lists) {
$numLists = count($lists);
if ($numLists === 0) {
return null;
}
while ($numLists > 1) {
$mid = intval($numLists / 2);
for ($i = 0; $i < $mid; $i++) {
$lists[$i] = $this->mergeTwoLists($lists[$i], $lists[$numLists - $i - 1]);
}
$numLists = intval(($numLists + 1) / 2);
}
return $lists[0];
}
function mergeTwoLists($list1, $list2) {
$dummy = new ListNode(0);
$current = $dummy;
while ($list1 != null && $list2 != null) {
if ($list1->val <= $list2->val) {
$current->next = $list1;
$list1 = $list1->next;
} else {
$current->next = $list2;
$list2 = $list2->next;
}
$current = $current->next;
}
if ($list1 != null) {
$current->next = $list1;
} elseif ($list2 != null) {
$current->next = $list2;
}
return $dummy->next;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Merge Using a Min-Heap | Time Complexity: O(N log k), where N is the total number of nodes and k is the number of linked lists. Each insertion and extraction from the heap takes log k time, and there are N nodes in total. |
| Divide and Conquer | Time Complexity: O(N log k), where N is the total number of nodes and k is the number of lists. |
| Priority Queue (Min Heap) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sequential Merge | O(Nk) | O(1) | Simple baseline solution or when k is very small |
| Min-Heap (Priority Queue) | O(N log k) | O(k) | Best general solution when merging many sorted lists |
| Divide and Conquer | O(N log k) | O(log k) | Efficient when recursion or pairwise merging is preferred |
Frequently asked questions
Is Merge k Sorted Lists easy or hard?
Merge k Sorted Lists is classified as a hard problem because it combines linked list manipulation with advanced algorithm design. Efficient solutions require understanding heaps or divide and conquer techniques to achieve O(N log k) performance.
Merge k Sorted Lists Python/Java solution
Python typically uses the heapq module to implement the min-heap, while Java uses PriorityQueue. Both implementations push the head nodes of each list, repeatedly extract the smallest value, and append it to the result list.
How to solve Merge k Sorted Lists in O(N log k)?
Use either a priority queue or a divide and conquer strategy. The heap approach always extracts the smallest node among the current list heads in O(log k) time. Since every node is processed once, the total runtime becomes O(N log k).
What is the best approach for Merge k Sorted Lists?
The most practical approach uses a min-heap (priority queue). Insert the head node of each of the k lists into the heap, repeatedly extract the smallest node, and push its next node. This keeps the heap size at most k and processes all N nodes in O(N log k) time with O(k) extra space.
Is Merge k Sorted Lists asked at Google/Amazon/Meta?
Merge k Sorted Lists appears frequently in interviews at companies like Google, Amazon, Meta, and Microsoft. It tests understanding of linked lists, heaps, and efficient multi-way merging techniques.
What data structure is used in Merge k Sorted Lists?
The most common data structure used is a min-heap (priority queue) to track the smallest node among the k lists. Linked list pointers are used to build the final merged list as nodes are extracted from the heap.
What is the time complexity of Merge k Sorted Lists?
The optimal solutions run in O(N log k) time where N is the total number of nodes across all lists and k is the number of lists. Both the min-heap approach and the divide and conquer merging strategy achieve this complexity.