Next Higher Node

Easy
0/40
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
HSBCAspire Systems

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
1 
6 10 7 8 5 -1
Sample Output 1:
5 6 7 8 10 -1
Explanation For Sample Output 1:
The ‘nextHigher’ pointer of every node should point to the next higher value in the linked list.

example

The linked list printed after the above process is 5 6 7 8 10 -1. Note that list is printed starting from the minimum valued node using ‘nextHigher’ pointer.
Sample Input 2:
3
5 10 -6 4 7 -1
10 20 30 40 50 -1
-10 -20 -30 -40 -50 -1
Sample Output 2:
-6 4 6 7 10 -1
10 20 30 40 50 -1
-50 -40 -30 -20 -10 -1
Hint

For every node, find the next greater valued node in the linked list. 

Approaches (2)
Brute Force

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

 

Time Complexity

O(N * N), where ‘N’ is the number of nodes in the linked list.

 

For every node of the linked list, we are traversing all the remaining nodes. The total operations performed will be (N * N). Thus, the final time complexity is O(N * N).

Space Complexity

O(1) 

 

Constant additional space is required. 

Code Solution
(100% EXP penalty)
Next Higher Node
Full screen
Console