Leaders of a List

Medium

You are given a singly linked list head. Call a node a *leader* if no node to its right (closer to the end of the list) holds a strictly greater value. Remove every node that is not a leader, keeping the remaining nodes in their original order, and return the head of the resulting list. The last node is always a leader, so the result is never empty.

Example 1

head=list_node([4, 7, 2, 6, 3]) → [7, 6, 3]

4 goes (7 is further right) and 2 goes (6 is further right). 7, 6 and 3 stay: nothing to the right of them is larger.

Example 2

head=list_node([2, 2, 5, 5]) → [5, 5]

Both 2s go because of the 5s. The 5s stay: an equal value is not a larger one.

Example 3

head=list_node([9]) → [9]

Constraints

The list has between 1 and 10⁵ nodes
1 ≤ Node.val ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Recursion Linked List Monotonic Stack

Similar problems

List Folded From Both Ends Medium Preorder of a Search Tree Medium Next Larger Down the List Medium Nights of the Withering Row Medium Symmetric Bead String Easy

Input

head=list_node([4, 7, 2, 6, 3])

Expected

[7, 6, 3]

Run checks the first 3 tests in your browser. Submit checks all 110 tests on the server, hidden ones included.