Merge In Between Linked Lists - Solution & Explanation
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, 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.
In this C solution, we define a struct ListNode and operate on pointers within the linked list. First, we traverse to just before the ath position in list1 (prevA), and then traverse from there to just beyond the bth node (nodeB) in list1. After that, we link prevA to list2 and traverse to the end of list2 to link it to nodeB.
Complexity
Time Complexity: O(n + m) where n is the number of nodes in list1 up to b and m is the length of list2. Space Complexity: O(1) as we use a constant amount of auxiliary space.
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.
C does not naturally support recursive list manipulations easily, especially without introducing significant complications. Therefore, this approach is better showcased in languages with better support for recursive structures.
Complexity
Complexity details are not provided for C in recursive solutions.
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.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using Two Pointers | Time Complexity: O(n + m) where n is the number of nodes in |
| Recursive Approach | Complexity details are not provided for C in recursive solutions. |
| Simulation | — |
Detailed 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. |
Video Solution
Merge in Between Linked Lists - Leetcode 1669 - Python • NeetCodeIO • 10,861 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Merge In Between Linked Lists easy or hard?
Merge In Between Linked Lists Python/Java solution
How to solve Merge In Between Linked Lists in O(n)?
What is the best approach for Merge In Between Linked Lists?
Is Merge In Between Linked Lists asked at Google/Amazon/Meta?
What data structure is used in Merge In Between Linked Lists?
What is the time complexity of Merge In Between Linked Lists?
Ready to solve this problem?
Practice Merge In Between Linked Lists with our built-in code editor and test cases.
Practice on FleetCode