-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNextGreaterNodeInLinkedList.java
More file actions
65 lines (55 loc) · 1.41 KB
/
NextGreaterNodeInLinkedList.java
File metadata and controls
65 lines (55 loc) · 1.41 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package Leetcode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
class ListNode
{
int val;
ListNode next;
ListNode( int x )
{
val = x;
}
}
public class NextGreaterNodeInLinkedList
{
public static void main( String[] args )
{
Scanner s = new Scanner( System.in );
int n = s.nextInt();
ListNode temp = new ListNode( 0 );
ListNode head = temp;
for( int i = 0; i < n; i++ )
{
temp.next = new ListNode( s.nextInt() );
temp = temp.next;
}
head = head.next;
int[] nextLargerNodes = nextLargerNodes(head);
for(int nextNumber: nextLargerNodes)
System.out.print( nextNumber + " ");
}
public static int[] nextLargerNodes( ListNode head )
{
ArrayList<Integer> list = new ArrayList();
while(head!=null)
{
list.add( head.val );
head= head.next;
}
int n = list.size();
int[] res = new int[n];
Arrays.fill( res, 0 );
Stack<Integer> stack = new Stack();
for(int i =0;i<n;i++)
{
while(!stack.isEmpty() && list.get( stack.peek())<list.get( i ))
{
res[stack.pop()] = list.get( i );
}
stack.push( i );
}
return res;
}
}