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. Consider the following code snippet implementing the two-pointer approach to find the intersection of two linked lists. Given the lists: listA: 1 -> 2 -> 3 -> 4 -> 5 listB: 9 -> 4 -> 5 where nodes with values 4 and 5 are shared (intersection starts at node with value 4). What is the value returned by the function?

easy

A. 3

B. 4

C. 5

D. No intersection

Solution

1. Step 1: Trace pointers through lists

   pA starts at 1, pB at 9. They advance until pA reaches 4, pB reaches 4 (intersection node). Since nodes are shared, pA is pB at node with value 4.

2. Step 2: Confirm return value

   The function returns the intersection node, which has value 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Intersection node value is 4 as expected [OK]

Hint: Pointers meet at shared node 4 [OK]

Common Mistakes:

• Returning node value instead of node reference
• Confusing next pointers
• Off-by-one in pointer switching

2. Given the following Python code implementing the recursive reversal of a sublist, what is the output when reversing positions 2 to 3 of the list [1, 2, 3, 4]?

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

successor = None

def reverseN(head, n):
    global successor
    if n == 1:
        successor = head.next
        return head
    last = reverseN(head.next, n - 1)
    head.next.next = head
    head.next = successor
    return last

def reverseBetween(head, left, right):
    if left == 1:
        return reverseN(head, right)
    head.next = reverseBetween(head.next, left - 1, right - 1)
    return head

# Build list
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(3):
    nodes[i].next = nodes[i+1]

new_head = reverseBetween(nodes[0], 2, 3)
curr = new_head
while curr:
    print(curr.val, end=' ')
    curr = curr.next

easy

A. 1 3 2 4

B. 1 2 3 4

C. 3 2 1 4

D. 1 4 3 2

Solution

1. Step 1: Trace reverseN for n=2 starting at node with val=2

   reverseN reverses first 2 nodes starting at node 2: it recursively reverses node 3, then sets pointers to reverse links between 2 and 3.

2. Step 2: Reconnect reversed sublist to original list

   Node 1 points to reversed sublist head (node 3), and the tail of reversed sublist (node 2) points to node 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected partial reversal between positions 2 and 3 [OK]

Hint: Partial reversal swaps nodes 2 and 3 only [OK]

Common Mistakes:

• Assuming full list reversed
• Off-by-one error reversing wrong nodes
• Confusing node values with positions

3. What is the time complexity of the optimal recursive solution that pads the shorter list and recursively adds two linked lists representing numbers in forward order, each of length n and m respectively?

medium

A. O(n + m)

B. O(max(n, m))

C. O(max(n, m) * log(max(n, m)))

D. O(n * m)

Solution

1. Step 1: Analyze list traversal and padding

   Getting lengths and padding shorter list takes O(n + m) time.

2. Step 2: Analyze recursive addition

   Recursion visits each node once, total O(max(n, m)) steps.

3. Step 3: Simplify complexity

   Since padding and traversal are linear, total time complexity is O(max(n, m)).

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Each node processed once, no nested loops [OK]

Hint: Single pass plus padding is linear [OK]

Common Mistakes:

• Mistaking recursion stack as extra multiplicative factor
• Confusing with quadratic due to nested loops
• Assuming log factor from recursion depth

4. What is the time complexity of the two-pointer length equalization approach to find the intersection node of two singly linked lists with lengths m and n, respectively?

medium

A. O(m + n)

B. O(m * n)

C. O(max(m, n) * 2)

D. O(m + n + k), where k is the length of the intersection

Solution

1. Step 1: Identify loop iterations

   Each pointer traverses its list once, then switches to the other list, traversing at most m + n nodes.

2. Step 2: Simplify complexity

   Total steps are proportional to m + n, so time complexity is O(m + n). O(m * n) is brute force, O(max(m, n) * 2) simplifies to O(m + n), and O(m + n + k) adds an unnecessary term.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer approach is linear in combined list lengths [OK]

Hint: Pointers traverse each list once plus switch [OK]

Common Mistakes:

• Confusing nested loops with two-pointer approach
• Counting intersection length separately
• Misreading max(m,n) as multiplication

5. Suppose the problem is modified so that the linked list is circular (last node points back to head). Which of the following changes is necessary to correctly remove the nth node from the end in one pass?

hard

A. Use the same two-pointer approach without changes; it works as is.

B. First break the circular link to convert it into a linear list, then apply the standard algorithm.

C. Use a hash set to detect the cycle and count nodes before removal.

D. Modify the recursion to detect when the node revisits the head to stop infinite recursion.

Solution

1. Step 1: Understand circular list implications

   In a circular list, traversal never ends naturally, so counting nodes or recursion can loop infinitely.

2. Step 2: Break the cycle

   Temporarily breaking the cycle converts it to a linear list, allowing standard removal algorithms to work correctly.

3. Step 3: Restore circular link if needed

   After removal, reconnect the last node to the new head to restore circularity.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Breaking cycle prevents infinite loops and enables standard logic [OK]

Hint: Circular lists require cycle breaking before linear algorithms [OK]

Common Mistakes:

• Assuming two-pointer works on circular lists
• Using recursion without cycle detection
• Using extra space unnecessarily