Log inSign up
easyLeetCodeNot Started

Merge Two Sorted Lists

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

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*.

Example 1 · Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Explanation: Nodes are merged into ascending order by comparing current heads.

Example 2 · Example 2:

Input: list1 = [], list2 = []
Output: []
Explanation: Merging two empty lists results in an empty list.

Example 3 · Example 3:

Input: list1 = [], list2 = [0]
Output: [0]
Explanation: Merging empty list with [0] returns [0].

Constraints:

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Dummy Head pattern to eliminate edge cases when constructing new lists.
  • Implement the two-pointer zipper merge with O(1) auxiliary space.
  • Exploit pointer structures to splice remaining list fragments in O(1) constant time.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Combining two pre-sorted pointer sequences into one.
  • Need to preserve ascending sorted order in O(1) extra space.
  • Subroutine in Merge Sort for Linked Lists.

Algorithmic Decision Tree:

  • Use dummy sentinel node to avoid complex conditional branches for choosing the initial head.
  • Directly wire tail.next = remainingList without iterating node-by-node once one list runs out.

Connected Patterns:

Merge K Sorted ListsSort List (Merge Sort on Linked List)Merge Sorted Array

1. Brute Force — Array Collection, Sort & Rebuild

Intuition

Read all elements from both lists into an array, sort the array, and build a brand new linked list.

Algorithm

  1. Step 1: Collect all values from list1 and list2 into array vals.
  2. Step 2: Sort vals in non-decreasing order.
  3. Step 3: Construct a new linked list with vals and return its head.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct ListNode {
8 int val;
9 ListNode *next;
10 ListNode(int x) : val(x), next(nullptr) {}
11};
12
13class Solution {
14public:
15 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
16 vector<int> vals;
17 for (ListNode* c = list1; c; c = c->next) vals.push_back(c->val);
18 for (ListNode* c = list2; c; c = c->next) vals.push_back(c->val);
19
20 sort(vals.begin(), vals.end());
21
22 ListNode* dummy = new ListNode(0);
23 ListNode* curr = dummy;
24 for (int val : vals) {
25 curr->next = new ListNode(val);
26 curr = curr->next;
27 }
28 ListNode* res = dummy->next;
29 delete dummy;
30 return res;
31 }
32};
33
34int main() {
35 ListNode* l1 = new ListNode(1);
36 l1->next = new ListNode(2);
37 l1->next->next = new ListNode(4);
38
39 ListNode* l2 = new ListNode(1);
40 l2->next = new ListNode(3);
41 l2->next->next = new ListNode(4);
42
43 Solution sol;
44 ListNode* merged = sol.mergeTwoLists(l1, l2);
45
46 cout << "Brute Force Merged: ";
47 for (ListNode* c = merged; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
48 cout << endl;
49 return 0;
50}

Time & Space Complexity

  • Time complexity: O((N + M) log(N + M)) — Extracts N + M values into an array, sorts in O((N+M) log(N+M)), and creates new nodes in O(N+M).
  • Space complexity: O(N + M) — Allocates array buffer and fresh nodes for all elements.

Why Brute Force Doesn't Scale:

Array sorting runs in O((N+M) log(N+M)) time and allocates O(N+M) space.

For N = 100,000 and M = 100,000, iterative merge takes <1ms and 0 heap allocations.

2. Better — Recursive Divide & Conquer Splicing

Intuition

The smaller of list1 and list2 head should be the first node. Recursively merge the rest of that list with the other list, and wire the result to head.next.

Algorithm

  1. Step 1: If list1 == null, return list2.
  2. Step 2: If list2 == null, return list1.
  3. Step 3: If list1.val <= list2.val:
  4. a. Set list1.next = mergeTwoLists(list1.next, list2).
  5. b. Return list1.
  6. Step 4: Else:
  7. a. Set list2.next = mergeTwoLists(list1, list2.next).
  8. b. Return list2.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12public:
13 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
14 if (!list1) return list2;
15 if (!list2) return list1;
16
17 if (list1->val <= list2->val) {
18 list1->next = mergeTwoLists(list1->next, list2);
19 return list1;
20 } else {
21 list2->next = mergeTwoLists(list1, list2->next);
22 return list2;
23 }
24 }
25};
26
27int main() {
28 ListNode* l1 = new ListNode(1);
29 l1->next = new ListNode(2);
30 l1->next->next = new ListNode(4);
31
32 ListNode* l2 = new ListNode(1);
33 l2->next = new ListNode(3);
34 l2->next->next = new ListNode(4);
35
36 Solution sol;
37 ListNode* merged = sol.mergeTwoLists(l1, l2);
38
39 cout << "Recursive Merged: ";
40 for (ListNode* c = merged; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
41 cout << endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N + M) — Each recursive invocation connects one node. Total recursion depth is N + M.
  • Space complexity: O(N + M) call stack — Recursive call stack grows linearly with total number of nodes.

3. Optimal — Iterative Dummy Head Sentinel Zipper Merge

Intuition

Initialize dummy = new ListNode(0) and tail = dummy. Compare list1.val and list2.val. Attach the smaller node to tail.next, and advance that list. When one list becomes null, attach the other directly: tail.next = list1 ? list1 : list2. Return dummy.next.

Algorithm

  1. Step 1: Create dummy = new ListNode(0) and tail = dummy.
  2. Step 2: While list1 != null && list2 != null:
  3. a. If list1.val <= list2.val: tail.next = list1, list1 = list1.next.
  4. b. Else: tail.next = list2, list2 = list2.next.
  5. c. tail = tail.next.
  6. Step 3: tail.next = list1 != null ? list1 : list2.
  7. Step 4: Return dummy.next.

Merge Two Sorted Lists Master Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
dummy
Visual state
Values and pointers at this exact step
linked list
tail → 1a
Node d
dummy
Node 1a
1
NULL
Check / comparison
1 <= 1
Decision / next transition
Attach from list1
Why this step matters

dummy.next is list1(1).

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12public:
13 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
14 ListNode dummy(0);
15 ListNode* tail = &dummy;
16
17 while (list1 && list2) {
18 if (list1->val <= list2->val) {
19 tail->next = list1;
20 list1 = list1->next;
21 } else {
22 tail->next = list2;
23 list2 = list2->next;
24 }
25 tail = tail->next;
26 }
27
28 tail->next = list1 ? list1 : list2;
29 return dummy.next;
30 }
31};
32
33int main() {
34 ListNode* l1 = new ListNode(1);
35 l1->next = new ListNode(2);
36 l1->next->next = new ListNode(4);
37
38 ListNode* l2 = new ListNode(1);
39 l2->next = new ListNode(3);
40 l2->next->next = new ListNode(4);
41
42 Solution sol;
43 ListNode* merged = sol.mergeTwoLists(l1, l2);
44
45 cout << "Optimal Merged: ";
46 for (ListNode* c = merged; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
47 cout << endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(N + M) — Each step consumes one node from either list1 or list2. When one list runs out, remaining nodes are attached in O(1).
  • Space complexity: O(1) — Operates strictly in-place with a single dummy node and pointer.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Collect into Array, Sort & BuildO((N + M) log(N + M))O(N + M)Traverse both lists, store all values in a dynamic array, sort the array using standard quicksort/timsort, and construct a new linked list.Sorting overhead and extra memory allocation.
2.Better — Recursive Subproblem MergingO(N + M)O(N + M) call stackIf list1 == null, return list2. If list2 == null, return list1. If list1.val < list2.val, set list1.next = mergeTwoLists(list1.next, list2) and return list1; else set list2.next = mergeTwoLists(list1, list2.next) and return list2.Call stack frames.
3.Optimal — Iterative Dummy Head Sentinel Zipper MergeOptimalO(N + M)O(1)Maintain dummy sentinel and tail = dummy. Compare list1.val and list2.val, linking tail.next to the smaller node. Once one list is exhausted, attach the other list in O(1) time.Optimal.

Common Pitfalls & Crucial Edge Cases

Iterating through the remainder list

Using a loop to append the remaining elements of the non-null list instead of doing tail.next = list1 ? list1 : list2 in O(1).

Memory leak in C++

Allocating dummy with new on the heap and failing to delete it (stack allocation ListNode dummy(0) is idiomatic).

Null pointer dereferences on empty inputs

Forgetting to check if either input list is initially null.

Crucial Edge Cases to Validate:

  • Both Lists Empty — list1 = null, list2 = null -> returns null.
  • One List Empty — list1 = null, list2 = [0] -> returns [0] in O(1).
  • Disjoint Ranges — list1 = [1, 2, 3], list2 = [10, 20, 30] -> list1 is fully attached, then list2 is attached in O(1).
  • Duplicate Values — list1 = [2, 2], list2 = [2, 2] -> handles non-decreasing equality cleanly.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the dummy head pattern immediately: 'We will use a dummy sentinel node to avoid special casing the head.'
  2. Highlight the O(1) remainder attachment: tail.next = list1 ? list1 : list2.
  3. Mention how this function serves as the core subroutine for 'Merge K Sorted Lists' and 'Sort List'.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the iterative approach preferred over the recursive approach in production environments?

2.What happens after the while (list1 && list2) loop terminates in the iterative solution?

3.What purpose does the dummy head sentinel serve?

Back to DSA Sheet