Merge LinkedList

Easy

0/40

Average time to solve is 20m

Contributed by

16 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input-1

Sample Output-1

1 2 3 4 5 6
3 6

Explanation for Sample Input 1:

For test case 1: 
    It is explained above.
For test case 2: 
    We added the first element of the second LinkedList next to the first element of the first LinkedList. Hence the first LinkedList will look like 3 -> 6.

Sample Input -2

2
3 
1 2 3 -1
-5 -2 -3 -1
3 
24 42 13 -1
91 42 13 -1

Sample Output -2

1 -5 2 -2 3 -3
24 91 42 42 13 13

Hint 1

Just merge them as asked in the problem.

Approaches (1)

Approach 1

Brute Force

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’.

Time Complexity

O(N).

We are traversing in the LinkedList containing ‘N’ elements. Hence the overall complexity is O(N).

Space Complexity

O(1).

We are creating four-pointers. Hence the overall complexity is O(1).

(100% EXP penalty)

Merge LinkedList

Console