Merge Two Sorted Lists
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
