Language Selection
Choose your preferred programming language
Showing: Python
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.
Input/Output Specifications
- Input: Array of k sorted linked lists
- Output: Single merged sorted linked list
- 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
Examples
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
Solutions
Approach 1: Divide and Conquer
This approach recursively merges pairs of lists until only one list remains.
Algorithm:
- Base case: if k <= 1, return the single list or null
- Recursively merge the first half and second half of lists
- Merge the two resulting lists
- Return the merged result
Python:
def mergeKLists(lists):
"""
Merge k sorted linked lists using divide and conquer
Time: O(n log k)
Space: O(log k) - recursion stack
"""
if not lists:
return None
def mergeTwoLists(l1, l2):
"""Helper function to merge two sorted lists"""
dummy = ListNode(0)
current = dummy
while l1 and 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 if l1 else l2
return dummy.next
def mergeKListsHelper(lists, start, end):
if start == end:
return lists[start]
mid = (start + end) // 2
left = mergeKListsHelper(lists, start, mid)
right = mergeKListsHelper(lists, mid + 1, end)
return mergeTwoLists(left, right)
return mergeKListsHelper(lists, 0, len(lists) - 1)
Java:
class Solution {
/**
* Merge k sorted linked lists using divide and conquer
* Time: O(n log k)
* Space: O(log k) - recursion stack
*/
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
return mergeKListsHelper(lists, 0, lists.length - 1);
}
private ListNode mergeKListsHelper(ListNode[] lists, int start, int end) {
if (start == end) {
return lists[start];
}
int mid = (start + end) / 2;
ListNode left = mergeKListsHelper(lists, start, mid);
ListNode right = mergeKListsHelper(lists, mid + 1, end);
return mergeTwoLists(left, right);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
Go:
// mergeKLists - Merge k sorted linked lists using divide and conquer
// Time: O(n log k)
// Space: O(log k) - recursion stack
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
return mergeKListsHelper(lists, 0, len(lists)-1)
}
func mergeKListsHelper(lists []*ListNode, start, end int) *ListNode {
if start == end {
return lists[start]
}
mid := (start + end) / 2
left := mergeKListsHelper(lists, start, mid)
right := mergeKListsHelper(lists, mid+1, end)
return mergeTwoLists(left, right)
}
func mergeTwoLists(l1, l2 *ListNode) *ListNode {
dummy := &ListNode{Val: 0}
current := dummy
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
current.Next = l1
l1 = l1.Next
} else {
current.Next = l2
l2 = l2.Next
}
current = current.Next
}
if l1 != nil {
current.Next = l1
} else {
current.Next = l2
}
return dummy.Next
}
JavaScript:
/**
* Merge k sorted linked lists using divide and conquer
* Time: O(n log k)
* Space: O(log k) - recursion stack
*/
function mergeKLists(lists) {
if (!lists || lists.length === 0) {
return null;
}
return mergeKListsHelper(lists, 0, lists.length - 1);
}
function mergeKListsHelper(lists, start, end) {
if (start === end) {
return lists[start];
}
const mid = Math.floor((start + end) / 2);
const left = mergeKListsHelper(lists, start, mid);
const right = mergeKListsHelper(lists, mid + 1, end);
return mergeTwoLists(left, right);
}
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
while (l1 !== null && l2 !== null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 !== null ? l1 : l2;
return dummy.next;
}
C#:
public class Solution {
/// <summary>
/// Merge k sorted linked lists using divide and conquer
/// Time: O(n log k)
/// Space: O(log k) - recursion stack
/// </summary>
public ListNode MergeKLists(ListNode[] lists) {
if (lists == null || lists.Length == 0) {
return null;
}
return MergeKListsHelper(lists, 0, lists.Length - 1);
}
private ListNode MergeKListsHelper(ListNode[] lists, int start, int end) {
if (start == end) {
return lists[start];
}
int mid = (start + end) / 2;
ListNode left = MergeKListsHelper(lists, start, mid);
ListNode right = MergeKListsHelper(lists, mid + 1, end);
return MergeTwoLists(left, right);
}
private ListNode MergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
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;
}
}
Approach 2: Priority Queue (Min Heap)
This approach uses a priority queue to always get the smallest element from all lists.
Algorithm:
- Add the head of each non-empty list to the priority queue
- While the queue is not empty:
- Extract the minimum element
- Add it to the result list
- Add the next element from the same list to the queue
- Return the result list
Python:
def mergeKListsPriorityQueue(lists):
"""
Merge k sorted linked lists using priority queue
Time: O(n log k)
Space: O(k)
"""
import heapq
if not lists:
return None
# Create priority queue with (value, list_index, node)
pq = []
# Add head of each non-empty list to priority queue
for i, head in enumerate(lists):
if head:
heapq.heappush(pq, (head.val, i, head))
dummy = ListNode(0)
current = dummy
while pq:
val, list_idx, node = heapq.heappop(pq)
# Add node to result
current.next = node
current = current.next
# Add next node from the same list
if node.next:
heapq.heappush(pq, (node.next.val, list_idx, node.next))
return dummy.next
Java:
class Solution {
/**
* Merge k sorted linked lists using priority queue
* Time: O(n log k)
* Space: O(k)
*/
public ListNode mergeKListsPriorityQueue(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
// Add head of each non-empty list to priority queue
for (ListNode head : lists) {
if (head != null) {
pq.offer(head);
}
}
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
// Add node to result
current.next = node;
current = current.next;
// Add next node from the same list
if (node.next != null) {
pq.offer(node.next);
}
}
return dummy.next;
}
}
Go:
// mergeKListsPriorityQueue - Merge k sorted linked lists using priority queue
// Time: O(n log k)
// Space: O(k)
func mergeKListsPriorityQueue(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
// Create priority queue
pq := make(PriorityQueue, 0)
heap.Init(&pq)
// Add head of each non-empty list to priority queue
for _, head := range lists {
if head != nil {
heap.Push(&pq, head)
}
}
dummy := &ListNode{Val: 0}
current := dummy
for pq.Len() > 0 {
node := heap.Pop(&pq).(*ListNode)
// Add node to result
current.Next = node
current = current.Next
// Add next node from the same list
if node.Next != nil {
heap.Push(&pq, node.Next)
}
}
return dummy.Next
}
// PriorityQueue implementation for Go
type PriorityQueue []*ListNode
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].Val < pq[j].Val
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
*pq = append(*pq, x.(*ListNode))
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}
JavaScript:
/**
* Merge k sorted linked lists using priority queue
* Time: O(n log k)
* Space: O(k)
*/
function mergeKListsPriorityQueue(lists) {
if (!lists || lists.length === 0) {
return null;
}
// Create priority queue (min heap)
const pq = new MinHeap();
// Add head of each non-empty list to priority queue
for (const head of lists) {
if (head !== null) {
pq.insert(head);
}
}
const dummy = new ListNode(0);
let current = dummy;
while (!pq.isEmpty()) {
const node = pq.extractMin();
// Add node to result
current.next = node;
current = current.next;
// Add next node from the same list
if (node.next !== null) {
pq.insert(node.next);
}
}
return dummy.next;
}
// MinHeap implementation for JavaScript
class MinHeap {
constructor() {
this.heap = [];
}
insert(node) {
this.heap.push(node);
this.heapifyUp(this.heap.length - 1);
}
extractMin() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.heapifyDown(0);
return min;
}
isEmpty() {
return this.heap.length === 0;
}
heapifyUp(index) {
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[parentIndex].val <= this.heap[index].val) break;
[this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
index = parentIndex;
}
}
heapifyDown(index) {
while (true) {
let smallest = index;
const leftChild = 2 * index + 1;
const rightChild = 2 * index + 2;
if (leftChild < this.heap.length && this.heap[leftChild].val < this.heap[smallest].val) {
smallest = leftChild;
}
if (rightChild < this.heap.length && this.heap[rightChild].val < this.heap[smallest].val) {
smallest = rightChild;
}
if (smallest === index) break;
[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
index = smallest;
}
}
}
C#:
public class Solution {
/// <summary>
/// Merge k sorted linked lists using priority queue
/// Time: O(n log k)
/// Space: O(k)
/// </summary>
public ListNode MergeKListsPriorityQueue(ListNode[] lists) {
if (lists == null || lists.Length == 0) {
return null;
}
var pq = new PriorityQueue<ListNode, int>();
// Add head of each non-empty list to priority queue
foreach (var head in lists) {
if (head != null) {
pq.Enqueue(head, head.val);
}
}
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (pq.Count > 0) {
ListNode node = pq.Dequeue();
// Add node to result
current.next = node;
current = current.next;
// Add next node from the same list
if (node.next != null) {
pq.Enqueue(node.next, node.next.val);
}
}
return dummy.next;
}
}
Key Insights
- Divide and conquer: Recursively merge pairs of lists
- Priority queue: Always get the smallest element from all lists
- Time complexity: O(n log k) where n is total number of nodes
- Space complexity: O(log k) for divide-conquer, O(k) for priority queue
- Optimal approach: Divide and conquer is generally preferred for space efficiency
Edge Cases
- Empty array of lists
- Array with empty lists
- Single list
- Two lists
- Very large number of lists
Test Cases
# Test case 1: Normal case
lists1 = [
ListNode(1, ListNode(4, ListNode(5))),
ListNode(1, ListNode(3, ListNode(4))),
ListNode(2, ListNode(6))
]
# Expected: [1,1,2,3,4,4,5,6]
# Test case 2: Empty array
lists2 = []
# Expected: None
# Test case 3: Array with empty lists
lists3 = [None, None]
# Expected: None
# Test case 4: Single list
lists4 = [ListNode(1, ListNode(2, ListNode(3)))]
# Expected: [1,2,3]
Follow-up Questions
- How would you handle very large lists?
- Can you solve this with O(1) space?
- How would you handle lists of different lengths?
- What if the lists are not sorted?
Common Mistakes
- Not handling empty lists properly
- Incorrect priority queue implementation
- Not maintaining the correct order in divide-conquer
- Memory leaks when not properly managing pointers
- Off-by-one errors in array indexing
- Not handling the case where all lists are empty