Interweave Nodes

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
14 upvotes
Asked in company
Amazon

Problem statement

You have been given two singly linked lists of length 'N1' and 'N2' respectively. Your task is to modify them by interweaving alternate nodes of the two linked lists. If one list is smaller than the other, complete the process using another linked list.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T' representing the number of Test cases.
The next '2*T' lines denote the 'T' test cases. Each test case consists of two lines.

The first line of each test case contains the first linked list separated by space and terminated by -1.

The second line of each test case contains a second linked list separated by space and terminated by -1.
Output Format : 
For each test case, print two lines denoting a single space-separated modified linked list by interweaving alternate nodes of the two linked lists.


The output of each test case will be printed in a separate line.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.

The return type is a vector/list of Node*, hence you need to push the head of the first and then second modified linked lists and return the vector/list.
Constraints : 
1 <= T <= 10        
0 <= N1 <= 10^4
0 <= N2 <= 10^4
-10^9 <= data <= 10^9 and data != -1

Time Limit : 1 sec
Sample Input 1 :
3
1 2 3 4 5 -1
6 7 8 9 10 -1
-1
3 4 5 7 -1
5 4 3 7 9 -1
4 3 -1
Sample Output 1 :
1 7 3 9 5 
6 2 8 4 10
4 7 
3 5
5 3 3 9 
4 4 7
Explanation For Sample Input1 :
Here we have 3 test cases, hence there are 3 pairs of linked lists.

Test case 1

Test Case 1: Here we connect alternate nodes of linked list 1 and linked list 2. The yellow link in the above diagram shows the modified linking of linked list 1, similarly, the green link shows the modified linking of linked list 2.

Test case 2

Test Case 2: As the first linked list is of length zero, we need to use the second linked list for the process. Hence first two alternate nodes of linked list 2 would be modified linked list 2 and the remaining alternate nodes would become modified linked list 1. The yellow link in the above diagram shows the modified linking of linked list 1, similarly, the green link shows the modified linking of linked list 2.

Test case 3

Test Case 3: Here the linked list 2 is shorter than linked list 1, hence once we encounter NULL in linked list 2, we would use alternate nodes of linked list 1. The yellow link in the above diagram shows the modified linking of linked list 1, similarly, the green link shows the modified linking of linked list 2.
Hint

Traverse iteratively through both the linked list and merge alternate nodes between them.

Approaches (1)
Brute Force
  1. Initially maintain two temporary pointers, (say, ’TEMP1’ and ‘TEMP2’) pointing to the head of both the linked lists 1 and 2, respectively.
  2. Create a third pointer (say, ‘tempNext’ and use it to point to the next node of ‘TEMP1’.
  3. Assign next of ‘TEMP1’ as ’TEMP2’ and ‘tempNext’ as next of ‘TEMP2’.
  4. Repeat this process to link alternate nodes between the two linked lists.
  5. If ‘NULL’ is encountered while iterating in any of the linked lists,  we need to continue the above process with the other linked list's remaining nodes.
  6. Finally, when then ‘NULL’ is encountered in the other linked list we get our answer.
  7. If the length of any of the two linked lists is zero in the first place, then create a new dummy node for the empty linked list and use the other linked lists nodes for alternate linking.
  8. Same as the previous process, use a third pointer ‘tempNext’ to point to the next node of ‘TEMP1’.
  9. Assign next of ‘TEMP1’ as ’TEMP2’ and ‘tempNext’ as next of ’TEMP2’. Repeat the same until ‘NULL’ in the other linked list is encountered.
Time Complexity

O(N1 + N2), where ‘N1’ denotes the length of the linked list 1 and ‘N2’ denotes the length of linked list 2.

 

We are iteratively traversing simultaneously through the linked lists of lengths ‘N1’ and ‘N2’. Hence, the overall time complexity will be O(N1 + N2).

Space Complexity

O(1)

 

We are not using any extra space. Hence, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Interweave Nodes
Full screen
Console