Fold and Merge Linked List

Moderate
0/80
profile
Contributed by
13 upvotes
Asked in company
Nucleus Software

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

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2 2 2 2 -1
4 5 3 1 2 6 -1
Sample Output 1 :
4 4 -1
3 10 24 -1
Explanation Of Sample Input 1 :
For test case 1, 
First, we will break into two equal halves, [ 2 -> 2 ] and [ 2 -> 2 ], now folding and merging with the product, so the result is [ 2 * 2 -> 2 * 2 ] i.e. [ 4 -> 4 ].

For test case 2,
For this case the two halves are [ 4 -> 5 -> 3 ] and [ 1 -> 2 -> 6 ], now folding and merging with product [ 3 * 1 -> 5 * 2 -> 6 * 4 ] i.e [ 3 -> 10 -> 24 ]
Sample Input 2 :
2
3 1 2 2 -1
5 5 1 2 1 2 -1
Sample Output 2 :
2 6 -1
2 5 10 -1
Hint

Can you break down the problem into two different problems and later merge by performing both?


 

Approaches (1)
Optimal

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

O(N), where ‘N’ is the size of our linked list ‘HEAD’.
 

We will iterate over linked only once, so total operations are ‘N’.

Space Complexity

O(1) .


Constant extra space is required. Hence, the overall Space Complexity is O(1).


 

Code Solution
(100% EXP penalty)
Fold and Merge Linked List
Full screen
Console