LC-2487 Medium LeetCode

2487. Remove Nodes From Linked List

Linked List Stack Recursion Monotonic Stack

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 74% Topics: Linked List, Stack, Recursion, Monotonic Stack

Reading material

Linked Lists 14 min Stacks & Queues 11 min Backtracking 14 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class ListNode(object):
    def __init__(self, val=0, next=None):
        pass


# mono stack
class Solution(object):
    def removeNodes(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        stk = []
        while head:
            while stk and stk[-1].val < head.val:
                stk.pop()
            if stk:
                stk[-1].next = head
            stk.append(head)
            head = head.next
        return stk[0]

Solution from kamyu104/LeetCode-Solutions · MIT