Next Greater Node In Linked List LeetCode

 class Solution {

    public int[] nextLargerNodes(ListNode head) {

        ArrayList<Integer> aa=new ArrayList<Integer>();

        Stack<Integer> stack=new Stack<Integer>();

        

        

        ListNode temp=head;

       

        while(temp!=null){

            aa.add(temp.val);

            temp=temp.next;

        }

        Collections.reverse(aa);

        

        System.out.println(aa);

        

        int ab[]=new int[aa.size()];

        

        for(int i=0;i<aa.size();i++){

            if(stack.isEmpty()){

                ab[i]=(0);

                

            }

            else{

                while(!stack.isEmpty() && stack.peek()<=aa.get(i)){

                    stack.pop();

                }

                if(stack.isEmpty()){

                    ab[i]=(0);

                }

                else{

                    ab[i]=(stack.peek());

                }

                

            }

            stack.push(aa.get(i));

        }

        for(int i=0;i<ab.length/2;i++){

            int temp1=ab[i];

            ab[i]=ab[ab.length-i-1];

            ab[ab.length-i-1]=temp1;

        }

        

        return ab;

    }

}

APPROACH:

First We need to understand that we have to find the next greater element in right. So for this, we can either go for nested loops in which I will traverse from 0 to n and j from i+1 to n. 

While we can optimize this approach using Stack. 

Here we will first take all the data of the linked list and store them in ArrayList. Now we will find out the largest element starting from the end till the first element. So after forming ArrayList, we will reverse it, as a result, the linked list got reversed(only data sequence not links or addresses). Then we will take one element and look into the stack whether it's empty or not. If it's empty then add 0 in the array, else we will find out the next greater element traversing in the stack If we find it, we will add that peek otherwise we will pop till the stack becomes empty.

And in every iteration, we will store that element coming from ArrayList in the stack. 

As a result in end, we will be having one array which will store the values of the greater elements from the end till the start. Now again we will reverse it and hence we get desired output, which we will return.

  

TIME:O(N)[One Dimensional Array Is Used][LeetCode Time: 37ms faster than 31.26%]

SPACE:O(N)[Additional Stack, ArrayList Is Used][LeetCode Memory: 44.5MB less than 42.62%]

Thanks For Reading.😇

"Share Further To Increase Knowledge Treasure.😊"