Log inSign up
mediumLeetCodeNot Started

Merge In Between Linked Lists

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

Linked List
Solve on LeetCode
Lesson

Problem Statement

You are given two linked lists: list1 and list2 of sizes n and m respectively.

Remove list1's nodes from the ath node to the bth node (0-indexed), and put list2 in their place.

The blue edges in the following figure indicate the operations: - Connect node a-1 of list1 to the head of list2. - Connect the tail of list2 to node b+1 of list1.

Build the result list and return its head.

Example 1 · Example 1:

Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: Nodes at indices 3 and 4 (values 6 and 9) are removed. list2 is inserted between node 13 (index 2) and node 5 (index 5).

Example 2 · Example 2:

Input: list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
Output: [0,1,1000000,1000001,1000002,1000003,1000004,6]
Explanation: Nodes 2 through 5 are removed from list1, and list2 is spliced in their place.

Constraints:

  • 3 <= list1.length <= 10^4
  • 1 <= a <= b < list1.length - 1
  • 1 <= list2.length <= 10^4
  • 1 <= Node.val <= 10^5

What You'll Learn

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

  • Navigate 0-indexed linked list positions accurately without off-by-one errors.
  • Perform multi-list splicing with anchor pointers in O(1) auxiliary space.
  • Manage memory cleanup for detached nodes in manual memory environments.

Pattern Recognition Trigger

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

Signals to Look For:

  • Replacing a contiguous 0-indexed range [a, b] within one linked list with another linked list.
  • Splicing disjoint pointer chains.
  • Fixed 1-based bounds ensuring a >= 1 (never removes list1's original head).

Algorithmic Decision Tree:

  • Since 1 <= a, head1 will never be removed, eliminating the need for dummy sentinel head logic.
  • Find anchors nodeA_prev, nodeB_next, and tail2 in a single pass over list1 and list2.

Connected Patterns:

Reverse Linked List IIRemove Nth Node From End of ListFlatten a Multilevel Doubly Linked List

1. Brute Force — Array Conversion & Reconstruction

Intuition

Read all nodes of list1 into an array. Replace elements from index a to b with elements of list2. Rebuild a new linked list from the combined array.

Algorithm

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

Time & Space Complexity

  • Time complexity: O(N + M) — Extracts N elements from list1 and M elements from list2, splices in array, and creates new linked nodes in O(N + M).
  • Space complexity: O(N + M) — Allocates array buffer of size N + M and allocates new node objects.

Why Brute Force Doesn't Scale:

Array conversions allocate O(N + M) memory buffer and discard existing pointer graph.

For N = 10,000 and M = 10,000, in-place splicing requires 0 extra bytes and finishes in <0.1ms.

2. Better — Two-Pass Pointer Locator & Re-link

Intuition

Use two explicit passes: first, traverse list1 to index a - 1 to get nodeBeforeA, and continue to index b + 1 to get nodeAfterB. Second, walk list2 to its tail. Finally connect nodeBeforeA.next = list2 and tail2.next = nodeAfterB.

Algorithm

  1. Step 1: Traverse list1 with pointer prevA = list1 for a - 1 steps.
  2. Step 2: Traverse from prevA for b - a + 2 steps to reach afterB (node at index b + 1).
  3. Step 3: Traverse list2 to its last node tail2 (tail2.next == null).
  4. Step 4: Set prevA.next = list2.
  5. Step 5: Set tail2.next = afterB.
  6. Step 6: Return list1.
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* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
14 ListNode* prevA = list1;
15 for (int i = 0; i < a - 1; ++i) {
16 prevA = prevA->next;
17 }
18
19 ListNode* afterB = prevA;
20 for (int i = 0; i < b - a + 2; ++i) {
21 afterB = afterB->next;
22 }
23
24 ListNode* tail2 = list2;
25 while (tail2->next != nullptr) {
26 tail2 = tail2->next;
27 }
28
29 prevA->next = list2;
30 tail2->next = afterB;
31
32 return list1;
33 }
34};
35
36int main() {
37 ListNode* l1 = new ListNode(10);
38 l1->next = new ListNode(1);
39 l1->next->next = new ListNode(13);
40 l1->next->next->next = new ListNode(6);
41 l1->next->next->next->next = new ListNode(9);
42 l1->next->next->next->next->next = new ListNode(5);
43
44 ListNode* l2 = new ListNode(100);
45 l2->next = new ListNode(101);
46
47 Solution sol;
48 ListNode* merged = sol.mergeInBetween(l1, 3, 4, l2);
49
50 cout << "Better Pointer Merged: ";
51 for (ListNode* c = merged; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
52 cout << endl;
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(N + M) — Pass 1 traverses list1 to locate node at index a-1 and node at index b+1. Pass 2 traverses list2 to locate tail2. Total operations <= N + M.
  • Space complexity: O(1) — Uses O(1) auxiliary pointer references.

3. Optimal — Single-Pass Pointer Anchoring & Direct Splicing

Intuition

Traverse list1 with index counter idx. When idx == a - 1, record nodeA_prev. When idx == b + 1, record nodeB_next and stop scanning list1. Concurrently or sequentially walk list2 to its tail2. Wire nodeA_prev.next = list2 and tail2.next = nodeB_next.

Algorithm

  1. Step 1: Initialize curr = list1, idx = 0, prevA = null, afterB = null.
  2. Step 2: While curr != null:
  3. a. If idx == a - 1, prevA = curr.
  4. b. If idx == b + 1: afterB = curr; break.
  5. c. curr = curr.next, idx++.
  6. Step 3: Locate tail2 = list2; while tail2.next != null, tail2 = tail2.next.
  7. Step 4: Wire prevA.next = list2 and tail2.next = afterB.
  8. Step 5: Return list1.

Merge In Between Linked Lists Master Trace

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Pointers to bounds located
Visual state
Values and pointers at this exact step
linked list
prevA → 13afterB → 5
Node 13
13 (a-1)
Node 6
6
Node 9
9
Node 5
5 (b+1)
NULL
Check / comparison
Anchors found
Decision / next transition
Ready to splice
Why this step matters

Pointers to bounds located.

Step 1 / 2
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* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
14 ListNode* prevA = nullptr;
15 ListNode* afterB = nullptr;
16 ListNode* curr = list1;
17 int idx = 0;
18
19 while (curr) {
20 if (idx == a - 1) {
21 prevA = curr;
22 }
23 if (idx == b + 1) {
24 afterB = curr;
25 break;
26 }
27 curr = curr->next;
28 idx++;
29 }
30
31 ListNode* tail2 = list2;
32 while (tail2->next) {
33 tail2 = tail2->next;
34 }
35
36 prevA->next = list2;
37 tail2->next = afterB;
38
39 return list1;
40 }
41};
42
43int main() {
44 ListNode* l1 = new ListNode(10);
45 l1->next = new ListNode(1);
46 l1->next->next = new ListNode(13);
47 l1->next->next->next = new ListNode(6);
48 l1->next->next->next->next = new ListNode(9);
49 l1->next->next->next->next->next = new ListNode(5);
50
51 ListNode* l2 = new ListNode(100);
52 l2->next = new ListNode(101);
53 l2->next->next = new ListNode(102);
54
55 Solution sol;
56 ListNode* merged = sol.mergeInBetween(l1, 3, 4, l2);
57
58 cout << "Optimal Merged: ";
59 for (ListNode* c = merged; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
60 cout << endl;
61 return 0;
62}

Time & Space Complexity

  • Time complexity: O(b + M) where b <= N, M = len(list2) — Only traverses list1 up to index b+1 (saving unnecessary traversals of the rest of list1) and traverses list2 to its tail. Strictly optimal linear time.
  • Space complexity: O(1) — Modifies pointers in-place with O(1) auxiliary variables.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Array Conversion & ReconstructionO(N + M)O(N + M)Convert list1 into an array, slice out elements from a to b, insert all elements of list2 into the slice position, then construct a new linked list from the combined array.Memory allocation.
2.Better — Two-Pass Pointer TraversalO(N + M)O(1)In pass 1, find node at index a - 1 and node at index b + 1. In pass 2, traverse list2 to locate tail2. Re-link nodeA_prev.next = list2 and tail2.next = nodeB_next.Separate traversals.
3.Optimal — Single-Pass Pointer Anchoring & Direct SplicingOptimalO(N + M)O(1)Traverse list1 up to index b + 1 with a single loop, recording nodeA_prev at step a - 1 and nodeB_next at step b + 1. Concurrently or sequentially find tail2. Wire nodeA_prev.next = list2 and tail2.next = nodeB_next.Optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-one on indices

Stopping at index a instead of a - 1 cuts off the wrong node.

Forgetting to connect `tail2` to `afterB`

Connecting prevA to list2 without attaching tail2 to the remaining suffix of list1 loses the end of the list.

Re-traversing list1 from the beginning

After finding prevA, you can simply continue scanning for afterB without starting from head1 again.

Crucial Edge Cases to Validate:

  • `a == b` (Single Node Replacement) — a = 3, b = 3 -> removes only node at index 3.
  • `list2` has Single Node — list2 = [99] -> tail2 == list2, properly wires prevA -> 99 -> afterB.
  • `b` is Penultimate Node — b = list1.length - 2 -> afterB is the original tail of list1.
  • `a == 1` — prevA is head1 -> head remains unchanged.

Interview Tips & Best Practices

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

  1. Point out the constraint 1 <= a immediately: 'Since a >= 1, head1 will always be the return value.'
  2. State the 3 anchors needed: nodeA_prev (index a-1), nodeB_next (index b+1), and tail2 (last node of list2).
  3. Showcase clean O(1) space pointer manipulation.

Quick Comprehension Check

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

1.Why is a dummy head sentinel node not strictly required for this problem?

2.How many pointer assignments are needed to splice list2 into list1?

3.What is the time complexity of the optimal single-pass approach?

Back to DSA Sheet