Merge two sorted linked list
EasyUnlock detailed company stats for this questionUpgrade
You're given the heads of two sorted linked lists, list1 and list2. Merge them into one sorted list by splicing their nodes together, and return the head of the merged list.
Example 1
Input: list1 = [1, 2, 4], list2 = [1, 3, 4] Output: [1, 1, 2, 3, 4, 4]
Example 2
Input: list1 = [], list2 = [0] Output: [0]
An empty list contributes nothing.
Constraints
- Each list has between
0and50nodes. -100 <= Node.val <= 100- Both lists are sorted in non-decreasing order.
Approach
Both lists are sorted, so the next node of the merged list is always the smaller of the two current heads. Walk both lists together, attach the smaller head to the result, and advance that list. When one list runs out, attach the rest of the other one, which is already sorted. Starting the result with a dummy node means the first attachment works exactly like every other one.
The Merge Linked Lists lesson extends this to k sorted lists.
Steps
- Create a dummy node and set
tailto it. - While both lists have nodes, attach the smaller head to
tail.next, advance that list, and movetailforward. - Attach whichever list still has nodes.
- Return
dummy.next.
Complexity
- Time:
O(m + n), wheremandnare the lengths of the two lists. - Space:
O(1). The merge reuses the existing nodes.
Common mistakes
- Forgetting the leftover nodes. When one list runs out, the rest of the other list still has to be attached.
- Returning
dummyinstead ofdummy.next. The dummy node is a placeholder, not part of the answer.
Interview experiences
1 sharedRelated questions
Merge two sorted listsMerge k sorted linked lists.Sort a doubly linked list using merge sort.Related courses

Course

Course
Course
