Merge Two Sorted Lists
Dummy-head merge — splice the smaller head into the tail at each step.
3 min read
linked-list recursion
Problem#
Merge two sorted linked lists into a single sorted list.
Examples#
[1,2,4], [1,3,4]→[1,1,2,3,4,4].[], []→[];[], [0]→[0].
Constraints#
0 <= length <= 50.
Approach#
Dummy head, tail pointer. Each step, splice the smaller of the two heads onto the tail. When one list is exhausted, attach the rest of the other.
Solution#
struct ListNode { int val; ListNode* next; };
class Solution {public: ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode dummy{0, nullptr}; ListNode* tail = &dummy; while (a && b) { if (a->val <= b->val) { tail->next = a; a = a->next; } else { tail->next = b; b = b->next; } tail = tail->next; } tail->next = a ? a : b; return dummy.next; }};func mergeTwoLists(a *ListNode, b *ListNode) *ListNode { dummy := &ListNode{} tail := dummy for a != nil && b != nil { if a.Val <= b.Val { tail.Next = a a = a.Next } else { tail.Next = b b = b.Next } tail = tail.Next } if a != nil { tail.Next = a } else { tail.Next = b } return dummy.Next}from typing import Optional
class Solution: def mergeTwoLists( self, a: Optional[ListNode], b: Optional[ListNode], ) -> Optional[ListNode]: dummy = ListNode() tail = dummy while a and b: if a.val <= b.val: tail.next = a a = a.next else: tail.next = b b = b.next tail = tail.next tail.next = a if a else b return dummy.nextfunction mergeTwoLists(a, b) { const dummy = new ListNode(0); let tail = dummy; while (a && b) { if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; } tail = tail.next; } tail.next = a ? a : b; return dummy.next;}class Solution { public ListNode mergeTwoLists(ListNode a, ListNode b) { ListNode dummy = new ListNode(0); ListNode tail = dummy; while (a != null && b != null) { if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; } tail = tail.next; } tail.next = (a != null) ? a : b; return dummy.next; }}function mergeTwoLists(a: ListNode | null, b: ListNode | null): ListNode | null { const dummy = new ListNode(0); let tail: ListNode = dummy; while (a && b) { if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; } tail = tail.next as ListNode; } tail.next = a ? a : b; return dummy.next;}Editorial#
In-place splicing — no allocation. The dummy head avoids the “first node is the smaller of the two” branch. After the loop, exactly one input list is non-null and its remainder is appended in O(1).
Complexity#
- Time:
O(m + n). - Space:
O(1).
Concept revision#
Related#