Merge Two Sorted Lists

Problem

Merge two sorted linked lists into one sorted linked list. Reuse the existing nodes (do not create new ones).

Input:  list1 = 1->2->4,  list2 = 1->3->5   → 1->1->2->3->4->5
Input:  list1 = [],        list2 = []          → []
Input:  list1 = [],        list2 = [0]         → [0]

Solution

Approach: Dummy head with a two-pointer merge.

Create a sentinel dummy = Node(0) and a builder pointer curr = dummy. The dummy exists so attaching the first merged node is identical to attaching every later one - curr always has somewhere to point from, so there is no special case for an empty result. While both lists still have nodes, compare their heads and splice the smaller one onto curr.next, then advance that list's pointer and curr. Using <= keeps the merge stable: when values tie, list1's node goes first. Each node is examined and linked exactly once, so the merged list reuses the existing nodes - no allocation.

The loop ends the moment one list is exhausted. The other list is already sorted and entirely larger-or-equal to what we have placed, so curr.next = list1 or list2 attaches its whole remaining tail in one move (Python's or returns the first non-None operand, or None if both are empty). Finally return dummy.next, skipping the sentinel to hand back the real head. Tracing [1,2,4] and [1,3,5]: attach 1 from list1, then 1 from list2 (tie went to list1 first), then 2, 3, 4, 5, yielding 1->1->2->3->4->5.

Edge cases: Two empty inputs return dummy.next = None. One empty input skips the loop and the or attaches the non-empty list directly.

Complexity: O(m + n) time, O(1) space - one pass over both lists, no new nodes.