Last Updated: 2 Feb, 2022

Fold and Merge Linked List

Moderate

Asked in company

Solve now

Problem statement

You are given a singly linked list containing ‘N’ nodes (‘N’ is even), where every node in the linked list contains a pointer ‘NEXT’, which points to the next node in the list and has an integer value associated with it.

Your task is to break LinkedList into two halves and then take the first half, fold it over the second half and merge all the intersecting nodes by taking their product.

Note :

You will apply this operation only once, check example for better understanding.

Example :

N = 4
NODE = 1 -> 2 -> 3 -> 4

In the following example, first, you break your List into two equal half, [ 1 -> 2 ] and [ 3 -> 4 ],

Now you will fold the first half over the second half and merge them with their product.
So the answer is [ 3 * 2 -> 4 * 1 ] i.e. [ 6 -> 4 ].

Input Format :

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of the test case contains ‘N + 1’ space-separated where the first 'N' elements represent the LinkedList node, and the last integer is always '-1' representing the end of the LinkedList.

Output format :

Print the folded and merged LinkedList. Make sure to add ‘-1’ at the end of your resulting LinkedList.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 1e5

Sum of N <= 10^5

Time Limit: 1 sec

Solve now

Approaches

01 Approach

APPROACH :

Firstly, we need to divide our LinkedList into two equal half. We do this by using the Fast pointer method, where we initially take two pointers, let's say ‘FAST’ and ‘HEAD’ where ‘HEAD’ is the initial pointer of our list also ‘FAST’ is also pointed to our ‘HEAD’ pointer.
We will jump our pointer to ‘NEXT’ once for ‘HEAD’ and twice for ‘FAST’. When our ‘FAST’ pointer reaches the end of our list, our ‘HEAD’ will be precisely at the middle of our list. The above process divides our list into two halves.
Our folding is done to the second half, where it merges with the reversed first half of our list. Keeping this in mind, we will reverse our first half of the list as we do our first step to find the middle of our List.
Now for each upcoming node for the ‘HEAD’ pointer, we need to multiply all our values of the first half in reverse, which we stored in some pointer, let's say ‘PREV’.
We will store the initial node of our resultant List in pointer ‘ANS’ and start merging ‘HEAD’ and ‘PREV’ by multiplying the values of both nodes.
Once we merge, we will return the ‘ANS’ pointer.

ALGORITHM :

Create three-pointer ‘FAST’, ‘NEXT’ and ‘PREV’ where ‘FAST’ points to our ‘HEAD’.
We will run a while loop till our ‘FAST’ is not ‘NULL’.
- We change our ‘FAST’ to its ‘NEXT->NEXT’ pointer, set ‘NEXT’ as ‘NODE->NEXT’, set ‘NODE->NEXT’ as ‘PREV’ and now change ‘PREV’ to ‘NODE’.
- Set ‘NODE’ to ‘NEXT’.
Now we initialise our ‘ANS’ pointer as ‘HEAD’.
Start a while loop till our ‘HEAD’ is not ‘NULL’.
- Set ‘HEAD->VAL’ as ‘HEAD->VAL * PREV->VAL’.
- Move ‘HEAD’ to ‘HEAD->NEXT’ and ‘PREV’ to ‘PREV->NEXT’.
Return ‘ANS’.

Solve now