# Next Greater Node In Linked List

Posted: 15 Mar, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### For "node i" , next larger("node i") is the "node j.val" such that j > i and "node j.val" > "node i.val" , and j is the smallest possible choice. If such a j does not exist, the next larger value is 0.

##### Note :
``````Your task is to return an array of integers answer,
where ans[i] = next_larger(node_{i+1}).
``````
##### For Example :
``````Input: 2 - >1 -> 5
Output: ans = [5,5,0]

Here for the first node village, the village with a stronger ninja is present with a strength of 5, therefore ans = 5.
Similarly ans = 5 and since there are no villages after node 3 with stronger ninjas, therefore, ans = 0
``````
##### Input Format :
``````The first line of input contains a single integer ‘T’ denoting the number of test cases.

The second line contains single space-separated integers, denoting the elements of the linked list with -1 being the last element denoting the end of the list (or null element).
``````
##### Output Format :
``````Return an array of integers answer, where ans[i] = next_larger(node_{i+1}).
Print the output of each test case in a separate line.
``````
##### Note :
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 100
1 <= N <= 5000
1 <= node.val <=10^9

where 'N' is the size of the linked list and 'node.value' is the value of a node.

Time Limit : 1 sec
`````` Approach 1

We will iterate through the given linked list of elements (nodes) with the help of two nested loops. Where we will check for every node whether there exists a next node with a value bigger than the value of current node and subsequently build the ‘ans’ list (array) and return it.

The algorithm will be-

1. We will run a loop for the starting node (head) of the given linked list.
2. From every node we will run a loop and traverse the remaining nodes to check if there exists a node with a bigger value than our current node.
1. We will maintain a list (array) ‘ans’ for the final answer initialised by 0 which is required.
2. Add the next node’s value if it has a value bigger than the current node otherwise keep traversing linked list ahead until we reach the end of the list
3. The list ‘ans’ will be returned finally.