Merge Two Sorted Lists

Dummy-head merge — splice the smaller head into the tail at each step.

Easy
Time O(m + n) Space O(1)
LeetCode
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#

Merge Two Sorted Lists
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.