Last Updated: 19 Nov, 2021

Merge LinkedList

Easy
Asked in companies
FlipkartRed HatAmazon

Problem statement

You are given two LinkedList of length ‘N’. Your task is to insert the elements of the second LinkedList in the first LinkedList at the alternate positions.

For example: Let 1 -> 3 -> 5 be the first LinkedList and 2 -> 4 -> 6 be the second LinkedList. Then after merging the first LinkedList will look like 1 -> 2 -> 3 -> 4 -> 5 -> 6.

Input Format-
First-line contains ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains an integer, ‘N’.
The following line contains ‘N + 1’  space-separated integers, which are the nodes of the first LinkedList, and each line ends with -1 to indicate that the LinkedList is over. Thus, -1 will never be a LinkedList element.
The following line contains ‘N + 1’ space-separated integers, which are the nodes of the second LinkedList, and each line ends with -1 to indicate that the LinkedList is over. Thus, -1 will never be a LinkedList element.
Output Format-
For each test case, you have to print the modified first LinkedList,
Note :
You don’t need to print or return anything. Just implement the given function and modify the first LinkedList.
Constraints -
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
All the elements in both of the LinkedList lie in the range [-10^9, 10^9] - {1}.
Note- the sum of ‘N’ over all test cases does not exceed 10^5.

Time Limit: 1 sec

Approaches

01 Approach

Approach: Run a loop and insert the element of the second LinkedList in the first LinkedList.

 

Algorithm:

  • Create two pointers, ‘first’ and ‘second’, and initialize them to the head of the first and the second LinkedList, respectively.
  • Create two pointers, ‘f_next’ and ‘s_next’.
  • While ‘first’ is not Null.
    • Update ‘f_next’ to ‘first -> next’.
    • Update ‘s_next’ to ‘second -> next’.
    • Update ‘second -> next’ to ‘f_next’.
    • Update ‘first -> next’ to ‘second’.
    • Update ‘first’ to ‘f_next’.
    • Update ‘second’ to ‘s_next’.