Remove Nodes From Linked List

MediumLinked Listmonotonic stack

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given the head of a linked list. Delete every node that has a node with a **strictly greater** value somewhere to its right (anywhere later in the list, not only the next node). Return the head of the resulting list. The surviving nodes keep their original relative order. A node is kept when every later value is less than or equal to it, so equal values do not cause deletions, and the last node is always kept.

Examples

Input: head = [5,2,13,3,8]
Output: [13,8]
5 and 2 are removed because of 13 later on, and 3 is removed because of 8.
Input: head = [1,1,1,1]
Output: [1,1,1,1]
No value is strictly greater than another, so nothing is removed.

Constraints

  • The number of nodes is in `[1, 10^5]`.
  • `1 <= Node.val <= 10^5`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More monotonic stack problems