19. Remover o enésimo nó a partir do final da lista

2ª edição da minha jornada pelo leetcode :)

A questão:

Nesse problema precisamos remover o n-ésimo nó a partir do final da lista. Por exemplo, para uma lista [1, 2, 3, 4, 5] e n=2, o nó 4 deve ser removido, o que deixa a lista [1, 2, 3, 5].

Precisamos entender primeiro o conceito de lista encadeada simples (Singly Linked List) que aparece bastante em entrevistas de big techs (como por exemplo Amazon, a qual participei).

Uma lista encadeada simples é uma sequência de nós, onde cada nó contém um valor, val e uma referência para o próximo nó, next.

O problema já nos dá a classe do nó pronta.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */

A ideia para solução é utilizar dois ponteiros (first e second), ambos começam apontando para a cabeça da lista (head). E um ponteiro adicional, previous que aponta sempre para o nó anterior ao que vai ser removido.

var first: ListNode? = head
var second: ListNode? = head
var previous: ListNode? = nil

Agora a gente precisa mover o ponteiro first, n vezes a frente do second.

for _ in 0..<n {
    first = first?.next
}

Depois disso vamos avançar os dois ponteiros até o first alcançar o final da lista.

while first != nil {
    previous = second
    first = first?.next
    second = second?.next
}

Para finalizar vamos deletar o nó desejado, se o previous for nil, significa que o nó que vai ser removido é a cabeça da lista. Entao a nova cabeça vai ser head?.next.

Se não for esse caso então o nó previous?.next é ajustado para pular o nó second, que vai ser removido.

Aqui está o código completo:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        var first: ListNode? = head
        var second: ListNode? = head
        var previous: ListNode? = nil

        for _ in 0..<n {
            first = first?.next
        }

        while first != nil {
            previous = second
            first = first?.next
            second = second?.next
        }

        if previous == nil {
            return head?.next
        } else {
            previous?.next = second?.next
        }

        return head
    }
}

Complexidade de Tempo: O(n)

A primeira passagem é no for, que vai passar por n passos, e a segunda passagem no while, vai basicamente rodar pela mesma lisa que vai levar até O(n) no pior caso, onde n é o numero total de nós na lista.

É um algoritmo simples e eficiente.