2487.remove-nodes-from-linked-list.md

2487. Remove Nodes From Linked List

Monotonic Stack

We iterate the list and use monotonic stack to find the next greater node, then we start a new list to chain the remaining nodes in the stack.

fun removeNodes(head: ListNode?): ListNode? {
    var current: ListNode? = head
    val stack = Stack<ListNode>()
    while (current != null) {
        while (stack.isNotEmpty() && stack.peek().`val` < current.`val`) {
            stack.pop()
        }
        stack.push(current)
        current = current.next
    }

    val sentinel = ListNode(-1)
    sentinel.next = head
    current = sentinel
    for (node in stack) {
        current!!.next = node
        current = current.next!!
    }

    return sentinel.next
}

• Time Complexity: O(N), where N is the number of nodes in the list.
• Space Complexity: O(N)

Recursion

We can also use recursion to solve this problem. The recursive function returns the list that has removed all nodes which have a greater value.

In the recursive function, we need to remove the next node first recursively (bottom-up), then we can decide whether to remove the current node.

There are some possible cases:

• next is null: Just return the current node.
• current >= next: Keep the current node, we update the next pointer (it might updated after removal) and return current node.
• Current < next: Remove the current node, we return the updated next node.

  5 -> 2 -> 13 -> 3 -> 8
f(5)
     f(2) = 13
          f(13) = 13
                f(3) = 8
                     f(8) = 8
                         f(null) = null
                       8.next = null, return 8
                  3 < 8, return 8
            13.next = 8, return 13
       2 < 13, return 13
  5 < 13, return 13

fun removeNodes(head: ListNode?): ListNode? {
    if (head == null) return null

    val next = head.next
    val newNext = removeNodes(next)
    if (newNext != null && head.`val` < newNext.`val`) return newNext

    head.next = newNext
    return head
}

• Time Complexity: O(N), where N is the number of nodes in the list.
• Space Complexity: O(N) for recursion stack.

Reverse

For 5 -> 2 -> 13 -> 3 -> 8, it will become 13 -> 8 after removal. It's increasing of reversed list (8 -> 13). We can reverse the list first, then remove the nodes which have a smaller value. Finally, we reverse the list again.

fun removeNodes(head: ListNode?): ListNode? {
    if (head == null) return null
    
    val reversedHead = reverseList(head)
    var current: ListNode? = reversedHead
    var next: ListNode? = reversedHead?.next
    while (current != null && next != null) {
        // We keep skipping the smaller node.
        while (next != null && current.`val` > next.`val`) {
            next = next.next
        }
        // Chain the next greater node.
        current.next = next
        current = next
        next = next?.next
    }
    // Remember to reverse the list back
    return reverseList(reversedHead)
}

// Skip revserseList()

• Time Complexity: O(N), where N is the number of nodes in the list.