Merge In Between Linked Lists

Med

#1531Time: O(n + m), where `n` is the length of `list1` and `m` is the length of `list2`. Specifically, the complexity is O(a + b + m). Finding `nodeBeforeA` takes O(a) time, finding `nodeAfterB` takes O(b) time, and finding the tail of `list2` takes O(m) time. Since `a < b < n`, the total time is dominated by O(b + m).Space: O(1), as we only use a few extra pointers to store the nodes, regardless of the input size.2 companies

Data structures

Linked List

Companies

PayPal Arista Networks

Prompt

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

Remove list1's nodes from the a^th node to the b^th 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 <= 10⁴
1 <= a <= b < list1.length - 1
1 <= list2.length <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

This straightforward approach involves traversing the linked lists multiple times to identify the key nodes for the merge operation. We perform separate traversals to find: the node just before the segment to be removed, the node immediately following the segment, and the tail of the list to be inserted. While easy to conceptualize, it's less efficient due to redundant traversals.

Algorithm

Create a pointer nodeBeforeA and traverse list1 for a-1 steps to find the node at index a-1.
Create another pointer nodeAfterB and traverse list1 from the head again for b+1 steps to find the node at index b+1.
Create a pointer tailOfList2 and traverse list2 to its end.
Connect nodeBeforeA.next to the head of list2.
Connect tailOfList2.next to nodeAfterB.
Return the head of list1.

Walkthrough

The core idea is to break the problem into three independent sub-problems:

Find the (a-1)-th node: Traverse list1 from the beginning to locate the node at index a-1. Let's call this nodeBeforeA. This node's next pointer will eventually point to the head of list2.
Find the (b+1)-th node: Traverse list1 again from the beginning to find the node at index b+1. Let's call this nodeAfterB. This node will be connected to the tail of list2.
Find the tail of list2: Traverse list2 from its head to its last node. Let's call this tailOfList2. Once these three nodes are identified, the merging is a simple matter of reassigning pointers: nodeBeforeA.next is set to list2, and tailOfList2.next is set to nodeAfterB.

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        // 1. Find the node at index a-114        ListNode nodeBeforeA = list1;15        for (int i = 0; i < a - 1; i++) {16            nodeBeforeA = nodeBeforeA.next;17        }18 19        // 2. Find the node at index b+120        ListNode nodeAfterB = list1;21        for (int i = 0; i < b + 1; i++) {22            nodeAfterB = nodeAfterB.next;23        }24 25        // 3. Find the tail of list226        ListNode tailOfList2 = list2;27        while (tailOfList2.next != null) {28            tailOfList2 = tailOfList2.next;29        }30 31        // 4. Perform the merge32        nodeBeforeA.next = list2;33        tailOfList2.next = nodeAfterB;34 35        return list1;36    }37}

Complexity

Time

O(n + m), where `n` is the length of `list1` and `m` is the length of `list2`. Specifically, the complexity is O(a + b + m). Finding `nodeBeforeA` takes O(a) time, finding `nodeAfterB` takes O(b) time, and finding the tail of `list2` takes O(m) time. Since `a < b < n`, the total time is dominated by O(b + m).

Space

O(1), as we only use a few extra pointers to store the nodes, regardless of the input size.

Trade-offs

Pros

The logic is simple and easy to follow as each major step is handled independently.

Cons

This approach is inefficient because it traverses list1 from the beginning multiple times. The nodes from index 0 to a-1 are visited twice, leading to unnecessary operations.

A more efficient method is to find the required connection points in list1 within a single pass. We first traverse to the node before the removal section (a-1). From that point, we continue traversing to find the end of the removal section (b). This avoids restarting the traversal from the head, reducing the total number of steps and making the solution faster.

Algorithm

Initialize a pointer startNode to list1 and traverse a-1 nodes. startNode is now at index a-1.
Initialize another pointer endNodePredecessor to startNode. Traverse b - a + 1 more nodes. endNodePredecessor is now at index b.
Set startNode.next to point to the head of list2.
Traverse list2 to find its tail, tailOfList2.
Set tailOfList2.next to endNodePredecessor.next, which is the node at index b+1.
Return the head of list1.

Walkthrough

This optimized approach minimizes the number of node traversals.

Locate the start of the merge point: We traverse list1 for a-1 steps to find the node just before the section to be removed. Let's call this startNode.
Locate the end of the merge point: Starting from startNode, we traverse b - a + 1 more steps. Let's call the pointer we use for this traversal endNodePredecessor. After this traversal, endNodePredecessor will be at node b. The portion of list1 that needs to be kept starts at endNodePredecessor.next.
Connect list1 and list2: We set startNode.next to point to the head of list2.
Find list2's tail and connect: We traverse list2 to find its last node. Then, we connect this last node's next pointer to endNodePredecessor.next. This way, we traverse list1 only up to the b-th node once.

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        // 1. Traverse to the (a-1)th node14        ListNode startNode = list1;15        for (int i = 0; i < a - 1; i++) {16            startNode = startNode.next;17        }18 19        // 2. From startNode, find the b-th node20        ListNode endNodePredecessor = startNode;21        for (int i = 0; i < b - a + 1; i++) {22            endNodePredecessor = endNodePredecessor.next;23        }24 25        // 3. Connect the startNode to list2's head26        startNode.next = list2;27 28        // 4. Find the tail of list229        ListNode tailOfList2 = list2;30        while (tailOfList2.next != null) {31            tailOfList2 = tailOfList2.next;32        }33 34        // 5. Connect list2's tail to the rest of list135        tailOfList2.next = endNodePredecessor.next;36 37        return list1;38    }39}

Complexity

Time

O(n + m), where `n` is the length of `list1` and `m` is the length of `list2`. The complexity is specifically O(b + m). We traverse `list1` up to the `b`-th node once (which takes `b` steps in total) and traverse all of `list2` once (which takes `m` steps). This is more efficient than the multiple traversal approach as it avoids redundant steps.

Space

O(1), as we only use a constant amount of extra space for pointers.

Trade-offs

Pros

More efficient in terms of constant factors as it avoids re-traversing the initial part of list1.
The logic is still clear and directly implements the required pointer manipulations.

Cons

No significant cons, as this is the optimal approach for this problem.

Solutions

Solution

1/** * Definition for singly-linked list. * 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 p = list1 , q = list1 ; while (-- a > 0 ) { p = p . next ; } while ( b -- > 0 ) { q = q . next ; } p . next = list2 ; while ( p . next != null ) { p = p . next ; } p . next = q . next ; q . next = null ; return list1 ; } }

1/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeInBetween ( ListNode list1 , int a , int b , ListNode list2 ) { ListNode p = list1 , q = list1 ; while (-- a > 0 ) { p = p . next ; } while ( b -- > 0 ) { q = q . next ; } p . next = list2 ; while ( p . next != null ) { p = p . next ; } p . next = q . next ; q . next = null ; return list1 ; } }

1/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * mergeInBetween ( ListNode * list1 , int a , int b , ListNode * list2 ) { auto p = list1 , q = list1 ; while ( -- a ) { p = p -> next ; } while ( b -- ) { q = q -> next ; } p -> next = list2 ; while ( p -> next ) { p = p -> next ; } p -> next = q -> next ; q -> next = nullptr ; return list1 ; } };

1# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def mergeInBetween ( self , list1 : ListNode , a : int , b : int , list2 : ListNode ) -> ListNode : p = q = list1 for _ in range ( a - 1 ): p = p . next for _ in range ( b ): q = q . next p . next = list2 while p . next : p = p . next p . next = q . next q . next = None return list1

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem