Day 22 : Merge In Between

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
10 upvotes
Asked in companies
AppleAmazonVMware Inc

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].
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
2 4
0 1 2 3 4 5 -1
10 20 30 -1
3 3
0 1 3 8 11 -1
7 9 -1
Sample Output 1:
0 1 10 20 30 5 -1 
0 1 3 7 9 11 -1
Explanation:
For the first test case, if we remove nodes from index 2 to 4 and after inserting the second list at the index 2 then the final list will be: [0 -> 1 -> 10 -> 20 -> 30 -> 5 -> NULL].

For the second test case, if we remove node at index 3, and after inserting second list at the index 3 then the final list will be: [0 -> 1 -> 3 -> 7 -> 9 -> 11  -> NULL].
Sample Input 2:
2
2 3 
-2 3 5 -7 9 -1
0 0 0 -1
3 4 
3 4 5 2 6 7 -1
9 -1
Sample Output 2:
-2 3 0 0 0 9 -1
3 4 5 9 7 -1
Hint

Use pointers to keep track of previous nodes.

Approaches (1)
Iterative 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
Time Complexity

O(N + M), where N and M are the numbers of nodes in the first Linked List and second Linked List.
 

We are iterating through the first Linked List twice, first to set prev1 at index x -1 and the second to set prev2 at index y. Also, we are iterating the second Linked List once to find the last node of this list. Hence the overall time complexity is O(N + M).

Space Complexity

O(1).
 

Constant space is being used. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Day 22 : Merge In Between
Full screen
Console