Merge Two Sorted Lists
Easy· dummy head· merge
Problem
You are given the heads of two linked lists, each sorted in non-decreasing order. Splice their nodes together into one sorted list and return its head, reusing the existing nodes.
Examples
Input: list1 = [1,3,8], list2 = [2,3,4]
Output: [1,2,3,3,4,8]
Input: list1 = [], list2 = [0]
Output: [0]
Constraints
- • 0 <= nodes in each list <= 50
- • Both lists are sorted non-decreasing
Hints & approach
Hint 1
Repeatedly take the smaller of the two current heads.
Hint 2
A dummy node in front of the result removes the special case for the first node.
Hint 3
When one list runs out, attach the rest of the other in one step.
Approachtry the hints first
Create a dummy node and a tail pointer to it. While both lists are non-empty, attach whichever head is smaller to tail.next, advance that list, and advance tail. When one list is exhausted, link tail.next to the remainder of the other, which is already sorted. Return dummy.next. No new nodes are allocated beyond the dummy.
Time O(n + m) · Space O(1)