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 <= 104The key idea in Merge In Between Linked Lists is to splice one linked list into another by carefully adjusting pointers. You are given two indices a and b that mark the segment of the first list to be removed. The goal is to replace that segment with the entire second linked list.
The optimal approach is to traverse the first linked list to locate two critical nodes: the node just before position a and the node just after position b. Once these nodes are identified, connect the node before a to the head of the second list. Then traverse the second list to find its tail and attach it to the node after b.
This method relies purely on pointer manipulation and a few linear traversals. The process runs in O(n + m) time, where n and m are the lengths of the two lists, and requires O(1) extra space since the merge happens in-place.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Pointer traversal and in-place merge | O(n + m) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Check which edges need to be changed.
Let the next node of the (a-1)th node of list1 be the 0-th node in list 2.
Let the next node of the last node of list2 be the (b+1)-th node in list 1.
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.
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.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int val=0, ListNode next=null) {
5 this.val = val;
6 this.next = next;
7 }
8}
9
10public class Solution {
11 public ListNode MergeInBetween(ListNode list1, int a, int b, ListNode list2) {
12 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 C# solution traverses list1 using two pointers, similar to the previous solutions. It finds a position before and after where list2 should be inserted, ensuring the rest of list1 remains connected.
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.
Complexity details are not provided for C in recursive solutions.
1
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);
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, linked list manipulation problems like Merge In Between Linked Lists are common in technical interviews, including FAANG-style interviews. They test understanding of pointers, traversal, and in-place list modification.
The time complexity is O(n + m), where n is the length of the first linked list and m is the length of the second linked list. You traverse the first list to find the cut points and the second list to find its tail.
A singly linked list is the primary data structure used for this problem. Since the task involves removing and reconnecting nodes, pointer manipulation in linked lists makes the operation efficient without needing extra memory.
The optimal approach is to traverse the first linked list to find the node just before index a and the node just after index b. Then connect the first node to the head of the second list and link the tail of the second list to the node after b. This efficiently replaces the segment using pointer manipulation.
This C++ solution employs recursion to perform the list insertion. It recursively advances along list1 until reaching the position where list2 is linked. Once recursion reaches the insertion point, it begins linking list2 and the node after b.