Merge K Sorted Lists

🎯

Merge K Sorted Lists

hardLINKED_LISTAmazonFacebookGoogle

Imagine you have multiple sorted streams of data coming from different sensors, and you want to combine them into one sorted stream efficiently.

💡 This problem involves merging multiple sorted linked lists into one sorted list. Beginners often struggle because merging two lists is straightforward, but merging k lists efficiently requires understanding of advanced data structures or divide and conquer techniques.

📋

Problem Statement

Given an array of k linked-lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] is sorted in ascending orderThe sum of lists[i].length won't exceed 10^5

💡

Example

Input"[[1->4->5],[1->3->4],[2->6]]"

Output1->1->2->3->4->4->5->6

Merging the three sorted lists results in one sorted list.

• Empty list array → return null
• All lists empty → return null
• Lists with one element each → merge correctly
• Lists with duplicate values → maintain duplicates in output

⚠️

Common Mistakes

Not handling empty lists or null heads

Null pointer exceptions or incorrect output

✅ Check for null before processing each list

Not defining comparison for ListNode in heap

Heap operations fail or runtime errors

✅ Implement __lt__ in Python or use comparator in Java/C++

Merging lists sequentially without updating merged list properly

Lost nodes or incorrect merges

✅ Always assign merged result back to merged variable

Forgetting to attach leftover nodes after merging two lists

Partial merges, missing nodes in output

✅ Attach remaining nodes after one list ends

Using sorting approach for very large inputs

Time limit exceeded or memory issues

✅ Use min-heap or divide and conquer approach

🧠

Brute Force (Collect & Sort All Nodes)

💡 This approach exists to build intuition by simplifying the problem to sorting all elements at once, ignoring the linked list structure initially.

Intuition

Extract all nodes from the k lists into an array, sort the array, then rebuild a sorted linked list from the sorted values.

Algorithm

1. Traverse each linked list and collect all node values into an array.
2. Sort the array of values.
3. Create a new linked list by iterating over the sorted array.
4. Return the head of the newly created sorted linked list.

💡 This approach is straightforward but inefficient because it ignores the sorted nature of input lists and uses extra space.

</>

Code

from typing import List, Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    nodes = []
    for head in lists:
        while head:
            nodes.append(head.val)
            head = head.next
    nodes.sort()
    dummy = ListNode(0)
    current = dummy
    for val in nodes:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

# Driver code to test
if __name__ == '__main__':
    # Helper to create linked list from list
    def create_list(arr):
        dummy = ListNode(0)
        cur = dummy
        for v in arr:
            cur.next = ListNode(v)
            cur = cur.next
        return dummy.next

    lists = [create_list([1,4,5]), create_list([1,3,4]), create_list([2,6])]
    merged = mergeKLists(lists)
    # Print merged list
    while merged:
        print(merged.val, end='->' if merged.next else '')
        merged = merged.next

Line Notes

nodes = []Initialize list to collect all node values

for head in lists:Iterate over each linked list head

while head:Traverse each linked list fully

nodes.append(head.val)Collect node values for sorting

nodes.sort()Sort all collected values to get global order

dummy = ListNode(0)Create dummy node to simplify list construction

for val in nodes:Rebuild linked list from sorted values

return dummy.nextReturn head of merged sorted list

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> nodes = new ArrayList<>();
        for (ListNode head : lists) {
            while (head != null) {
                nodes.add(head.val);
                head = head.next;
            }
        }
        Collections.sort(nodes);
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (int val : nodes) {
            current.next = new ListNode(val);
            current = current.next;
        }
        return dummy.next;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode l1 = createList(new int[]{1,4,5});
        ListNode l2 = createList(new int[]{1,3,4});
        ListNode l3 = createList(new int[]{2,6});
        ListNode[] lists = new ListNode[]{l1, l2, l3};
        ListNode merged = sol.mergeKLists(lists);
        printList(merged);
    }

    static ListNode createList(int[] arr) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int v : arr) {
            cur.next = new ListNode(v);
            cur = cur.next;
        }
        return dummy.next;
    }

    static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print("->");
            head = head.next;
        }
        System.out.println();
    }
}

Line Notes

List<Integer> nodes = new ArrayList<>();Collect all node values in a list

for (ListNode head : lists)Iterate over each linked list

while (head != null)Traverse each linked list fully

nodes.add(head.val);Add node values for sorting

Collections.sort(nodes);Sort all values to merge

ListNode dummy = new ListNode(0);Dummy node to simplify list building

for (int val : nodes)Rebuild merged list from sorted values

return dummy.next;Return head of merged list

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<int> nodes;
        for (auto head : lists) {
            while (head) {
                nodes.push_back(head->val);
                head = head->next;
            }
        }
        sort(nodes.begin(), nodes.end());
        ListNode dummy(0);
        ListNode* current = &dummy;
        for (int val : nodes) {
            current->next = new ListNode(val);
            current = current->next;
        }
        return dummy.next;
    }
};

// Helper functions for testing
ListNode* createList(const vector<int>& arr) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int v : arr) {
        cur->next = new ListNode(v);
        cur = cur->next;
    }
    return dummy.next;
}

void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << "->";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Solution sol;
    vector<ListNode*> lists = {createList({1,4,5}), createList({1,3,4}), createList({2,6})};
    ListNode* merged = sol.mergeKLists(lists);
    printList(merged);
    return 0;
}

Line Notes

vector<int> nodes;Store all node values from lists

for (auto head : lists)Iterate over each linked list head

while (head)Traverse each linked list fully

nodes.push_back(head->val);Collect node values for sorting

sort(nodes.begin(), nodes.end());Sort all collected values

ListNode dummy(0);Dummy node to simplify list construction

for (int val : nodes)Rebuild linked list from sorted values

return dummy.next;Return head of merged sorted list

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function mergeKLists(lists) {
    const nodes = [];
    for (const head of lists) {
        let current = head;
        while (current) {
            nodes.push(current.val);
            current = current.next;
        }
    }
    nodes.sort((a, b) => a - b);
    const dummy = new ListNode(0);
    let current = dummy;
    for (const val of nodes) {
        current.next = new ListNode(val);
        current = current.next;
    }
    return dummy.next;
}

// Driver code
function createList(arr) {
    const dummy = new ListNode(0);
    let cur = dummy;
    for (const v of arr) {
        cur.next = new ListNode(v);
        cur = cur.next;
    }
    return dummy.next;
}

const lists = [createList([1,4,5]), createList([1,3,4]), createList([2,6])];
const merged = mergeKLists(lists);
let cur = merged;
let output = '';
while (cur) {
    output += cur.val + (cur.next ? '->' : '');
    cur = cur.next;
}
console.log(output);

Line Notes

const nodes = [];Array to collect all node values

for (const head of lists)Iterate over each linked list

while (current)Traverse each linked list fully

nodes.push(current.val);Collect node values for sorting

nodes.sort((a, b) => a - b);Sort all values numerically

const dummy = new ListNode(0);Dummy node to simplify list building

for (const val of nodes)Rebuild merged list from sorted values

return dummy.next;Return head of merged sorted list

⏱

Complexity

TimeO(N log N) where N is total number of nodes

SpaceO(N) for storing all node values

We collect all nodes (N total), then sort them which takes O(N log N), then rebuild the list in O(N).

💡 For example, if total nodes are 1000, sorting takes roughly 1000*log2(1000) ≈ 10,000 operations.

Interview Verdict: Accepted but inefficient for large k or large total nodes

This approach works but is slow and uses extra memory, so it's good to mention but not to implement in interviews.

🧠

Better (Merge Lists One by One)

💡 This approach improves on brute force by merging two lists at a time, leveraging the sorted property to avoid sorting all nodes at once.

Intuition

Iteratively merge the first two lists, then merge the result with the third, and so on until all lists are merged.

Algorithm

1. Define a helper function to merge two sorted linked lists.
2. Initialize merged list as null.
3. Iterate over each list and merge it with the current merged list.
4. Return the final merged list.

💡 This approach is easier to implement than optimal but can be slow if k is large because merges happen sequentially.

</>

Code

from typing import List, Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    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 mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    merged = None
    for l in lists:
        merged = mergeTwoLists(merged, l)
    return merged

# Driver code
if __name__ == '__main__':
    def create_list(arr):
        dummy = ListNode(0)
        cur = dummy
        for v in arr:
            cur.next = ListNode(v)
            cur = cur.next
        return dummy.next

    lists = [create_list([1,4,5]), create_list([1,3,4]), create_list([2,6])]
    merged = mergeKLists(lists)
    while merged:
        print(merged.val, end='->' if merged.next else '')
        merged = merged.next

Line Notes

def mergeTwoLists(l1: Optional[ListNode], l2: Optional[ListNode])Helper to merge two sorted lists efficiently

while l1 and l2:Traverse both lists until one is exhausted

if l1.val < l2.val:Pick smaller node to maintain sorted order

current.next = l1Link smaller node to merged list

current.next = l1 if l1 else l2Attach remaining nodes after one list ends

merged = NoneStart with empty merged list

for l in lists:Iteratively merge each list into merged

merged = mergeTwoLists(merged, l)Update merged list after each merge

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public 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;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode merged = null;
        for (ListNode l : lists) {
            merged = mergeTwoLists(merged, l);
        }
        return merged;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode l1 = createList(new int[]{1,4,5});
        ListNode l2 = createList(new int[]{1,3,4});
        ListNode l3 = createList(new int[]{2,6});
        ListNode[] lists = new ListNode[]{l1, l2, l3};
        ListNode merged = sol.mergeKLists(lists);
        printList(merged);
    }

    static ListNode createList(int[] arr) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int v : arr) {
            cur.next = new ListNode(v);
            cur = cur.next;
        }
        return dummy.next;
    }

    static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print("->");
            head = head.next;
        }
        System.out.println();
    }
}

Line Notes

public ListNode mergeTwoLists(ListNode l1, ListNode l2)Helper merges two sorted lists efficiently

while (l1 != null && l2 != null)Traverse both lists until one ends

if (l1.val < l2.val)Choose smaller node to maintain order

current.next = (l1 != null) ? l1 : l2;Attach leftover nodes after one list ends

ListNode merged = null;Initialize merged list as empty

for (ListNode l : lists)Iterate over all lists to merge

merged = mergeTwoLists(merged, l);Update merged list after each merge

return merged;Return fully merged list

#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* 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 ? l1 : l2;
        return dummy.next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* merged = nullptr;
        for (auto l : lists) {
            merged = mergeTwoLists(merged, l);
        }
        return merged;
    }
};

// Helper functions
ListNode* createList(const vector<int>& arr) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int v : arr) {
        cur->next = new ListNode(v);
        cur = cur->next;
    }
    return dummy.next;
}

void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << "->";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Solution sol;
    vector<ListNode*> lists = {createList({1,4,5}), createList({1,3,4}), createList({2,6})};
    ListNode* merged = sol.mergeKLists(lists);
    printList(merged);
    return 0;
}

Line Notes

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)Helper merges two sorted lists efficiently

while (l1 && l2)Traverse both lists until one ends

if (l1->val < l2->val)Pick smaller node to maintain order

current->next = l1 ? l1 : l2;Attach remaining nodes after one list ends

ListNode* merged = nullptr;Initialize merged list as empty

for (auto l : lists)Iterate over all lists to merge

merged = mergeTwoLists(merged, l);Update merged list after each merge

return merged;Return fully merged list

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

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;
}

function mergeKLists(lists) {
    let merged = null;
    for (const l of lists) {
        merged = mergeTwoLists(merged, l);
    }
    return merged;
}

// Driver code
function createList(arr) {
    const dummy = new ListNode(0);
    let cur = dummy;
    for (const v of arr) {
        cur.next = new ListNode(v);
        cur = cur.next;
    }
    return dummy.next;
}

const lists = [createList([1,4,5]), createList([1,3,4]), createList([2,6])];
const merged = mergeKLists(lists);
let cur = merged;
let output = '';
while (cur) {
    output += cur.val + (cur.next ? '->' : '');
    cur = cur.next;
}
console.log(output);

Line Notes

function mergeTwoLists(l1, l2)Helper merges two sorted lists efficiently

while (l1 && l2)Traverse both lists until one ends

if (l1.val < l2.val)Pick smaller node to maintain order

current.next = l1 || l2;Attach leftover nodes after one list ends

let merged = null;Initialize merged list as empty

for (const l of lists)Iterate over all lists to merge

merged = mergeTwoLists(merged, l);Update merged list after each merge

return merged;Return fully merged list

⏱

Complexity

TimeO(kN) where k is number of lists and N total nodes

SpaceO(1) extra space (in-place merges)

Each mergeTwoLists takes O(n) where n is total nodes merged so far; repeated k times leads to O(kN).

💡 If k=10 and total nodes=1000, this means roughly 10*1000=10,000 operations, better than brute force but still slow for large k.

Interview Verdict: Accepted but can be slow for large k

Better than brute force but still not optimal; good to implement if k is small or as a stepping stone.

🧠

Optimal (Min-Heap / Priority Queue)

💡 This approach uses a min-heap to always pick the smallest current node among all lists, merging efficiently in O(N log k) time.

Intuition

Put the head of each list into a min-heap. Extract the smallest node, add it to the merged list, then add the next node from that list to the heap. Repeat until heap is empty.

Algorithm

1. Initialize a min-heap and insert the head node of each non-empty list.
2. Create a dummy node to build the merged list.
3. While the heap is not empty, extract the smallest node and append it to the merged list.
4. If the extracted node has a next node, insert it into the heap.
5. Return the merged list starting from dummy.next.

💡 This approach efficiently merges by always choosing the smallest available node, avoiding repeated full merges.

</>

Code

from typing import List, Optional
import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __lt__(self, other):
        return self.val < other.val

def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    heap = []
    for node in lists:
        if node:
            heapq.heappush(heap, node)
    dummy = ListNode(0)
    current = dummy
    while heap:
        smallest = heapq.heappop(heap)
        current.next = smallest
        current = current.next
        if smallest.next:
            heapq.heappush(heap, smallest.next)
    return dummy.next

# Driver code
if __name__ == '__main__':
    def create_list(arr):
        dummy = ListNode(0)
        cur = dummy
        for v in arr:
            cur.next = ListNode(v)
            cur = cur.next
        return dummy.next

    lists = [create_list([1,4,5]), create_list([1,3,4]), create_list([2,6])]
    merged = mergeKLists(lists)
    while merged:
        print(merged.val, end='->' if merged.next else '')
        merged = merged.next

Line Notes

import heapqUse Python's built-in min-heap implementation

def __lt__(self, other)Define less-than for ListNode to allow heap comparisons

for node in lists:Add all non-empty list heads to heap

heapq.heappush(heap, node)Push node into min-heap

smallest = heapq.heappop(heap)Pop smallest node from heap

current.next = smallestAppend smallest node to merged list

if smallest.next:If next node exists, push it to heap

return dummy.nextReturn head of merged sorted list

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        for (ListNode node : lists) {
            if (node != null) heap.offer(node);
        }
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        while (!heap.isEmpty()) {
            ListNode smallest = heap.poll();
            current.next = smallest;
            current = current.next;
            if (smallest.next != null) heap.offer(smallest.next);
        }
        return dummy.next;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode l1 = createList(new int[]{1,4,5});
        ListNode l2 = createList(new int[]{1,3,4});
        ListNode l3 = createList(new int[]{2,6});
        ListNode[] lists = new ListNode[]{l1, l2, l3};
        ListNode merged = sol.mergeKLists(lists);
        printList(merged);
    }

    static ListNode createList(int[] arr) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int v : arr) {
            cur.next = new ListNode(v);
            cur = cur.next;
        }
        return dummy.next;
    }

    static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print("->");
            head = head.next;
        }
        System.out.println();
    }
}

Line Notes

PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));Min-heap ordered by node value

for (ListNode node : lists)Add all non-null list heads to heap

ListNode smallest = heap.poll();Extract smallest node from heap

current.next = smallest;Append smallest node to merged list

if (smallest.next != null) heap.offer(smallest.next);Add next node from extracted node's list

return dummy.next;Return merged list head

public static void main(String[] args)Driver code to test solution

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

struct Compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Compare> heap;
        for (auto node : lists) {
            if (node) heap.push(node);
        }
        ListNode dummy(0);
        ListNode* current = &dummy;
        while (!heap.empty()) {
            ListNode* smallest = heap.top();
            heap.pop();
            current->next = smallest;
            current = current->next;
            if (smallest->next) heap.push(smallest->next);
        }
        return dummy.next;
    }
};

// Helper functions
ListNode* createList(const vector<int>& arr) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int v : arr) {
        cur->next = new ListNode(v);
        cur = cur->next;
    }
    return dummy.next;
}

void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << "->";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Solution sol;
    vector<ListNode*> lists = {createList({1,4,5}), createList({1,3,4}), createList({2,6})};
    ListNode* merged = sol.mergeKLists(lists);
    printList(merged);
    return 0;
}

Line Notes

priority_queue<ListNode*, vector<ListNode*>, Compare> heap;Min-heap with custom comparator for ListNode

for (auto node : lists)Add all non-null list heads to heap

ListNode* smallest = heap.top();Get smallest node from heap

current->next = smallest;Append smallest node to merged list

if (smallest->next) heap.push(smallest->next);Add next node from extracted node's list

return dummy.next;Return merged list head

int main()Driver code to test solution

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class MinHeap {
    constructor() {
        this.heap = [];
    }
    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
    parent(i) { return Math.floor((i - 1) / 2); }
    left(i) { return 2 * i + 1; }
    right(i) { return 2 * i + 2; }
    push(node) {
        this.heap.push(node);
        this.bubbleUp(this.heap.length - 1);
    }
    bubbleUp(i) {
        while (i > 0 && this.heap[this.parent(i)].val > this.heap[i].val) {
            this.swap(i, this.parent(i));
            i = this.parent(i);
        }
    }
    pop() {
        if (this.heap.length === 0) return null;
        const top = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.bubbleDown(0);
        }
        return top;
    }
    bubbleDown(i) {
        let smallest = i;
        const left = this.left(i);
        const right = this.right(i);
        if (left < this.heap.length && this.heap[left].val < this.heap[smallest].val) smallest = left;
        if (right < this.heap.length && this.heap[right].val < this.heap[smallest].val) smallest = right;
        if (smallest !== i) {
            this.swap(i, smallest);
            this.bubbleDown(smallest);
        }
    }
    isEmpty() {
        return this.heap.length === 0;
    }
}

function mergeKLists(lists) {
    const heap = new MinHeap();
    for (const node of lists) {
        if (node) heap.push(node);
    }
    const dummy = new ListNode(0);
    let current = dummy;
    while (!heap.isEmpty()) {
        const smallest = heap.pop();
        current.next = smallest;
        current = current.next;
        if (smallest.next) heap.push(smallest.next);
    }
    return dummy.next;
}

// Driver code
function createList(arr) {
    const dummy = new ListNode(0);
    let cur = dummy;
    for (const v of arr) {
        cur.next = new ListNode(v);
        cur = cur.next;
    }
    return dummy.next;
}

const lists = [createList([1,4,5]), createList([1,3,4]), createList([2,6])];
const merged = mergeKLists(lists);
let cur = merged;
let output = '';
while (cur) {
    output += cur.val + (cur.next ? '->' : '');
    cur = cur.next;
}
console.log(output);

Line Notes

class MinHeapCustom min-heap implementation for ListNode objects

this.heap.push(node);Add node to heap array

bubbleUpRestore heap property after insertion

pop()Remove and return smallest node from heap

bubbleDownRestore heap property after removal

for (const node of lists)Add all non-null list heads to heap

current.next = smallest;Append smallest node to merged list

if (smallest.next) heap.push(smallest.next);Add next node from extracted node's list

⏱

Complexity

TimeO(N log k) where N is total nodes and k is number of lists

SpaceO(k) for the heap

Each node is pushed and popped from the heap once; heap size is at most k, so operations cost O(log k).

💡 For example, with 1000 total nodes and 10 lists, this is about 1000 * log2(10) ≈ 3000 operations, very efficient.

Interview Verdict: Accepted and optimal for large k and large total nodes

This is the best approach to implement in interviews for this problem.

🧠

Divide and Conquer Merge

💡 This approach merges pairs of lists recursively, reducing the number of lists by half each iteration, improving efficiency over sequential merges.

Intuition

Repeatedly merge pairs of lists until only one list remains, similar to the merge step in merge sort.

Algorithm

1. If the list array is empty, return null.
2. While more than one list remains, merge lists in pairs.
3. Replace the list array with the merged lists.
4. Repeat until only one list remains and return it.

💡 This approach balances merges to reduce total work compared to sequential merging.

</>

Code

from typing import List, Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    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 mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    if not lists:
        return None
    interval = 1
    while interval < len(lists):
        for i in range(0, len(lists) - interval, interval * 2):
            lists[i] = mergeTwoLists(lists[i], lists[i + interval])
        interval *= 2
    return lists[0]

# Driver code
if __name__ == '__main__':
    def create_list(arr):
        dummy = ListNode(0)
        cur = dummy
        for v in arr:
            cur.next = ListNode(v)
            cur = cur.next
        return dummy.next

    lists = [create_list([1,4,5]), create_list([1,3,4]), create_list([2,6])]
    merged = mergeKLists(lists)
    while merged:
        print(merged.val, end='->' if merged.next else '')
        merged = merged.next

Line Notes

if not lists:Handle empty input edge case

interval = 1Start merging pairs with distance 1

for i in range(0, len(lists) - interval, interval * 2)Merge pairs of lists at current interval

lists[i] = mergeTwoLists(lists[i], lists[i + interval])Merge two lists and store result

interval *= 2Double interval to merge larger pairs next iteration

return lists[0]Return fully merged list

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public 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;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        int interval = 1;
        while (interval < lists.length) {
            for (int i = 0; i + interval < lists.length; i += interval * 2) {
                lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
            }
            interval *= 2;
        }
        return lists[0];
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode l1 = createList(new int[]{1,4,5});
        ListNode l2 = createList(new int[]{1,3,4});
        ListNode l3 = createList(new int[]{2,6});
        ListNode[] lists = new ListNode[]{l1, l2, l3};
        ListNode merged = sol.mergeKLists(lists);
        printList(merged);
    }

    static ListNode createList(int[] arr) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int v : arr) {
            cur.next = new ListNode(v);
            cur = cur.next;
        }
        return dummy.next;
    }

    static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print("->");
            head = head.next;
        }
        System.out.println();
    }
}

Line Notes

if (lists.length == 0) return null;Handle empty input

int interval = 1;Start merging pairs with distance 1

for (int i = 0; i + interval < lists.length; i += interval * 2)Merge pairs of lists at current interval

lists[i] = mergeTwoLists(lists[i], lists[i + interval]);Merge two lists and store result

interval *= 2;Double interval for next iteration

return lists[0];Return fully merged list

#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* 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 ? l1 : l2;
        return dummy.next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        int interval = 1;
        while (interval < (int)lists.size()) {
            for (int i = 0; i + interval < (int)lists.size(); i += interval * 2) {
                lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
            }
            interval *= 2;
        }
        return lists[0];
    }
};

// Helper functions
ListNode* createList(const vector<int>& arr) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int v : arr) {
        cur->next = new ListNode(v);
        cur = cur->next;
    }
    return dummy.next;
}

void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << "->";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Solution sol;
    vector<ListNode*> lists = {createList({1,4,5}), createList({1,3,4}), createList({2,6})};
    ListNode* merged = sol.mergeKLists(lists);
    printList(merged);
    return 0;
}

Line Notes

if (lists.empty()) return nullptr;Handle empty input

int interval = 1;Start merging pairs with distance 1

for (int i = 0; i + interval < (int)lists.size(); i += interval * 2)Merge pairs of lists at current interval

lists[i] = mergeTwoLists(lists[i], lists[i + interval]);Merge two lists and store result

interval *= 2;Double interval for next iteration

return lists[0];Return fully merged list

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

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;
}

function mergeKLists(lists) {
    if (lists.length === 0) return null;
    let interval = 1;
    while (interval < lists.length) {
        for (let i = 0; i + interval < lists.length; i += interval * 2) {
            lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
        }
        interval *= 2;
    }
    return lists[0];
}

// Driver code
function createList(arr) {
    const dummy = new ListNode(0);
    let cur = dummy;
    for (const v of arr) {
        cur.next = new ListNode(v);
        cur = cur.next;
    }
    return dummy.next;
}

const lists = [createList([1,4,5]), createList([1,3,4]), createList([2,6])];
const merged = mergeKLists(lists);
let cur = merged;
let output = '';
while (cur) {
    output += cur.val + (cur.next ? '->' : '');
    cur = cur.next;
}
console.log(output);

Line Notes

if (lists.length === 0) return null;Handle empty input

let interval = 1;Start merging pairs with distance 1

for (let i = 0; i + interval < lists.length; i += interval * 2)Merge pairs of lists at current interval

lists[i] = mergeTwoLists(lists[i], lists[i + interval]);Merge two lists and store result

interval *= 2;Double interval for next iteration

return lists[0];Return fully merged list

⏱

Complexity

TimeO(N log k) where N is total nodes and k is number of lists

SpaceO(1) extra space (in-place merges)

Merging pairs reduces the number of lists by half each iteration, leading to log k merge rounds, each processing all nodes.

💡 For 1000 nodes and 10 lists, this means about 1000 * log2(10) ≈ 3000 operations, efficient for large inputs.

Interview Verdict: Accepted and optimal alternative to min-heap

This approach is equally efficient and sometimes preferred for its simplicity and no extra data structures.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, implement the min-heap or divide and conquer approach for best efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(N log N)	O(N)	No	Yes	Mention only - never code
2. Merge Lists One by One	O(kN)	O(1)	No	Yes	Good for small k, mention as improvement
3. Min-Heap / Priority Queue	O(N log k)	O(k)	No	Yes	Optimal, implement in interviews
4. Divide and Conquer Merge	O(N log k)	O(1)	No	Yes	Optimal alternative, good to know

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when to use each in interviews.

How to Present

Step 1: Clarify input size, constraints, and output format.Step 2: Describe brute force approach to collect and sort all nodes.Step 3: Explain iterative merging of two lists to improve efficiency.Step 4: Present optimal min-heap approach for best time complexity.Step 5: Optionally mention divide and conquer merging as alternative.Step 6: Code the optimal approach with clear explanations.Step 7: Test with edge cases and discuss complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test: 7min. Total ~30min

What the Interviewer Tests

Understanding of linked list manipulation, priority queues or divide and conquer, and ability to optimize from brute force to optimal.

Common Follow-ups

• How to merge if lists are not sorted? → Sort each first or use different approach
• Can you do this in O(N) time? → No, must at least look at all nodes
• How to handle very large k with limited memory? → Use external sorting or streaming
• What if lists are arrays instead of linked lists? → Similar approach but with array indices

💡 These follow-ups test your understanding of problem constraints and ability to adapt solutions.

🔍

Pattern Recognition

When to Use

1) Multiple sorted lists or arrays to merge, 2) Need a single sorted output, 3) Input size large enough to require efficient merging, 4) Linked list data structure involved

Signature Phrases

merge k sorted listssorted linked listsmerge k sorted arrays

NOT This Pattern When

Sorting unsorted lists from scratch or problems requiring dynamic programming

Similar Problems

Merge Two Sorted Lists - simpler version with k=2Sort List - uses merge sort on linked listFind Kth Smallest Element in Sorted Matrix - uses min-heap for merging sorted rows

Practice

1. Given the following code for finding k pairs with smallest sums, what is the returned result when called with nums1 = [1,7,11], nums2 = [2,4,6], and k = 3?

easy

A. [[1, 2], [1, 4], [1, 6]]

B. [[1, 2], [7, 2], [1, 4]]

C. [[1, 2], [7, 2], [7, 4]]

D. [[1, 2], [1, 4], [7, 2]]

Solution

1. Step 1: Initialize min-heap with pairs (nums1[i] + nums2[0])

   Push (1+2,0,0), (7+2,1,0), (11+2,2,0) -> heap = [(3,0,0),(9,1,0),(13,2,0)]

2. Step 2: Extract k=3 pairs

   Pop (3,0,0) -> result [[1,2]], push (1+4,0,1) -> heap [(7,0,1),(9,1,0),(13,2,0)] Pop (7,0,1) -> result [[1,2],[1,4]], push (1+6,0,2) -> heap [(7,1,0),(13,2,0),(7,0,2)] Pop (7,1,0) -> result [[1,2],[1,4],[7,2]]

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches expected output from code trace [OK]

Hint: Heap pops smallest sum pairs in order [OK]

Common Mistakes:

• Off-by-one in indexing nums2
• Wrong order of pairs in result
• Confusing heap push/pop order

2. You are given K sorted arrays and need to find the median of all elements combined without fully merging them. Which algorithmic approach guarantees an optimal solution in terms of time complexity for large inputs?

easy

A. Merge all arrays fully into one sorted array and then pick the median.

B. Use binary search on the value range combined with counting elements ≤ mid across arrays.

C. Apply a greedy approach by repeatedly picking the smallest current element from arrays until median is found.

D. Use dynamic programming to build a table of medians for subarrays and combine results.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the median without merging all arrays fully, which is costly for large inputs.

2. Step 2: Identify optimal approach

   Binary search on the value range combined with counting elements ≤ mid leverages sorted arrays and avoids full merge, achieving better time complexity.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search on value range is known optimal for this problem [OK]

Hint: Binary search on value range beats full merge [OK]

Common Mistakes:

• Assuming full merge is always optimal
• Confusing greedy with binary search
• Misapplying DP to median finding

3. Consider the following Python code implementing the optimal job assignment to K machines. Given K = 2 and jobs = [[0,5],[1,2],[5,3]], what is the final returned list indicating the machine assigned to each job (in original job order)?

easy

A. [0, 1, 0]

B. [0, 0, 1]

C. [1, 0, 1]

D. [1, 1, 0]

Solution

1. Step 1: Sort jobs by start time

   Jobs sorted by start time: (0,[0,5]), (1,[1,2]), (2,[5,3]) with indices 0,1,2 respectively.

2. Step 2: Simulate assignment

   Initially, available machines = [0,1]. - Job 0 starts at 0: assign machine 0, finish at 5. - Job 1 starts at 1: machine 1 is free, assign machine 1, finish at 3. - Job 2 starts at 5: running machines finish times are 3 and 5; both ≤ 5, so both machines become available. Assign machine 0 (smallest index). Result array indexed by original job indices: [0,1,0].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trace matches output [0,1,0] [OK]

Hint: Sort jobs by start time and track machine availability with heaps [OK]

Common Mistakes:

• Assigning machine 1 to job 1 instead of machine 0
• Not freeing machines before assigning next job
• Mixing up job indices after sorting

4. Consider the following buggy code for finding the k-th smallest sum of pairs from two sorted arrays. Which line contains the subtle bug that can cause incorrect results or runtime errors?

def countPairs(nums1, nums2, mid):
    count = 0
    j = len(nums2) - 1
    for i in range(len(nums1)):
        while j >= 0 and nums1[i] + nums2[j] > mid:
            j -= 1
        count += (j + 1)
    return count

def kthSmallestSum(nums1, nums2, k):
    low = nums1[0] + nums2[0]
    high = nums1[-1] + nums2[-1]
    while low < high:
        mid = (low + high) // 2
        if countPairs(nums1, nums2, mid) <= k:  # Bug here
            low = mid + 1
        else:
            high = mid
    return low

medium

A. Line with 'j = len(nums2) - 1' initialization

B. Line with 'count += (j + 1)' inside countPairs

C. Line with 'while j >= 0 and nums1[i] + nums2[j] > mid:' condition

D. Line with 'if countPairs(nums1, nums2, mid) <= k:' in kthSmallestSum

Solution

1. Step 1: Understand binary search condition

   Correct condition is countPairs(...) < k to move low up; using ≤ k skips valid sums.

2. Step 2: Effect of bug

   Using ≤ k causes binary search to overshoot and miss the exact k-th sum, returning incorrect result.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Changing ≤ to < fixes correctness [OK]

Hint: Binary search must use strict less-than for correct convergence [OK]

Common Mistakes:

• Using ≤ instead of < in binary search condition
• Off-by-one errors in countPairs

5. Suppose jobs can be reused multiple times (i.e., the same job can be assigned repeatedly), and you want to assign jobs to machines minimizing start delays as before. Which modification to the optimal algorithm is necessary to handle this scenario correctly?

hard

A. No change needed; the existing algorithm handles reuse naturally by sorting jobs once and assigning sequentially.

B. Sort jobs by duration instead of start time to prioritize shorter jobs for reuse.

C. Use a brute force approach checking all possible assignments since reuse breaks heap assumptions.

D. Maintain a priority queue of job instances and re-insert jobs after completion to simulate reuse, updating start times accordingly.

Solution

1. Step 1: Understand job reuse impact

   Reusing jobs means after a job finishes, it can be assigned again, so jobs are not fixed once but can appear multiple times.

2. Step 2: Modify algorithm to handle reuse

   Maintain a priority queue of job instances with their next available start times. After a job finishes, re-insert it with updated start time to simulate reuse.

3. Step 3: Why other options fail

   No change ignores reuse; brute force is inefficient; sorting by duration ignores start times and scheduling constraints.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Re-inserting jobs after completion models reuse correctly [OK]

Hint: Re-insert jobs with updated start times to simulate reuse [OK]

Common Mistakes:

• Assuming reuse needs no algorithm change
• Switching sort order breaks scheduling correctness
• Using brute force is inefficient and unnecessary