3) Next Greater Node In Linked List

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