Desafio 2: Implemente o TAD Listas circulares simples. Deve ter as operações abaixo: (2 V)
f. Crie uma função que recebe uma lista circular simples de números inteiros e um número inteiro que represente o número K aleatório. Começando pelo primeiro elemento da lista deve ser contado até K. Todos os K nós devem ser removidos da lista até
sobrar um único número. Imprima os números a medida que forem sendo removidos.

Passo 1

Beleza, vamos entender o que a questão está pedindo. A gente precisa implementar um Tipo Abstrato de Dados (TAD) para Listas Circulares Simples. O foco aqui é criar uma função que recebe uma lista circular de números inteiros e um número K. A função vai contar até K a partir do primeiro elemento e remover cada K-ésimo nó da lista até restar apenas um número. Além disso, conforme removemos os nós, vamos imprimir os números retirados. Para isso, vamos precisar entender como funcionam as listas circulares e como manipular seus nós.

Passo 2

Primeiro, vamos definir como é uma Lista Circular Simples. É uma estrutura de dados onde cada elemento (ou nó) aponta para o próximo, e o último nó aponta de volta para o primeiro, formando um círculo. Isso é útil para problemas onde precisamos percorrer repetidamente a lista, como o nosso desafio.

Passo 3

Vamos começar implementando a estrutura básica da lista circular. Precisamos de uma classe para representar cada nó e outra para a lista em si. Cada nó vai ter um valor e um ponteiro para o próximo nó.
class No:
    def __init__(self, valor):
        self.valor = valor
        self.proximo = None

class ListaCircular:
    def __init__(self):
        self.ultimo = None

Passo 4

Agora, vamos adicionar uma função para inserir elementos na lista. Como a lista é circular, sempre vamos manter uma referência para o último nó, que aponta para o primeiro.
    def inserir(self, valor):
        novo_no = No(valor)
        if not self.ultimo:
            self.ultimo = novo_no
            self.ultimo.proximo = self.ultimo
        else:
            novo_no.proximo = self.ultimo.proximo
            self.ultimo.proximo = novo_no
            self.ultimo = novo_no

Passo 5

Com a lista pronta, vamos agora criar a função que remove os K-ésimos nós. A ideia é percorrer a lista, contando até K, remover o nó nessa posição e imprimir seu valor, repetindo o processo até sobrar apenas um nó.
    def remover_k_esimo(self, K):
        if not self.ultimo:
            return

        atual = self.ultimo.proximo  # Começa no primeiro nó
        anterior = self.ultimo

        while atual != anterior:
            # Contar até K
            for _ in range(K - 1):
                anterior = atual
                atual = atual.proximo
            # Remover o nó atual
            print(atual.valor)
            anterior.proximo = atual.proximo
            atual = atual.proximo

        # Imprimir o último nó
        print(atual.valor)

Passo 6

Vamos testar nossa implementação. Vamos criar uma lista com alguns números e chamar a função com um valor de K. Por exemplo, se K = 3 e a lista tiver os números de 1 a 5, a ordem de remoção deve seguir a contagem até 3.
# Criando a lista
lista = ListaCircular()
for numero in range(1, 6):
    lista.inserir(numero)

# Removendo os K-ésimos elementos
K = 3
lista.remover_k_esimo(K)

Resposta

Ao executar o código acima com K = 3 e lista de 1 a 5, a saída será:
3
1
5
2
4
Isso significa que os números foram removidos na ordem 3, 1, 5, 2 e, por fim, restou apenas o número 4.

Exercícios relacionados