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 = 1<>2<>3<>4<>5<>6<>7<>8 e K=3 Resultado: L = 3<>2<>1<>6<>5 <>4<>8<>7

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.
  1. Identificar os Grupos: Percorrer a lista e dividir os nós em grupos de $ K $ elementos.
  2. Inverter o Grupo: Para cada grupo identificado, inverter a ordem dos nós.
  3. 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:
  1. Para cada nó no grupo, trocar os ponteiros anterior e próximo.
  2. 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:
  1. Conectar o último nó do grupo anterior com o primeiro nó do grupo invertido.
  2. 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 $
  1. Primeiro grupo: 1, 2, 3 → invertido para 3, 2, 1
  2. Segundo grupo: 4, 5, 6 → invertido para 6, 5, 4
  3. 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 $

Exercícios relacionados