A festival path is lined with lanterns, given as a singly linked list of brightness values from the start of the path. Every night, at the same moment, each lantern that is strictly brighter than the lantern immediately before it (in the current chain, as it stands at dusk) burns out and is unhooked. The first lantern has nothing before it and never burns out. The remaining lanterns close up, keeping their order, and the next night the rule is applied again.
Return the head of the chain after k nights (it stops changing once a night passes with no
burn-out). Re-link the existing nodes; do not build a new list. An empty chain stays None.
Examples
Input: head = 1 -> 9 -> 8 -> 7 -> 3, k = 2
Output: 1 -> 7 -> 3
Explanation: night 1 removes 9 (brighter than 1); now 8 follows 1, so night 2 removes 8.
Input: head = 5 -> 3 -> 4 -> 6 -> 2 -> 7, k = 10
Output: 5 -> 3 -> 2
Explanation: 4, 6 and 7 all burn out on night 1; after that nothing changes.
Input: head = None, k = 3
Output: None
Constraints
0 <= number of nodes <= 3 * 10**4,0 <= k <= 10**9-10**9 <= node value <= 10**9- Chains can keep changing for thousands of nights. Re-checking the whole chain every night (even as a Python list) is far too slow for the large tests; aim for O(n) total.
Goals
- See that only nodes next to a removal can change status in the next round
- Apply simultaneous removals by marking first and splicing second
- Keep total work linear across many rounds