Merge k Sorted Lists

leetcode.com

Problem Statement

Given K sorted linked lists, merge them into one sorted linked list.

---

Brute Force Intuition

Put all nodes into an array.

Sort the array.

Create a new linked list.

Complexity

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Where:

N = Total Nodes

---

Better Heap Approach

Push first node of every list into Min Heap.

Repeatedly:

Take smallest node
Insert next node

Complexity

O(N log K)

---

Moving Towards Optimal

Instead of merging one list at a time:

Merge Lists Pairwise

Exactly like Merge Sort.

---

Pattern Recognition

Merge K Things

=> Divide and Conquer

---

Optimal Approach

K Lists

Split Into Two Halves

Merge Left
Merge Right

Merge Results

---

Optimal Java Solution

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {

        if (lists.length == 0)
            return null;

        return mergeKLists(
            lists,
            0,
            lists.length - 1
        );
    }

    private ListNode mergeKLists(
        ListNode[] lists,
        int si,
        int ei) {

        if (si == ei)
            return lists[si];

        int mid = (si + ei) / 2;

        ListNode left =
            mergeKLists(lists, si, mid);

        ListNode right =
            mergeKLists(lists, mid + 1, ei);

        return mergeTwoLists(left, right);
    }

    private ListNode mergeTwoLists(
        ListNode l1,
        ListNode l2) {

        ListNode dummy =
            new ListNode(-1);

        ListNode curr = dummy;

        while (l1 != null && l2 != null) {

            if (l1.val <= l2.val) {

                curr.next = l1;
                l1 = l1.next;

            } else {

                curr.next = l2;
                l2 = l2.next;
            }

            curr = curr.next;
        }

        curr.next =
            (l1 != null ? l1 : l2);

        return dummy.next;
    }
}

---

Dry Run

1→4→5

1→3→4

2→6

Merge:

(1→4→5) + (1→3→4)

=
1→1→3→4→4→5

Merge with:

2→6

Final:

1→1→2→3→4→4→5→6

---

Complexity Analysis

Metric	Complexity
Time	O(N log K)
Space	O(log K)

---

Interview One-Liner

Use Divide & Conquer like Merge Sort by recursively merging pairs of linked lists.