Last Updated: 1 Dec, 2020
Point to Greatest Value Node
Easy
Asked in companies
You are given a singly linked list with every node having an additional “arbitrary” pointer that currently points to NULL. We need to make the “arbitrary” pointer to the greatest value node in a linked list on its right side.
More formally, each Linked List node has three attributes ‘data’, which is the value of the node, the ‘next’ pointer, which points to the next node, and an ‘arbit’ pointer which is initially NULL.
Note:
You need to return the head after populating the ‘arbit’ pointer.
For example:
Given ‘head’ as 3 -> 5 -> 2 -> 1.
After populating the arbitrary pointer, each node's ‘arbit’ pointer would point to 5 2 1 -1 respectively.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The second line of each test case contains space-separated integers, denoting the elements in linked list nodes, and -1 denotes the end of the linked list.
Output Format :
For each test case, print integers denoting the value of the nodes being pointed by the arbitrary pointer of that node, if the arbitrary pointer points to NULL, print -1.
Note:
You are supposed to return the head of the linked list, whose arbitrary pointer is populated.
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= ‘T’ <= 10
1 <= ‘N’ <= 5000
0 <= ‘data’ <= 10 ^ 4 and ‘data’ != -1
Time Limit: 1sec.
Approaches
The idea is to loop for every node and find the node with the greatest value with respect to the current node.
The steps are as follows:
- Maintain a ‘tempNode’ which points at the 'head'.
- While ‘tempNode’ is not NULL:
- Maintain a ‘currentNode’ which points to the next of ‘tempNode’, a variable ‘mxVal’ which helps to find the max value towards the right of ‘currentNode’, and ‘maxValNode’, which points to the node with maximum value.
- Point the ‘arbit’ pointer of ‘tempNode’ to ‘maxValNode’.
- Move the ‘tempNode’ ahead.
- Return ‘head’ as the final result.
The idea is to Reverse the given linked list. Start traversing the linked list and store the maximum value node encountered so far. Make the arbitrary pointer of every node to point to the max. If the data in the current node is more than the max node so far, update max. Reverse the modified linked list and return head.
The steps are as follows:
- Reverse the linked list using a helper function ‘reverse’, which returns the head of a reversed linked list.
- The ‘reverse’ function takes a ‘head’ pointer as a parameter.
- Maintain three-pointers ‘prev’, ‘current’, and ‘next’.
- Loop till the end of the list using the ‘current’ pointer and for each iteration:
- ‘Next’ should point to the NEXT pointer of ‘current’.
- The NEXT pointer of ‘current’ should point to ‘prev’.
- ‘current’ becomes ‘next’.
- ‘prev’ becomes ‘current’.
- Finally, we return the ‘head’ as the final result of the reversed linked list.
- Maintain 2 pointers ‘max’, which points to the max value node we have encountered, and ‘temp’, which we use to traverse the linked list.
- Mark the ‘arbit’ pointer of ‘temp’ to ‘max’.
- Check if the data value of ‘max’ is less than data of ‘temp’, then update the ‘max’ node.
- Move the ‘temp’ node ahead.
- Reverse the linked list again.
- Return the final head that we got as the final result.