Desafio 1: Implemente o TAD Listas duplamente ligadas de inteiros. Deve ter as operações abaixo: (2 V):
e. Crie uma função que receba uma lista duplamente ligada e inverta cada grupo de K nós. A função deve retornar a lista invertida. Ex: L =
e
Resultado: L = 3<>2<>1<>6<>5
e. Crie uma função que receba uma lista duplamente ligada e inverta cada grupo de K nós. A função deve retornar a lista invertida. Ex: L =
Passo 1
Beleza, vamos lá! O desafio aqui é implementar uma lista duplamente ligada de inteiros e, mais especificamente, criar uma função que receba essa lista e inverta cada grupo de $ K $ nós. Por exemplo, se tivermos a lista $ 1 \leftrightarrow 2 \leftrightarrow 3 \leftrightarrow 4 \leftrightarrow 5 \leftrightarrow 6 \leftrightarrow 7 \leftrightarrow 8 $ e $ K = 3 $, o resultado deve ser $ 3 \leftrightarrow 2 \leftrightarrow 1 \leftrightarrow 6 \leftrightarrow 5 \leftrightarrow 4 \leftrightarrow 8 \leftrightarrow 7 $. Para resolver isso, precisamos entender como funciona uma lista duplamente ligada e como podemos manipular seus nós para realizar as inversões em grupos.
Passo 2
Primeiro, vamos relembrar o que é uma lista duplamente ligada. Em estruturas de dados, uma lista duplamente ligada é uma sequência de nós onde cada nó aponta para o nó anterior e para o próximo. Isso permite navegar tanto para frente quanto para trás na lista.
Cada nó geralmente contém dois ponteiros:
- Anterior: aponta para o nó anterior na lista.
- Próximo: aponta para o próximo nó na lista.
- Valor: armazena o valor inteiro.
Aqui está uma representação básica em pseudo-código:
Classe Nó:
inteiro valor
Nó anterior
Nó próximo
Passo 3
Agora, precisamos criar a função que inverte cada grupo de $ K $ nós na lista. Vamos pensar em como fazer isso passo a passo.
- Identificar os Grupos: Percorrer a lista e dividir os nós em grupos de $ K $ elementos.
- Inverter o Grupo: Para cada grupo identificado, inverter a ordem dos nós.
- Conectar os Grupos: Garantir que, após a inversão, os grupos estejam conectados corretamente na lista.
Vamos detalhar cada uma dessas etapas.
Passo 4
Identificando os Grupos de $ K $ Nós
Para dividir a lista em grupos de $ K $ nós, podemos percorrer a lista com um ponteiro e contar até $ K $, marcando o início e o fim de cada grupo.
Por exemplo, com $ K = 3 $:
- Primeiro grupo: 1, 2, 3
- Segundo grupo: 4, 5, 6
- Terceiro grupo: 7, 8 (menos de $ K $, pode ficar como está ou ser invertido conforme a especificação)
Passo 5
Invertendo um Grupo de $ K $ Nós
Para inverter os nós de um grupo, precisamos trocar os ponteiros de anterior e próximo de cada nó dentro desse grupo.
Passos para inverter:
- Para cada nó no grupo, trocar os ponteiros
anterior
epróximo
. - Após a troca, o último nó do grupo se tornará o primeiro, e o primeiro se tornará o último.
Isso pode ser feito iterativamente, percorrendo o grupo e invertendo os ponteiros.
Passo 6
Conectando os Grupos Invertidos na Lista
Depois de inverter um grupo, precisamos conectar corretamente esse grupo à lista geral. Isso envolve:
- Conectar o último nó do grupo anterior com o primeiro nó do grupo invertido.
- Conectar o último nó do grupo invertido com o primeiro nó do próximo grupo.
Também precisamos atualizar o ponteiro da cabeça da lista para o novo primeiro nó após a primeira inversão.
Passo 7
Implementando a Função
Vamos agora estruturar a função em pseudo-código:
Função inverterGrupos(cabeça, K):
se cabeça for nulo ou K <= 1:
retorne cabeça
atual = cabeça
novaCabeça = null
grupoAnterior = null
Enquanto atual não for nulo:
grupoInicio = atual
contador = 0
// Encontrar o final do grupo
Enquanto contador < K e atual não for nulo:
atual = atual.próximo
contador += 1
se contador == K:
// Inverter o grupo
grupoInvertido = inverterLista(grupoInicio, K)
se novaCabeça for nulo:
novaCabeça = grupoInvertido
se grupoAnterior não for nulo:
grupoAnterior.próximo = grupoInvertido
grupoAnterior = grupoInicio
senão:
// Menos de K nós, manter como está
if grupoAnterior não for nulo:
grupoAnterior.próximo = grupoInicio
retorne novaCabeça
Aqui,
inverterLista
é uma função que inverte um subgrupo de $ K $ nós.Passo 8
Exemplo Prático
Vamos aplicar nossa função ao exemplo dado:
Lista original: $ 1 \leftrightarrow 2 \leftrightarrow 3 \leftrightarrow 4 \leftrightarrow 5 \leftrightarrow 6 \leftrightarrow 7 \leftrightarrow 8 $
$ K = 3 $
- Primeiro grupo: 1, 2, 3 → invertido para 3, 2, 1
- Segundo grupo: 4, 5, 6 → invertido para 6, 5, 4
- Terceiro grupo: 7, 8 → mantendo ou invertendo conforme a regra (neste caso, invertendo para 8, 7)
Resultado final: $ 3 \leftrightarrow 2 \leftrightarrow 1 \leftrightarrow 6 \leftrightarrow 5 \leftrightarrow 4 \leftrightarrow 8 \leftrightarrow 7 $
Resposta
Implementando a função conforme os passos descritos, temos que ao aplicar a inversão em grupos de $ K = 3 $ na lista $ 1 \leftrightarrow 2 \leftrightarrow 3 \leftrightarrow 4 \leftrightarrow 5 \leftrightarrow 6 \leftrightarrow 7 \leftrightarrow 8 $, o resultado será:
$ 3 \leftrightarrow 2 \leftrightarrow 1 \leftrightarrow 6 \leftrightarrow 5 \leftrightarrow 4 \leftrightarrow 8 \leftrightarrow 7 $