Merge In Between Linked Lists solution and explanation
Google
9 more videos on this problem
Merge in Between Linked Lists - Leetcode 1669 - PythonNeetCodeIO · 6:22 · 10K views
1669. Merge In Between Linked Lists | Merge Linked ListAryan Mittal · 9:31 · 1K views
LEETCODE #1669 Merge In Between Linked Lists C++ solution ExplainedMr. Logic · 6:01 · 1K views
1669. Merge In Between Linked Lists (Leetcode Medium)Programming Live with Larry · 6:52 · 889 views
LeetCode 1669 Merge In Between Linked Lists (Medium Complexity Problem)AlgorithmicIQ · 10:39 · 353 views
LeetCode #1669 - Merge In Between Linked Lists: Linked ListsGDSC FIU · 9:17 · 318 views
Leetcode Problem 1669 Solution | Merge In Between Linked Lists | Explanation in HinglishSoftWiz Circle · 11:59 · 123 views
1669. Merge In Between Linked Lists | Google | Linked List | Easy Explanation | LeetcodeRapid Syntax · 10:00 · 58 views
LeetCode 1669 - Merge In Between Linked Lists - PythonAlpha-Code · 9:10 · 54 views
LeetCode 1669 | Merge In Between Linked Lists | Python Solution Explained | AlgoYogiAlgo Yogi · 13:55 · 31 views
The problem
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, and put list2 in their place.
The blue edges and nodes in the following figure indicate the result:
Build the result list and return its head.
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: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.
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: The blue edges and nodes in the above figure indicate the result.
Constraints:
3 <= list1.length <= 1041 <= a <= b < list1.length - 11 <= list2.length <= 104
Approach overview
Problem Overview: You are given two linked lists. In the first list, remove nodes from index a to b (inclusive) and insert the entire second list in that position. The task is to reconnect pointers so that list2 replaces that segment of list1 without creating new nodes.
Approach 1: Using Two Pointers (O(n) time, O(1) space)
This approach walks through list1 to find two critical nodes: the node right before index a and the node right after index b. Use iteration with a counter while maintaining pointers to these boundaries. Once found, connect the a-1 node to the head of list2, then traverse list2 to locate its tail. Finally connect that tail to the node after index b. The algorithm performs only pointer rewiring—no node copying or extra data structures—so the space complexity stays O(1). Time complexity is O(n + m), where n is the length of list1 and m is the length of list2. This pattern is common in two pointer linked list manipulation problems where you track boundaries and reconnect segments.
The key insight is that you never need to rebuild the list. You only identify the node before the cut and the node after the cut. Once those are known, the entire merge reduces to two pointer assignments. This keeps the algorithm linear and extremely memory efficient.
Approach 2: Recursive Approach (O(n + m) time, O(n) space)
A recursive strategy processes list1 node by node while keeping track of the current index. When the recursion reaches index a, instead of continuing down the original list, it returns the head of list2. The recursion skips nodes until index b and reconnects the tail of list2 with the remainder of list1. Conceptually this mirrors how recursion naturally rebuilds linked structures during stack unwinding.
This approach still visits each node once, giving O(n + m) time complexity. However, recursion introduces call stack overhead, so the auxiliary space becomes O(n). It is mainly useful for understanding structural transformations in linked lists and practicing pointer manipulation using recursion. In production or interview settings, iterative solutions are usually preferred for their constant space usage.
Recommended for interviews: The two-pointer approach is what interviewers typically expect. It shows you understand how to locate boundaries in a linked list and reconnect segments efficiently. Implementing it in O(n + m) time with O(1) extra space demonstrates strong pointer manipulation skills. Discussing the recursive version can still be useful to show deeper understanding of linked list transformations, but the iterative two-pointer method is the optimal and most practical solution.
Approach 1: Using Two Pointers
This approach involves using two pointers to identify the nodes in list1 where list2 will be inserted.
First, traverse list1 to reach the node right before the ath node. Next, continue to traverse to just beyond the bth node. The node at this position serves as the connection to the remainder of list1 after the insertion point.
Finally, link the identified nodes with list2.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeInBetween(list1, a, b, list2):
prevA = list1
for _ in range(a - 1):
prevA = prevA.next
nodeB = prevA
for _ in range(b - a + 2):
nodeB = nodeB.next
prevA.next = list2
tail = list2
while tail.next:
tail = tail.next
tail.next = nodeB
return list1class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public class Solution {
public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
ListNode prevA = list1;
for (int i = 0; i < a - 1; i++) {
prevA = prevA.next;
}
ListNode nodeB = prevA;
for (int i = 0; i < b - a + 2; i++) {
nodeB = nodeB.next;
}
prevA.next = list2;
ListNode tail = list2;
while (tail.next != null) {
tail = tail.next;
}
tail.next = nodeB;
return list1;
}
}#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
ListNode* prevA = list1;
for (int i = 0; i < a - 1; ++i) {
prevA = prevA->next;
}
ListNode* nodeB = prevA;
for (int i = 0; i < b - a + 2; ++i) {
nodeB = nodeB->next;
}
prevA->next = list2;
while (list2->next != nullptr) {
list2 = list2->next;
}
list2->next = nodeB;
return list1;
}function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
var mergeInBetween = function(list1, a, b, list2) {
let prevA = list1;
for (let i = 0; i < a - 1; i++) {
prevA = prevA.next;
}
let nodeB = prevA;
for (let i = 0; i < b - a + 2; i++) {
nodeB = nodeB.next;
}
prevA.next = list2;
let tail = list2;
while (tail.next !== null) {
tail = tail.next;
}
tail.next = nodeB;
return list1;
};#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* mergeInBetween(struct ListNode* list1, int a, int b, struct ListNode* list2) {
struct ListNode* prevA = list1;
for (int i = 0; i < a - 1; i++) {
prevA = prevA->next;
}
struct ListNode* nodeB = prevA;
for (int i = 0; i < b - a + 2; i++) {
nodeB = nodeB->next;
}
prevA->next = list2;
while (list2->next != NULL) {
list2 = list2->next;
}
list2->next = nodeB;
return list1;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode MergeInBetween(ListNode list1, int a, int b, ListNode list2) {
ListNode prevA = list1;
for (int i = 0; i < a - 1; i++) {
prevA = prevA.next;
}
ListNode nodeB = prevA;
for (int i = 0; i < b - a + 2; i++) {
nodeB = nodeB.next;
}
prevA.next = list2;
ListNode tail = list2;
while (tail.next != null) {
tail = tail.next;
}
tail.next = nodeB;
return list1;
}
}This Python solution performs similar operations to other solutions. Pointers prevA and nodeB help link the non-replaced parts of list1 with list2.
Time Complexity: O(n + m) where n is the number of nodes traversed in list1 up to b, and m is the length of list2. Space Complexity: O(1).
Approach 2: Recursive Approach
This approach solves the problem recursively, leveraging recursive traversal to reach the split points on list1 and link list2 in the required section of list1.
Base cases are established for when the algorithm should stop the recursive calls and perform actions to connect the segments together.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeInBetween(list1, a, b, list2):
if a == 0:
nodeB = list1
for _ in range(b + 1):
nodeB = nodeB.next
tail = list2
while tail.next:
tail = tail.next
tail.next = nodeB
return list2
list1.next = mergeInBetween(list1.next, a - 1, b - 1, list2)
return list1// Java's recursion stack would be similarly inefficient for deep recursions; generally, iterations or a different structural recursion method is preferred.#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
if ((b - a + 1) == 0) {
return list2;
}
if (a > 0) {
list1->next = mergeInBetween(list1->next, a - 1, b - 1, list2);
return list1;
}
ListNode* nodeAfterB = list1;
for (int i = 0; i <= b; ++i) {
nodeAfterB = nodeAfterB->next;
}
ListNode* tail = list2;
while (tail->next != NULL) {
tail = tail->next;
}
tail->next = nodeAfterB;
return mergeInBetween(list1->next, a - 1, 0, list2);
}function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
function mergeInBetween(list1, a, b, list2) {
if (a === 0) {
while (b-- > 0) {
list1 = list1.next;
}
let tail = list2;
while (tail.next !== null) {
tail = tail.next;
}
tail.next = list1.next;
return list2;
}
list1.next = mergeInBetween(list1.next, a - 1, b - 1, list2);
return list1;
}// C does not directly support recursive list manipulations naturally, so this language is skipped for this approach.// Similar issues in recursion depth and possible stack overflow should be noted in languages like C#. Recursive approach is therefore not provided.This Python solution uses recursion and reduces the problem size with each call, moving closer to the base case where list2 is directly connected.
Time Complexity: O(n + m), where n is the nodes in list1 up to b and m is the length of list2. Space Complexity: O(n) for recursion depth in the call stack.
Approach 3: Simulation
We can directly simulate the operations described in the problem.
In the implementation, we use two pointers p and q, both initially pointing to the head node of list1.
Then we move pointers p and q forward, until pointer p points to the node before the a-th node in list1, and pointer q points to the b-th node in list1. At this point, we set the next pointer of p to the head node of list2, and set the next pointer of the tail node of list2 to the node pointed to by the next pointer of q. This completes the operation required by the problem.
The time complexity is O(m + n), and the space complexity is O(1). Where m and n are the lengths of list1 and list2 respectively.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function mergeInBetween(
list1: ListNode | null,
a: number,
b: number,
list2: ListNode | null,
): ListNode | null {
let p = list1;
let q = list1;
while (--a > 0) {
p = p.next;
}
while (b-- > 0) {
q = q.next;
}
p.next = list2;
while (p.next) {
p = p.next;
}
p.next = q.next;
q.next = null;
return list1;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
p, q := list1, list1
for ; a > 1; a-- {
p = p.Next
}
for ; b > 0; b-- {
q = q.Next
}
p.Next = list2
for p.Next != nil {
p = p.Next
}
p.Next = q.Next
q.Next = nil
return list1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Two Pointers | Time Complexity: O(n + m) where n is the number of nodes traversed in |
| Recursive Approach | Time Complexity: O(n + m), where n is the nodes in |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers | O(n + m) | O(1) | Best general solution. Efficient pointer manipulation with constant extra memory. |
| Recursive Approach | O(n + m) | O(n) | Useful for conceptual understanding of linked list reconstruction but uses call stack space. |
Frequently asked questions
Is Merge In Between Linked Lists easy or hard?
Merge In Between Linked Lists is categorized as a Medium problem. The main challenge is correctly identifying the nodes around indices a and b and reconnecting the pointers without breaking the list structure.
Merge In Between Linked Lists Python/Java solution
Most implementations iterate through list1 to find the boundary nodes, then connect list2 in place. The same logic works across Python, Java, C++, C#, and JavaScript because the solution relies on pointer references rather than language-specific libraries.
How to solve Merge In Between Linked Lists in O(n)?
Iterate through list1 to find the node just before index a and the node just after index b. Attach the head of list2 to the first boundary node, then find the tail of list2 and connect it to the node after b. This uses constant extra space and linear traversal.
What is the best approach for Merge In Between Linked Lists?
The best approach uses two pointers to locate the node before index a and the node after index b in list1. Connect the first node to the head of list2, then attach the tail of list2 to the remaining part of list1. This runs in O(n + m) time and O(1) space because it only rewires pointers.
Is Merge In Between Linked Lists asked at Google/Amazon/Meta?
Linked list pointer manipulation problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variants that involve cutting and reconnecting list segments are common because they test pointer reasoning and edge case handling.
What data structure is used in Merge In Between Linked Lists?
The problem uses singly linked lists. The main operations involve pointer traversal, locating specific indices, and reconnecting nodes without allocating additional data structures.
What is the time complexity of Merge In Between Linked Lists?
The optimal solution runs in O(n + m) time, where n is the length of list1 and m is the length of list2. You traverse list1 to locate the boundaries around indices a and b, and traverse list2 once to find its tail before reconnecting it.