You are given list1 and list2, the heads of two singly linked lists (either may be empty).
Each list's values are in non-decreasing order.
Join them into a single list whose values are in non-decreasing order, by relinking the nodes you were given rather than making new ones, and return its head.
Linked lists are written as their values from head to tail, so [1, 4, 6] is 1 → 4 → 6, and
[] is an empty list.
Example 1
- Input
- list1 = [2, 5, 9], list2 = [1, 5, 6, 12]
- Output
- [1, 2, 5, 5, 6, 9, 12]
Example 2
- Input
- list1 = [], list2 = [3]
- Output
- [3]
Constraints
- Each list holds 0 to 5000 nodes.
- Every value is between −10⁴ and 10⁴.
- Each list is sorted in non-decreasing order.
Show the pattern
Linked list
You build one chain by repeatedly taking the smaller of two heads. A dummy node in front of the result and a pointer to its tail let you splice each node in without special cases.
See linked list in a visualiserShow the approach
Make a dummy node and keep tail, the last node of the merged list so far, starting at the
dummy. While both lists still have nodes, compare their heads, link the smaller one after tail,
move that list on to its next node, and move tail to the node just linked.
When one list runs out, the other's remaining nodes are already in order, so link them after
tail all at once. The merged list starts at dummy.next.
Time: O(n + m) · Space: O(1) extra