2487. Remove Nodes From Linked List - Explanation

1. Convert To Array

# 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]:
        cur, arr = head, [ListNode(0, head)]
        while cur:
            arr.append(cur)
            cur = cur.next

        rightMaxi = ListNode(0, None)
        for i in range(len(arr) - 1, 0, -1):
            if rightMaxi.val > arr[i].val:
                arr[i - 1].next = rightMaxi
            else:
                rightMaxi = arr[i]

        return arr[0].next

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Monotonic Decreasing Stack

# 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()
        cur = dummy

        for num in stack:
            cur.next = ListNode(num)
            cur = cur.next

        return dummy.next

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Recursion

# 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]:
        if not head:
            return None

        head.next = self.removeNodes(head.next)
        if head.next and head.val < head.next.val:
            return head.next
        return head

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

4. Reverse Twice

# 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]:
        def reverse(head):
            prev, cur = None, head
            while cur:
                tmp = cur.next
                cur.next = prev
                prev, cur = cur, tmp
            return prev

        head = reverse(head)
        cur = head
        cur_max = head.val

        while cur and cur.next:
            if cur.next.val < cur_max:
                cur.next = cur.next.next
            else:
                cur_max = cur.next.val
                cur = cur.next

        return reverse(head)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.