Merge Two Sorted Lists
The key idea
Both inputs are already sorted, so the next node of the answer is always the smaller of the two current heads. Splice that node in, advance only that list, and repeat. A dummy head node lets you append without special-casing the first node.
Problem
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Constraints
- The number of nodes in both lists is in the range
[0, 50]. -100 <= Node.val <= 100- Both
list1andlist2are sorted in non-decreasing order.
Examples
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Input: list1 = [], list2 = []
Output: []
Input: list1 = [], list2 = [0]
Output: [0]
Complexity
Time: O(n + m) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Linked List problems
- Add Two NumbersMEDIUM
- Copy List with Random PointerMEDIUM
- Design Linked ListMEDIUM
- Insert Greatest Common Divisors in Linked ListMEDIUM
- Intersection of Two Linked ListsEASY
- Maximum Twin Sum of a Linked ListMEDIUM
- Odd Even Linked ListMEDIUM
- Partition ListMEDIUM
- Remove Duplicates from Sorted List IIMEDIUM
- Remove Linked List ElementsEASY
- Remove Nth Node From End of ListMEDIUM
- Reorder ListMEDIUM