Last Updated: 3 Dec, 2020
Next Higher Node
Easy
Asked in companies
You are given a Singly Linked List of distinct integers. In addition to the ‘next’ pointer, every node of the linked list has a ‘nextHigher’ pointer that currently points to NULL. The task is to make the ‘nextHigher’ pointer of every node point to the next higher value node in the linked list.
A singly linked list is a type of linked list that is unidirectional; that is, it can be traversed in only one direction from head to the last node (tail).
Note:
For a node, if there is no higher value node in the linked list, it’s ‘nextHigher’ pointer should point to NULL.
Input Format
The first line of input contains an integer 'T', the number of test cases to run.
The first and the only line of every test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
Output Format:
For every test case, print the elements of the modified linked list in ascending order. The elements should be single-space separated, terminated by -1.
The output of each test case is printed in a separate line.
Note
You do not need to print anything, It already has been taken care of. Just implement the function and return the pointer to the minimum node in the modified linked list.
The linked list will be traversed using the ‘nextHigher’ pointer to produce the output.
Constraints:
1 <= T <= 10
1 <= N <= 10^4
-10^3 <= data <= 10^3 and data != -1
Where ‘data’ denotes the value of the nodes in the linked list.
Approaches
The idea is very simple. We will consider every node and check all the remaining nodes. If we encounter a node with just greater value than the current node, we will simply connect the ‘NEXT_HIGHER’ pointer of the current node to that node.
Algorithm:
- Traverse the linked list using two loops.
- Maintain a pointer to a node ‘NEW_HEAD’ that will keep track of the minimum valued node in the linked list. Initialize ‘NEW_HEAD’ to ‘HEAD’ of the linked list.
- In the outer loop, pick every node of the linked list one by one.
- Keep updating ‘NEW_HEAD’ in the outer loop if the value of the current node is less than the value of ‘NEW_HEAD’.
- In the inner loop, check the value of the rest of the nodes. If there exists a node (say present node) with greater value than the picked node and the value of ( 'PRESENT_NODE' - ‘PICKED_NODE’) is minimum, connect the ‘NEXT_HIGHER’ pointer of the ‘PICKED_NODE’ to the 'PRESENT_NODE'.
- Return the ‘NEW_HEAD’.
If we analyse, we can see that the modified linked list printed is sorted in ascending order. This is because every node’s ‘NEXT_HIGHER' pointer is pointing to the next greater valued node.
Thus, the idea is to sort the linked list formed by ‘NEXT_HIGHER' pointer.
Algorithm:
- Traverse the given linked list. To form a linked list from ‘NEXT_HIGHER' pointers, copy the ‘NEXT' pointer to ‘NEXT_HIGHER' pointer for every node.
- Sort the linked list formed by ‘NEXT_HIGHER' pointer using the Merge Sort algorithm.
- After applying the Merge Sort, the head node will be the minimum valued node in the linked list.
- Return the head node.
Algorithm for Merge Sort:
Merge Sort is a divide and conquer algorithm. In this algorithm, we divide the list into two parts, recursively sort the two parts and finally merge them such that the resultant list will be sorted.
- If the list contains only one node, return the head of the list.
- Else, divide the list into two sublists. For this, we will use two pointers ‘MID’ and ‘TAIL’ which will initially point to the head node. We will change ‘MID’ and ‘TAIL’ as follows until ‘TAIL’ becomes NULL:
‘MID’ = ‘MID’ -> ‘NEXT’
‘TAIL’ = ‘TAIL’ -> ‘NEXT’ -> ‘NEXT’
The above operation will ensure that ‘MID’ will point to the middle node of the list. - ‘MID’ will be the head of the second sublist, so we will change the ‘NEXT’ value of the node which is before mid to NULL.
- Call the same recursive algorithm for the two sublists.
Sublist 1 : [ ‘HEAD’ to ‘MID’ - 1 ]
Sublist 2 : [ ‘MID’ to ‘TAIL’ ] - Merge the two sublists and return the head of the merged list. For this, we will make a list ‘MERGE_LIST’ which will be initially empty. If the head of the first sublist has a value less than the head of the second sublist then we will add the head of the first sublist in the ‘MERGE_LIST’ and change the head to its next value. Else, we will add the head of the second sub list.
In the end, if any of the sublists becomes empty and the other sublist is non-empty, then we will add all nodes of the non-empty sublist in the ‘MERGE_LIST’.