CareerCup

public static Node pointToNextHigherElement(Node head) {
        Stack<Node> stack = new Stack<Node>();
        Node current = head;
        Stack<Node> tempList = new Stack<>();
        while ( current != null){
            if (stack.isEmpty()) {
                current = fillStack(stack, current, tempList);
            } else {
                Node elementFromStack = stack.pop();
                if (elementFromStack.value > current.value) {
                    stack.push(elementFromStack);
                    current = fillStack(stack, current, tempList);
                } else {
                    tempList.add(elementFromStack);
                }
            }

        }

        while(!stack.isEmpty()) {
            Node temp = stack.pop();
            if (!stack.isEmpty()) {
                Node next = stack.peek();
                temp.random = next;
            }
        }

        return head;
    }

    private static Node fillStack(Stack<Node> stack, Node current, Stack<Node> tempList) {
        stack.push(current);
        while (!tempList.isEmpty()) {
           stack.push(tempList.pop());
        }
        current = current.next;
        return current;
    }

Good catch. Added a temp stack to hold values lesser than the current node.

Put all the nodes in a min-heap.Keep extracting the root and populating the random pointer with the next extracted root from heap.

Space: O(N)
Time : O(NLogN)

public static Node pointToNextHigherElement(Node head) {
        Stack<Node> stack = new Stack<Node>();
        Node current = head;
        stack.push(current);
        current = current.next;
        while ( current != null){
            Node elementFromStack = stack.pop();
            if (elementFromStack.value > current.value) {
                stack.push(elementFromStack);
                stack.push(current);
            } else {
                stack.push(current);
                stack.push(elementFromStack);
            }
            current = current.next;
        }

        while(!stack.isEmpty()) {
            Node temp = stack.pop();
            if (!stack.isEmpty()) {
                Node next = stack.peek();
                temp.random = next;
            }
        }

        return head;
    }

@Trutgeek, does it work for 2->4->3->1->8 ?