Next Greater Node In Linked List in Java
In this tutorial, we are going find the Next Greater Node In Linked List in Java provided the head of a linked list containing n nodes. Each node in the list has a value that must be determined for the next greater node. In other words, determining the value of the node that is immediately adjacent to each other and that is strictly greater than that node. An integer array that has the next greater node values are returned. If the ith node does not have a next greater node, 0 is returned.
Example 1:
Input: head = [4, 3, 6]
Output: [6, 6, 0]
Explanation: The next greater node for the first node with value 4 is the node with value 6. The next bigger node after the second node with value 3 is the node with value 6. There is no node with a strictly bigger value after the third node with a value of 6; hence, its output is 0. Thus, the output array is [6, 6, 0].
Example 2:
Input: head = [ 3, 5, 8, 2, 4]
Output: [5, 8, 0, 4, 0]
Explanation: The first node with a value of 3 has the next greater node with a value of 5, resulting in an output of 5. Similarly, for second node with a value of 5 has the next greater node with a value 8. The third node with value 8 has no strictly greater nodes after it, so the result is value 0. The fourth node with value 2 has the next greater node with value 4, and the fifth node with value 4 has no strictly greater nodes. Thus, the output array is [5, 8, 0, 4, 0].
Approach: Using Monotonic Stack
First of all, initialise a stack and an array called ansr, where stack stores the linked list's contents in reverse order and ansr stores the next greater nodes. Then, reverse the linked list using the reverse method. Next, begin the loop from the end of the linked list to the beginning. Then, pop elements from the stack while it is not empty, and the top element has a value less than or equal to the current node. If the stack is still not empty after the previous step, assign the top element to ansr[i], where i is the current index. Check if the stack is empty, then assign 0 to ansr[i] because there is no greater node. Let’s push the value of the current node onto the stack. Proceed to the subsequent node. Finally, return the ansr array, containing the next greater nodes for each node in the linked list.
FileName: GreatestNextNodeInLinkedList.java
import java.util.Stack; // defining linked list class ListNode { int valu; ListNode next; ListNode(int valu) { this.valu = valu; } } public class GreatestNextNodeInLinkedList{ public static void main(String[] args) { GreatestNextNodeInLinkedList n = new GreatestNextNodeInLinkedList(); // Create a linked list and provide input values ListNode head = new ListNode(3); head.next = new ListNode(5); head.next.next = new ListNode(8); head.next.next.next = new ListNode(2); head.next.next.next.next = new ListNode(4); int[] resl = n.nextLargerNodes(head); System.out.println("Next greater nodes in linked list are:"); for (int numb : resl) { System.out.print(numb + " "); } } //method for finding next greater node public int[] nextLargerNodes(ListNode head) { Stackstack = new Stack<>(); int len = length(head); int[] ansr = new int[len]; ListNode newHead = reverse(head); for (int i = len - 1; i >= 0; i--) { while (!stack.isEmpty() && stack.peek() <= newHead.valu) { stack.pop(); } if (!stack.isEmpty()) { ansr[i] = stack.peek(); } else { ansr[i] = 0; } stack.push(newHead.valu); newHead = newHead.next; } return ansr; } // to get the length of the linked list public int length(ListNode head) { if (head == null) return 0; int cnt = 0; while (head != null) { head = head.next; cnt++; } return cnt; } // function to reserve the linked list public ListNode reverse(ListNode head) { if (head == null || head.next == null) { return head; } ListNode secondLast = head.next; ListNode rev = reverse(head.next); secondLast.next = head; head.next = null; return rev; } }
Output:
Next greater nodes in linked list are: 5 8 0 4 0
Complexity analysis: The time complexity is O(n), where n is the number of nodes in the linked list. Because the program uses a recursive function to iterate through a linked list, it calculates its length and reverses it. It also finds the next greater node for each node, performing operations on the stack. The space complexity is O(n) because the program uses a stack to store potential next greater nodes. Also, additional space for the result array.