New update is available. Click here to update.

Interweave Nodes

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.

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

Approach 1

Initially maintain two temporary pointers, (say, ’TEMP1’ and ‘TEMP2’) pointing to the head of both the linked lists 1 and 2, respectively.
Create a third pointer (say, ‘tempNext’ and use it to point to the next node of ‘TEMP1’.
Assign next of ‘TEMP1’ as ’TEMP2’ and ‘tempNext’ as next of ‘TEMP2’.
Repeat this process to link alternate nodes between the two linked lists.
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.
Finally, when then ‘NULL’ is encountered in the other linked list we get our answer.
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.
Same as the previous process, use a third pointer ‘tempNext’ to point to the next node of ‘TEMP1’.
Assign next of ‘TEMP1’ as ’TEMP2’ and ‘tempNext’ as next of ’TEMP2’. Repeat the same until ‘NULL’ in the other linked list is encountered.

Try Problem