Merge Two Sorted Lists
Merge two sorted linked lists into one sorted list and return its head.
Open on LeetCode ↗Intuition
Both lists are sorted, so the next node of the result is always the smaller of the two current heads. A dummy head removes the awkward special case for the very first node.
Approach
Don't throw away the existing sort
Collecting every value, sorting, and rebuilding works but ignores that both inputs are already sorted — and it allocates a whole new structure. Since the lists are sorted, the next node of the merged result is always just the smaller of the two current heads, which we can decide one node at a time in linear time.
Use a dummy head to avoid edge cases
Building a linked list incrementally has an annoying wrinkle: the very first node has no predecessor to attach to, forcing a special case. A throwaway dummy node fixes this — tail starts at the dummy and always has somewhere to append, and at the end we return dummy.next, discarding the placeholder. This keeps the loop body uniform.
Compare heads, then splice the remainder
While both lists have nodes, attach the smaller head to tail and advance that list (using <= rather than < keeps equal values in a stable order). Once one list empties, the other is already sorted, so tail.next = list1 or list2 splices its entire remainder on in a single step — no need to walk it. O(m + n) time, O(1) space, no new nodes.
Solution & live demo
Edge cases
The while loop is skipped and tail.next = list1 or list2 attaches the non-empty list directly.
Nothing is appended; dummy.next is null — the correct empty result.
Using <= (not <) keeps equal values in a stable, predictable order.