Largest Node on the Right for Each Node in a Linked List

This problem is also known as "Point to next higher values node in a linked list with arbitrary pointer".

Problem statement: Given a linked list, find(and print) the node with the largest value on the right for each node in the given linked list.

For each node ‘n’ in the given linked list, find the largest valued node on its right by searching the right segment of the linked list.

This approach takes O(n^2) time.

If we keep track of the maximum element seen so far while traversing in the opposite direction (from right to left) we can solve this problem in O(n) time.

To traverse the list in the opposite direction, we can either reverse the list or we can make use of the stack data structure.

Algorithm using reversal of the list.

1.Find the largest valued node on the left for each node.
2. Reverse the output sequence to get the expected output.
3. Restore the original list by reversing the reversed list .

----------------

Algorithm using the Stack data structure

1. Push all nodes onto the stack.
2. Print the largest value seen so far for each element of the stack.
3. Reverse the output sequence to get the expected output.

Time complexity: O(n)

---
Website: http://www.ideserve.co.in

Facebook:   / ideserve.co.in