Merge Two Sorted Lists

Merge two sorted linked lists and return the head of the merged sorted list.

Function signature

func MergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode

Inputs / outputs

• l1, l2: heads of sorted linked lists.
• Return: head of merged sorted list.

Example

1 -> 2 -> 4
1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Constraints

• 0 <= number of nodes <= 100_000
• Lists are sorted in non-decreasing order.

Core idea (near-solution)

Use a dummy head and append the smaller node each step.

Invariant: the merged list so far is sorted.

Algorithm (step-by-step)

1. Initialize a dummy node and a tail pointer.
2. While both lists are non-empty:
   • Append the smaller node to the tail.
   • Advance the corresponding list.
3. Append the remaining nodes.
4. Return dummy.Next.

Correctness sketch

• Invariant: the merged list so far is sorted.
• Pointer rewiring preserves all nodes and changes only their order or links.
• Each step maintains list connectivity and the intended invariant.
• When the traversal ends, the list structure matches the required transformation.

Trace (hand walkthrough)

Example input:
1 -> 2 -> 4
1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Walk:
- pick 1 (list1), then 1 (list2)
- next pick 2 (list1), then 3 (list2)
- append remaining 4 (list1), 4 (list2) -> 1->1->2->3->4->4

Pitfalls to avoid

• Forgetting to attach the remaining tail.

Complexity

• Time: O(n+m)
• Extra space: O(1) (reusing nodes).

Implementation notes (Go)

• Use a dummy head and tail pointer to simplify merging.
• Attach the remaining list when one side is exhausted.