Remove Nodes From Linked List

---

Intuition

• Use a Monotonic Stack that is decreasing and then just make nodes out of it.

Complexity

Runtime

Space

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        stack = []
        cur = head
        while cur:
            while stack and cur.val > stack[-1]:
                stack.pop()
            stack.append(cur.val)
            cur = cur.next
        
        dummy = ListNode(-1)
        prev = dummy
        for num in stack:
            prev.next = ListNode(val=num)
            prev = prev.next
        
        return dummy.next

Notes

Cards

START Basic Front: Remove Nodes From Linked List Back: Convert to a monotonically decreasing stack END

---

References

• Remove Nodes From Linked List