Hi friends! In this article, we going to find next greater node in linked list after that we going to convert that into an array.

Lets jump into problem.

We are given a linked list with head as the first node.  Let’s number the nodes in the list: node_1, node_2, node_3, ... etc.

Each node may have a next larger value: for node_inext_larger(node_i) is the node_j.val such that j > inode_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.

Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).

Note that in the example inputs (not outputs) below, arrays such as [2,1,5] represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.

Example 1:

Input: [2,1,5]
Output: [5,5,0]

Example 2:

Input: [2,7,4,3,5]
Output: [7,0,5,5,0]

Example 3:

Input: [1,7,5,1,9,2,5,1]
Output: [7,9,9,9,0,5,0,0]

Solution:

public int[] nextLargerNodes(ListNode head) {
    
	// Keeps track of indices of values in nums
    Stack<Integer> stack = new Stack<>();
	
	// Store node values as we go, 
	// updates to output value ("next greatest") within while loop as we see them
    List<Integer> nums = new ArrayList<>();
    
    ListNode n = head;
	
	// For generating the corresponding index in nums as we step through LinkedList
    int index = 0;
    
    while (n != null) {
      
      nums.add(n.val);
      
	  // Process anything that is less than current node value
	  // i.e. current node value is the "next"greatest for elements (index-referenced) in the stack
      while (!stack.isEmpty() && nums.get(stack.peek()) < n.val) {
        nums.set(stack.pop(), n.val);
      }
      
	  // Set up for next iteration. 
	  // Note: Every node gets into the stack.
      stack.push(index);
      n = n.next;
      index++;
    }
    
    // Handle remaining items in stack / write in 0 (no "next greatest" found for these)
    while (!stack.isEmpty()) {
      nums.set(stack.pop(), 0);
    }
    
    // Format output
    int[] result = new int[nums.size()];
    for (int i = 0; i < result.length; i++) {
      result[i] = nums.get(i);
    }
    
    return result;
  }

Hand Written explanations:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s