Merge k Sorted Lists

Merge k sorted linked lists into a single sorted list.

Function signature

func MergeKLists(lists []*ListNode) *ListNode

Inputs / outputs

• lists: slice of list heads (may include nil).
• Return: head of the merged sorted list.

Example

lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Constraints

• 0 <= k <= 10_000
• total nodes <= 100_000

Core idea (near-solution)

Merge lists pairwise using divide and conquer. Each round halves the number of lists, keeping total work O(n log k).

Invariant: after each round, every list in the array is fully merged and sorted.

Algorithm (step-by-step)

1. If lists is empty, return nil.
2. While len(lists) > 1:
   • Merge lists in pairs: (0,1), (2,3), ....
   • If there is an odd list out, carry it forward.
3. Return the single remaining list.

Correctness sketch

• Invariant: after each round, every list in the array is fully merged and sorted.
• The problem is split into independent subproblems.
• By induction, recursive solutions are correct.
• The combine step preserves correctness for the full problem.

Trace (hand walkthrough)

Example input:
lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Walk:
- heap init: 1(l1),1(l2),2(l3)
- pop 1(l1) -> push 4; pop 1(l2) -> push 3; pop 2(l3) -> push 6
- continue pops -> [1,1,2,3,4,4,5,6]

Pitfalls to avoid

• Merging sequentially from left to right (can be O(k*n)).
• Losing nodes by reusing pointers without a dummy head.

Complexity

• Time: O(n log k) where n is total nodes.
• Extra space: O(1) besides recursion/temporary lists.

Implementation notes (Go)

• Use a helper mergeTwoLists with a dummy head.
• The reference solution uses iterative pairwise merging (no recursion needed).