Merge Linked List in Between Another Linked List || Beats 100%
IntuitionThe problem requires merging a second linked list (list2) into a first linked list (list1) by replacing the segment between indices a and b. The goal i
# Intuition
The problem requires merging a second linked list (list2) into a first linked list (list1) by replacing the segment between indices a and b. The goal is to identify the nodes before and after this segment, attach list2 in place of the removed nodes, and return the modified list.

# Approach
Find the Tail of list2: Traverse list2 to reach its last node.

Locate the a-1 and b+1 Nodes in list1:

Traverse list1 while keeping track of the node at index a-1 (let’s call it an).

Continue traversing until index b+1 to get the node after b.

Modify Pointers to Merge Lists:

Set an.next = list2 to connect list1 to list2.

Set the last node of list2 to point to the node at index b+1 of list1.

# Complexity
- Time complexity:
$$O(N+M)$$
O(M) for traversing list2 to find its tail.
O(N) for traversing list1 to locate a-1 and b+1.

- Space complexity:
$$O(1)$$
Only a few extra pointers are used, independent of input size.

# Code
```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 an=null;
        ListNode temp=list2;
        while(temp.next!=null){
            temp=temp.next;
        }
        ListNode t=list1;
        int i=0;
        while(i<b+1){
            if(i==a-1){
                an=t;
            }
            t=t.next;
            i++;
        }
        temp.next=t;
        an.next=list2;
        return list1;

    }
}
```
['Java']