1669. Merge In Between Linked Lists
Problem Description
In this problem, we are given two singly-linked lists called list1
and list2
. The sizes of these lists are n
and m
respectively. The goal is to modify list1
by removing a segment of its nodes, specifically the nodes from the a
th position to the b
th position (assuming the first node is at position 0). Following the removal of this segment, list2
is then inserted into list1
at the cut point. In other words, list1
should be continued by list2
starting at the a
th node, and after the last node of list2
, the continuation should be the rest of list1
starting from the node right after the b
th position. The task is to complete this operation and return the head of the updated list1
.
To visualize, imagine list1
as a chain of nodes and we are to clip out a section of this chain from a
to b
, then attach a new chain (list2
) in its place, and finally reattach the remaining part of the original list1
after list2
.
Intuition
To achieve the merge described in the problem, the solution involves a few key steps executed in sequence. The first step is to find the node just before the a
th node in list1
; let's call this the preA
node. We also need to find the b
th node itself because its next node is where we want to eventually connect the tail of list2
. Let's refer to the b
th node's next node as postB
. To navigate to these nodes, we can start at the head of list1
and traverse it while counting the nodes until we reach the desired positions.
Once we have preA
and postB
, we disconnect the nodes from preA
until postB
, effectively removing the segmented list between a
and b
. Now preA
's next node is set to the head of list2
, linking the start of list2
to the front portion of list1
.
Next, we traverse to the end of list2
since we need to connect the tail of list2
to the postB
node. After reaching the end of list2
, we set the next node to postB
.
The merge is complete at this point, and we return the head of the modified list1
. The essence of the solution is to splice the arrays by reassigning the next
pointers of the nodes in list1
, to incorporate the entirety of list2
and then reconnect list1
.
Handling the node connections properly and ensuring no nodes are lost in the process are crucial parts of the solution.
Learn more about Linked List patterns.
Solution Approach
The merger of the two lists is achieved via a step-by-step approach:
-
Initialize Pointers: We start by initializing two pointers
p
andq
to the head oflist1
. These pointers will help us traverse the list. -
Find
preA
Node: Thep
pointer is used to find the node just before thea
th position (thepreA
node). We use a simple loop that traverses the lista-1
times. The loopfor _ in range(a - 1)
moves thep
pointer to the correct spot. -
Find
postB
Node: Similarly, theq
pointer is aimed at finding the node at theb
th position. Because we're already at the head oflist1
(position 0), we only need to moveb
times to reach this node, hence the loop:for _ in range(b)
. -
Detach & Connect: The
next
pointer ofp
is then set to the head oflist2
, effectively detaching thelist1
segment betweena
andb
, and linking the beginning oflist2
tolist1
. -
Traverse
list2
: Now, we need to find the end oflist2
. We continue to movep
forward with the loopwhile p.next
. When this loop exits,p
is at the last node oflist2
. -
Reattach Remaining
list1
: The next pointer of the last node oflist2
(now atp
) is connected toq.next
, which is the node immediately following theb
th node inlist1
(thepostB
node). This is done withp.next = q.next
. -
Complete and Return: The
q.next
is then pointed toNone
to detach the removed segment from the rest of the list, which is a good practice to avoid potential memory leaks in some environments. Finally, the head of the modified list (which is stilllist1
) is returned.
Here's a breakdown of key patterns used:
- Two-pointer technique: Used to locate the nodes before and after the removed segment.
- Traversal: An essential operation for navigating linked lists.
- Link manipulation: The core logic revolves around correctly adjusting the
next
properties of the nodes to "stitch" the lists together.
This approach guarantees the merger without allocating new nodes, operating in-place within the given data structures. It also ensures we only traverse each list once, making the algorithm efficient with O(n + m) time complexity, where n
and m
are the lengths of list1
and list2
, respectively.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example where list1
= 1 -> 2 -> 3 -> 4 -> 5 and list2
= 100 -> 101. Suppose we want to replace nodes in positions a = 1
to b = 2
of list1
with list2
.
-
Initialize Pointers: We start by setting
p
andq
to the head oflist1
, which is the node with value1
. -
Find
preA
Node: We need to find the node just before thea
th position (thepreA
node). We movep
one step becausea - 1 = 0
. So,p
now points to node1
. -
Find
postB
Node: To locate thepostB
node, we setq
to the head oflist1
and move itb
steps. After moving 2 steps,q
points to node3
. -
Detach & Connect: We set the next of node
1
(preA.next
) to the head oflist2
(node100
). Nowlist1
starts as 1 -> 100 -> 101. -
Traverse
list2
: We movep
throughlist2
to the end. Aslist2
has two nodes,p
will now point to node101
. -
Reattach Remaining
list1
: Setp.next
(currentlyp
is at101
oflist2
) toq.next
(q
is at3
oflist1
), so thatlist1
now is 1 -> 100 -> 101 -> 3 -> 4 -> 5. -
Complete and Return: Set
q.next
toNone
, detaching the removed segment (in this case, not needed asq.next
already points to the correct segment). The head oflist1
remains the first node with value1
, so we returnlist1
.
Following this example, list1
will be transformed into 1 -> 100 -> 101 -> 3 -> 4 -> 5 after the operation, which demonstrates the solution approach in action.
Solution Implementation
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
8 # Initialize two pointers to the head of list1
9 prev_node_of_sublist = curr_node = list1
10
11 # Move prev_node_of_sublist to the node just before position 'a'
12 for _ in range(a - 1):
13 prev_node_of_sublist = prev_node_of_sublist.next
14
15 # Move curr_node to the node at position 'b'
16 for _ in range(b):
17 curr_node = curr_node.next
18
19 # Connect the node before 'a' with the head of list2
20 prev_node_of_sublist.next = list2
21
22 # Traverse to the end of list2 to find the last node
23 while prev_node_of_sublist.next:
24 prev_node_of_sublist = prev_node_of_sublist.next
25
26 # Connect the last node of list2 with the node after 'b' in list1
27 prev_node_of_sublist.next = curr_node.next
28
29 # The node at position 'b' no longer has any references and can be collected by garbage collector
30
31 # Return the merged list starting with list1's head
32 return list1
33
1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * int val;
5 * ListNode next;
6 * ListNode() {}
7 * ListNode(int val) { this.val = val; }
8 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11class Solution {
12 public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
13 // Initial pointers to help with node traversal.
14 ListNode beforeA = list1; // Pointer to the node just before position 'a'.
15 ListNode afterB = list1; // Pointer to the node just after position 'b'.
16
17 // Move the 'beforeA' pointer to the node just before the 'a' position.
18 for (int i = 0; i < a - 1; i++) {
19 beforeA = beforeA.next;
20 }
21
22 // Move the 'afterB' pointer to the node just after the 'b' position.
23 for (int i = 0; i < b; i++) {
24 afterB = afterB.next;
25 }
26
27 // Connect the 'beforeA' node to the start of list2.
28 beforeA.next = list2;
29
30 // Traverse list2 to the end.
31 ListNode endOfList2 = beforeA.next; // Start from the first node of list2
32 while (endOfList2.next != null) {
33 endOfList2 = endOfList2.next;
34 }
35
36 // Connect the end of list2 to the 'afterB' node, effectively skipping 'a' to 'b' in list1.
37 endOfList2.next = afterB.next;
38
39 // 'afterB.next' should be null to ensure we don't retain unwanted references.
40 afterB.next = null;
41
42 return list1; // Return the modified list1.
43 }
44}
45
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode() : val(0), next(nullptr) {}
7 * ListNode(int x) : val(x), next(nullptr) {}
8 * ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11
12class Solution {
13public:
14 ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
15 // Pointers to manage the positions in list1
16 ListNode* prevNode = list1; // Pointer to track the node before the 'a' position
17 ListNode* nextNode = list1; // Pointer to track the node at the 'b' position
18
19 // Move the prevNode pointer to the node just before the node at position 'a'
20 for (int i = 1; i < a; ++i) {
21 prevNode = prevNode->next;
22 }
23
24 // Move the nextNode pointer to the node at position 'b'
25 for (int i = 0; i <= b; ++i) {
26 nextNode = nextNode->next;
27 }
28
29 // Attach the start of list2 to where 'a' was in list1
30 prevNode->next = list2;
31
32 // Traverse list2 until the end
33 while (prevNode->next) {
34 prevNode = prevNode->next;
35 }
36
37 // Connect the end of list2 to the node just after 'b' in list1
38 prevNode->next = nextNode;
39
40 // The next node of 'b' position is now isolated, and we do not need to set it to nullptr
41
42 // Return the modified list1 with list2 merged in between
43 return list1;
44 }
45};
46
1/**
2 * Merges one linked list into another between the indices `a` and `b`. The nodes after `b`
3 * are reconnected to the end of `list2`.
4 * @param {ListNode | null} list1 - The first linked list.
5 * @param {number} a - The start index for the merge.
6 * @param {number} b - The end index for the merge.
7 * @param {ListNode | null} list2 - The second linked list to be merged.
8 * @returns {ListNode | null} - The merged linked list.
9 */
10function mergeInBetween(
11 list1: ListNode | null,
12 a: number,
13 b: number,
14 list2: ListNode | null
15): ListNode | null {
16 // `preMergeNode` will eventually point to the node just before 'a'.
17 let preMergeNode = list1;
18 // `postMergeNode` will eventually point to the node just after 'b'.
19 let postMergeNode = list1;
20
21 // Find the `(a-1)`th node, to connect list2 to its next.
22 while (--a > 0) {
23 preMergeNode = preMergeNode!.next;
24 }
25
26 // Find the `b`th node, which list2 will be connected before.
27 while (b-- > 0) {
28 postMergeNode = postMergeNode!.next;
29 }
30
31 // Connect list2 to the next of `preMergeNode`.
32 preMergeNode!.next = list2;
33
34 // Iterate to the last node of list2.
35 while (preMergeNode!.next) {
36 preMergeNode = preMergeNode!.next;
37 }
38
39 // Connect the last node of list2 to the node after `postMergeNode`.
40 preMergeNode!.next = postMergeNode!.next;
41 // Not necessary to nullify `postMergeNode.next` as it will not affect the resultant list.
42 return list1;
43}
44
Time and Space Complexity
Time Complexity
The given code consists of a few steps. Here is the analysis of each:
-
Advanced
p
pointera - 1
times: The time complexity isO(a)
because it requires one operation for each step until reaching thea-th
node. -
Advanced
q
pointerb
times: The time complexity isO(b)
because it traverses the linked list from the start until reaching theb-th
node. -
Connecting
list1
tolist2
: The operation is constant time,O(1)
, since it's a matter of single assignments. -
Traversing
list2
to find the end: In the worst case,list2
hasn
nodes, making this operationO(n)
, wheren
is the number of nodes inlist2
. -
Connecting the end of
list2
toq.next
: This is another constant time operation,O(1)
.
Adding these up, assuming n
is the number of nodes in the second list and a
and b
are the positions in the first list, the overall time complexity would be O(a) + O(b) + O(n) + O(1) + O(1)
, which simplifies to O(a + b + n)
.
Space Complexity
The space complexity is O(1)
because the code only uses a fixed number of pointers (p
and q
) and does not allocate extra space that grows with the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the relationship between a tree and a graph?
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!