# Merge In Between Linked Lists
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/merge-in-between-linked-lists)
Canonical: https://scaleengineer.com/dsa/problems/merge-in-between-linked-lists
**Data structures:** Linked List
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal), [Arista Networks](https://scaleengineer.com/companies/arista-networks)
---
## 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:

![](https://assets.glich.co/dsa/merge-in-between-linked-lists/image0.png) 

_Build the result list and return its head._

**Example 1:**

![](https://assets.glich.co/dsa/merge-in-between-linked-lists/image1.png) 

**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:**

![](https://assets.glich.co/dsa/merge-in-between-linked-lists/image2.png) 

**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 <= 104`
* `1 <= a <= b < list1.length - 1`
* `1 <= list2.length <= 104`

# Approaches
## Multiple Traversal Approach
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.
**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.
**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.
### Explanation
The core idea is to break the problem into three independent sub-problems:
1.  **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`.
2.  **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`.
3.  **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`.
```java
/**
 * 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) {
        // 1. Find the node at index a-1
        ListNode nodeBeforeA = list1;
        for (int i = 0; i < a - 1; i++) {
            nodeBeforeA = nodeBeforeA.next;
        }

        // 2. Find the node at index b+1
        ListNode nodeAfterB = list1;
        for (int i = 0; i < b + 1; i++) {
            nodeAfterB = nodeAfterB.next;
        }

        // 3. Find the tail of list2
        ListNode tailOfList2 = list2;
        while (tailOfList2.next != null) {
            tailOfList2 = tailOfList2.next;
        }

        // 4. Perform the merge
        nodeBeforeA.next = list2;
        tailOfList2.next = nodeAfterB;

        return list1;
    }
}
```
### 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`.

## Optimized Single Pass Approach
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.
**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.
**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.
### Explanation
This optimized approach minimizes the number of node traversals.
1.  **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`.
2.  **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`.
3.  **Connect `list1` and `list2`:** We set `startNode.next` to point to the head of `list2`.
4.  **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.
```java
/**
 * 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) {
        // 1. Traverse to the (a-1)th node
        ListNode startNode = list1;
        for (int i = 0; i < a - 1; i++) {
            startNode = startNode.next;
        }

        // 2. From startNode, find the b-th node
        ListNode endNodePredecessor = startNode;
        for (int i = 0; i < b - a + 1; i++) {
            endNodePredecessor = endNodePredecessor.next;
        }

        // 3. Connect the startNode to list2's head
        startNode.next = list2;

        // 4. Find the tail of list2
        ListNode tailOfList2 = list2;
        while (tailOfList2.next != null) {
            tailOfList2 = tailOfList2.next;
        }

        // 5. Connect list2's tail to the rest of list1
        tailOfList2.next = endNodePredecessor.next;

        return list1;
    }
}
```
### 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`.

# Solutions
### CSharp

```csharp
/** * 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 ; } }
```

### Java

```java
/** * 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 ; } }
```

### CPP

```cpp
/** * 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 ; } };
```

### Python

```python
# 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
```