Last Updated: 24 Sep, 2021

Day 22 : Merge In Between

Moderate

Asked in companies

Solve now

Problem statement

You are given two linked lists, ’head1’ and ‘head2’ of size ‘N’ and ‘M’. You are also provided with two integers, ‘X’ and ‘Y’, and your task is to remove the first Linked List’s nodes from index ‘X’ to ‘Y’ and insert all the nodes of the second Linked List in their place.

You need to return the head of the merged Linked List.

For example:

If the first list is: [0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL], the second list is: [10 -> 20 -> 30 -> NULL], ‘X’ = 2 and ‘Y’ = 4 then if we remove nodes from index 2 to 4, and after inserting the second list at index 2 then the final list will be: [0 -> 1 -> 10 -> 20 -> 30 -> 5 -> NULL].

Input Format:

The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains two space-separated integers denoting the value of ‘X’ and ‘Y’.

The second line of each test case contains space-separated integers denoting the values of the first Linked List nodes. The Linked List is terminated with -1. 

The third line of each test case contains space-separated integers denoting the values of the second Linked List nodes. The Linked List is terminated with -1.

Output Format:

For each test case, print the final linked list in a single line in a space-separated manner.

Print the output of each test case in a separate line.

Constraints:

1 <= T <= 10
3 <= N <= 10 ^ 6
1 <= M <= 10 ^ 6
-10^9 <= Node.Data <= 10^9 and Node.Data != -1
1 <= X <= Y < N - 1

The linked list is 0-indexed.

Time Limit: 1 sec

Note:

You do not need to input or print anything, as it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

In this approach, we will use two pointers, prev1 and prev2. We will set prev1 to the node at index (X - 1) in the first Linked LIst and prev2 to the node at index Y in the first Linked List. We will remove the link between nodes at index X - 1 and X and between nodes at index Y and Y - 1 by creating a link between prev1 with the head of the second Linked List(prev2 -> head2) and the tail of the second linked list with the prev2.next(tail.next -> prev2.next). Thus, removing the first Linked List’s nodes from index X to Y and putting the second list in their place.

Algorithm:

Initialize a variable prev1 with value head1
Initialize a variable prev2 with value head1
Initialize a variable i with value 0
Iterate while i is less than x - 1
- prev1 = prev1.next
- Increment i by 1
Set i as 0
Iterate while i is less than y
- prev2 = prev2.next
- Increment i by 1
Initialize a variable tail with value head2
Iterate while tail.next is not null
- tail = tail.next
Set prev1.next as head2
Set tail.next as prev2.next
Finally, return head1

Solve now