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.
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.
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;
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;
}
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;
}