Escreva uma função que remove o k-ésimo nó da lista encadeada.

Passo 1

O enunciado pede uma função que remova o k-ésimo nó (1-indexado) de uma lista simplesmente encadeada, manipulando ponteiros e cuidando de casos de borda como lista vazia ou k inválido.

Passo 2

Uma lista encadeada é composta de nós onde cada nó aponta para o próximo. Para remover um nó, precisamos ajustar o ponteiro do nó anterior para pular o nó a ser removido e liberar a memória desse nó.

Passo 3

Começamos tratando casos de borda: se a lista estiver vazia (head == NULL) ou k for menor que 1, não fazemos nada e retornamos a lista original.
Se k == 1, estamos removendo o primeiro nó: salvamos um ponteiro temporário para head, avançamos head para head->next, liberamos o nó original e retornamos o novo head.

Passo 4

Para k > 1, percorremos a lista até chegar ao (k-1)-ésimo nó. Se durante a travessia encontrarmos o fim da lista antes de alcançar esse nó, k é inválido e retornamos a lista sem alterações.
Se chegamos ao (k-1)-ésimo nó e ele tem um next válido, salvamos o ponteiro para o k-ésimo nó, ajustamos (k-1)->next para pular o k-ésimo nó, liberamos o nó removido e retornamos head.

Passo 5

A complexidade é O(n) no pior caso e o espaço é O(1); isso atende bem ao caso geral de remoção em lista encadeada.

Resposta

// Definição do nó
typedef struct Node {
int val;
struct Node *next;
} Node;
// Função que remove o k-ésimo nó (1-indexado) e retorna o novo head
Node* removeKthNode(Node* head, int k) {
// Caso a lista esteja vazia ou k inválido
if (head == NULL || k < 1) {
return head;
}
// Caso seja para remover o primeiro nó
if (k == 1) {
    Node* toRemove = head;
    head = head->next;
    free(toRemove);
    return head;
}

// Percorre até o (k-1)-ésimo nó
Node* prev = head;
for (int i = 1; i < k-1 && prev != NULL; i++) {
    prev = prev->next;
}

// Se não chegou ao (k-1)-ésimo ou não há k-ésimo, retorna sem alterações
if (prev == NULL || prev->next == NULL) {
    return head;
}

// Remove o k-ésimo nó
Node* toRemove = prev->next;
prev->next = toRemove->next;
free(toRemove);

return head;
}

Exercícios relacionados