Coding Interview: aprenda a resolver problemas com listas, árvores e grafos

Listas ligadas e duplamente ligadas - Introdução

Apresentando o curso e conteúdos

Boas-vindas a mais um curso de Coding Interview (entrevista técnica de código). Meu nome é Jefferson Silva, e, por questões de acessibilidade, eu vou me autodescrever.

Audiodescrição: Eu sou um homem branco, com barba e cabelos escuros; uso óculos e estou com uma camiseta preta com o nome da Alura.

Neste curso, indicamos este conteúdo para quem está se aprofundando no tema de Coding Interview (entrevista técnica de código) e pretende se candidatar a uma vaga cujo processo seletivo inclui uma etapa de Coding Interview (entrevista técnica de código).

Ao longo das aulas, nós vamos aprender a lidar com estruturas mais complexas, trabalhar com referências e ponteiros, e abordar relações entre elementos.

Nós vamos explorar listas ligadas, árvores, grafos e um tema que nós chamamos aqui de ordenação topológica.

Estabelecendo pré-requisitos e fluência

O que é necessário para acompanhar o conteúdo deste curso? Recomendamos que você já tenha concluído o primeiro curso de Coding Interview (Entrevista de Codificação), pois vamos aproveitar tudo o que vimos ali, especialmente técnicas e estruturas abordadas naquela etapa. Também vamos nos aprofundar e realizar novamente mais algumas simulações de entrevista.

Para isso, na parte de simulação, é importante que você tenha fluência em alguma linguagem de programação. Neste curso, continuaremos utilizando Python. Nas atividades, deixaremos alternativas que mostram como realizar as mesmas tarefas que executamos durante o curso em outras linguagens.

O importante é ter fluência nessas linguagens — não em frameworks (estruturas de desenvolvimento) ou bibliotecas —, mas na construção básica: sintaxe, estruturas de dados e assim por diante.

Dito isso, podemos seguir em frente e começar a estudar nossa primeira estrutura de dados.

Listas ligadas e duplamente ligadas - Listas ligadas

Apresentando estruturas baseadas em referências

As estruturas que vimos até agora lidavam, em geral, com elementos dispostos lado a lado na memória ou, no caso de hashes (tabelas hash) e dicionários, podiam estar espalhados na memória, mas ainda havia a ideia de ordem. Para muitos desses elementos, tínhamos índice e acesso por índice.

O fato de sabermos a posição inicial de um array (vetor) e o índice que queremos acessar permitia realizar acesso direto aos elementos.

Agora, vamos começar a tratar de estruturas que lidam com referências. Ou seja, os elementos podem estar espalhados na memória, e precisamos manter alguma forma de referência entre eles para indicar o tipo de relação que guardam, seja sequência, hierarquia e assim por diante.

Definindo nós e listas ligadas

A primeira estrutura que veremos aqui é a lista ligada. Para começarmos a falar sobre lista ligada, precisamos tratar do menor elemento que conseguimos representar em uma lista: um nó.

Vamos criar um nó e atribuir um valor a ele, por exemplo, 15. Esse seria o nosso primeiro nó.

Um nó é composto por um dado e uma referência para o próximo elemento. Para armazenarmos o valor 15, guardamos duas informações: o próprio dado e uma referência. Isso será importante ao avaliarmos a questão de espaço.

Se tivéssemos outro elemento, outro nó desse tipo — por exemplo, um nó com valor 25 — e quiséssemos representar uma relação de sequência entre esses números, poderíamos usar a referência next. Assim, poderíamos fazer o primeiro elemento apontar para o 25 e, então, teríamos uma lista ligada.

Nesse caso, temos o nó 15, composto por dado e next, ligado ao nó 25, estabelecendo a noção de sequência entre eles: primeiro vem o 15, depois o 25.

Vamos adicionar mais um elemento para reforçar como funciona. Incluiremos o 32 e faremos o mesmo procedimento. Podemos mover esse elemento adiante. Imagine que isso é a memória: os elementos podem estar espalhados, mas a ordem lógica da lista é dada pelas referências. Assim, ainda que o 15 esteja fisicamente “à direita”, ele pode ser o primeiro elemento da lista, seguido pelo 25 e, depois, pelo 32. A ordem é determinada pelas referências que guardamos junto aos nós.

Vamos organizar para ficar mais claro. Para todos os efeitos, teremos outra visualização, que utilizaremos várias vezes ao longo do curso: uma versão simplificada que omite o campo next e usa uma seta para representar a referência (a conexão) com outro nó. Assim, temos a lista 15 → 25 → 32.

Gerenciando referências e definindo o head

Se quisermos manipular essa lista — por exemplo, percorrê-la imprimindo todos os valores — precisamos de um primeiro cuidado ao lidar com referências: como chegamos a algum desses elementos? Qual é a referência para determinado nó?

Na maioria das linguagens de programação, quando existe um elemento desse tipo sem nenhuma referência apontando para ele, o sistema o considera lixo para o mecanismo de garbage collector (coletor de lixo). Esse elemento é lixo porque não conseguimos mais alcançá-lo; se não conseguimos alcançá-lo, não conseguiremos utilizá-lo. Nesse caso, o garbage collector pode remover esses elementos: remove um, o próximo fica sem referência, remove o seguinte e assim por diante.

Por isso, quando trabalhamos com listas, é comum mantermos uma referência para o primeiro elemento da lista, pois, a partir dele, conseguimos percorrer toda a estrutura. Vamos criar um ponteiro chamado head, convenção usada para listas ligadas, que aponta para a cabeça da lista, o primeiro elemento, o início da lista. Referenciaremos o nó de valor 15 utilizando o ponteiro head.

Percorrendo a lista ligada

Como implementaríamos um algoritmo simples para percorrer a lista imprimindo todos os elementos? Podemos começar com um nó atual apontando para o começo da lista, por meio de uma variável atual, e utilizar um laço. Esse laço funcionará da seguinte forma: enquanto atual não for vazio (nulo), avançamos.

Começamos inicializando o ponteiro no início da lista:

atual = head

Em seguida, estruturamos o laço que continuará enquanto houver nós a visitar:

while atual is not None:

Como avançamos na lista? Suponha que atual seja o primeiro nó e queiramos chegar ao próximo. Temos uma referência para ele, que é exatamente atual.next. Se fizermos atual = atual.next, avançamos um passo na lista. Repetimos isso até atual apontar para o vazio (nulo).

Colocando o avanço dentro do laço:

while atual is not None:
    atual = atual.next

Vamos retirar a marcação de cor e executar o algoritmo completo agora. Começamos com atual no primeiro nó. Vamos imprimir atual.dado. Em cada nó, conseguimos acessar tanto o dado desse nó quanto a referência para o próximo, então devemos lembrar sempre disso.

Executando com a impressão do valor em cada nó antes de avançar:

while atual is not None:
    print(atual.data)
    atual = atual.next

Executando: atual aponta para 15; imprimimos primeiro 15. Vamos posicionar o console mais abaixo. Em seguida, avançamos para o próximo, imprimimos 25 e avançamos novamente. Imprimimos 32; agora atual aponta para o vazio (nulo), encerramos o algoritmo e percorremos a lista.

Analisando a complexidade de percurso

Com isso, conseguimos começar a falar sobre complexidade em listas ligadas. Para percorrer uma lista, precisamos passar por todos os elementos, simplesmente atualizando uma referência. A atualização da referência é constante, O(1), mas, para percorrer a lista inteira, passamos por todos os elementos, o que é O(N).

Registrando: para nossa lista, em relação a tempo, percorrê-la é O(N).

Para deixar essa marcação de complexidade registrada no código:

# Lista

# Percorrer uma lista - O(n)

Esta é a primeira operação que estamos observando na lista.

Inserindo e removendo no início da lista

Vamos analisar as operações de inserção e remoção no início da lista.

Vamos supor que temos um nó novo. Vamos remover um elemento no nosso ambiente de testes para criar mais um nó, que chamaremos de 89. Vamos voltar para o sandbox (ambiente de testes) e criar o nó 89. Nosso objetivo é colocar esse elemento no começo da lista.

Como fazemos isso?

Intuitivamente, queremos que esse novo elemento aponte para o 15 e que o head passe a apontar para esse novo elemento. Isso efetivamente transforma a nossa lista em: 89, 15, 25, 32.

Vamos implementar apenas as operações básicas para observar como escreveríamos isso via código.

Para manipular esse nó, precisamos de um ponteiro para ele. Vamos supor que exista uma referência chamada nó. Supondo que nó aponte para o novo elemento e que temos o head da lista, como realizamos a operação?

Precisamos conectar esse nó ao começo da lista. Para isso, fazemos nó.next = head. No código, usando a variável no (sem acento) para representar o nó:

no.next = head

Em seguida, atualizamos o head com o nó recém-inserido, isto é, head = nó. Consolidando os dois passos:

no.next = head
head = no

Essa operação funciona independentemente da quantidade de nós na lista. Sempre realizaremos um número constante de mudanças nas referências, portanto, inserir no início é uma operação O(1). Concluímos que “inserir no início da lista” é sempre O(1), pois conseguimos fazê-la com apenas essas duas mudanças de referência.

Registrando as complexidades vistas até aqui:

# Percorrer uma lista - O(n)
# Inserir no início - O(1)

Removendo do início da lista

E se quisermos remover um elemento do começo da lista?

Dado que temos a referência para o elemento que desejamos remover, e considerando o caso de remoção do primeiro elemento, o head da lista deve passar a apontar para nó.next. Em seguida, há mais um passo importante.

O head apontará para o próximo nó em relação ao nó que estamos removendo e, em teoria, a lista já terá sido atualizada. Se observarmos, teremos o head apontando para o 15, e conseguiremos percorrer a lista a partir daí.

Ao sair do escopo da função, provavelmente não teremos mais a referência para o nó removido (por exemplo, o 89). Ele será marcado pelo garbage collector (coletor de lixo). No entanto, até que isso ocorra, estamos mantendo duas referências para o nó 15: uma por meio do head e outra por meio de nó.next. Esse é um ponto de atenção que nos leva a uma boa prática: sempre que removermos um nó de uma lista, devemos zerar todas as suas referências, para evitar referências que não têm mais utilidade.

Como esse elemento não será mais utilizado e será removido em algum momento, para ajudar o garbage collector (coletor de lixo), é recomendável zerarmos sua referência next.

Voltando ao ponteiro nó, vamos apontá-lo para o elemento a ser removido e repetir o raciocínio utilizado na inserção, agora para a remoção do início. A primeira coisa é fazer o head apontar para o próximo elemento em relação ao nó que queremos remover: head = nó.next.

head = no.next

Agora o head aponta para o começo da nova lista, já sem o elemento removido. Em seguida, não podemos esquecer de fazer nó.next = null. Isso ajuda o garbage collector (coletor de lixo) e garante que esse nó não será reutilizado inadvertidamente por conta de uma referência residual.

Consolidando a atualização do head e a anulação da referência do nó removido:

head = no.next
no.next = None

Novamente, mexemos em apenas duas referências. Portanto, “remover do início” também é O(1).

Para fixar essas marcações de complexidade:

# Inserir no início - O(1)
# Remover do início - O(1)

Consultando elemento por índice

Agora, suponhamos que precisemos consultar o elemento em uma posição específica da lista. Por exemplo, “verifique qual é o elemento que está na posição 1”.

Quando falamos em posição, precisamos definir uma convenção, pois em lista ligada não há índices nativos. Por convenção, especialmente neste curso, utilizaremos a mesma convenção de um array (vetor): a primeira posição é a posição 0, a segunda é a posição 1, a terceira é a posição 2 e assim por diante. Ou seja, começamos a contar em 0. Assim, ao solicitar o elemento na posição 1, estamos nos referindo ao nó com valor 25.

Apesar dessa convenção, sempre que estivermos resolvendo um problema em uma entrevista de código, é importante confirmar o que está sendo pedido. O enunciado pode especificar que “posição” se refere ao número do elemento começando em 1 (primeiro, segundo, terceiro), o que muda a interpretação. Portanto, vale a pena fazer a pergunta de clarificação no início para garantir que entendemos corretamente o que está sendo solicitado.

Sabendo disso, queremos descobrir como encontrar um elemento em uma posição (índice) específica. Para fazer isso, intuitivamente, precisamos percorrer nossa lista. Assim como vimos no começo, teremos um ponteiro atual apontando primeiro para o começo da lista e alguma variável de contagem para sabermos em qual índice estamos naquele momento — por exemplo, a variável índice.

Inicialmente, apontamos para o começo da lista:

atual = head

Quando entramos na lista, estamos no índice 0. A cada passo que damos dentro dessa lista, caso ainda não tenhamos encontrado o elemento buscado, acompanhamos o índice correspondente ao nó visitado.

Para registrar essa contagem explicitamente:

atual = head
indice = 0

Se não estivermos no índice solicitado, damos um passo e incrementamos esse índice.

Por exemplo, o elemento atual está no índice 0. Não é o índice que buscamos; buscamos o índice 1, então avançamos. Atualizamos atual para atual.next.

Quando chegamos a esse ponto, incrementamos o índice. Avançamos uma posição.

Agora, já chegamos ao índice desejado, então podemos imprimir atual.data e sabemos que o elemento no índice 1 tem o valor 25. Isso vale para qualquer índice da lista.

Ao consultar por índice, no pior caso, podemos solicitar o elemento no final da lista, na posição n-1. Nesse caso, percebemos que o custo é da ordem de n. Encontrar um elemento por índice é linear, proporcional a n. Registramos: consultar por índice é O(n).

Para manter a marcação de complexidade associada a essa operação:

# Remover do início - O(1)
# Consultar por índice - O(n)

Removendo por índice na lista

Para concluir a análise de complexidade da lista, precisamos avaliar o que muda ao remover um elemento a partir de um índice específico, por exemplo, no meio da lista. Suponhamos que queremos remover o elemento no índice 1, mencionado anteriormente. O que precisamos fazer?

Primeiro, precisamos descobrir quem é o elemento no índice 1. Para isso, realizamos uma consulta por índice, que custa O(n). Portanto, a complexidade já é linear. Percorremos a lista e obtemos uma referência para o nó em questão: este é o nó que desejamos remover.

Para removê-lo, precisamos tomar cuidado: é necessário pegar a referência do nó anterior e fazê-la apontar para o próximo do nó que estamos removendo e, em seguida, anular a referência do nó removido. Além do nó a ser removido, precisamos conhecer o nó anterior, o que podemos armazenar durante a própria consulta por índice, mantendo a referência do nó anterior enquanto percorremos a lista. Não há custo adicional de complexidade, mas é fundamental lembrar dessas duas referências.

O que queremos evidenciar? Que operações de inserção por índice — seja no meio da lista ou no final — exigem complexidade O(n). O mesmo vale para remoção por índice: O(n). Se já tivermos a referência direta ao elemento no qual desejamos remover ou após o qual desejamos inserir, a operação se torna mais simples. Por exemplo, se quisermos remover o elemento que vem depois do 15, sabendo quem é o próximo elemento e o próximo do próximo, conseguimos executar a operação diretamente. No entanto, na maioria dos casos, será necessário primeiro encontrar o elemento pelo índice para então realizar a remoção.

Resumindo as complexidades das operações

Para fechar com as marcações finais dessas operações:

# Consultar por índice - O(n)
# Inserir por índice - O(n)

# Inserir por índice - O(n)
# Remover por índice - O(n)

Com essa exposição inicial, já entendemos a estrutura básica de uma lista ligada: como é um nó, como funcionam as referências e as conexões (arestas) entre os elementos. Com base nas complexidades analisadas, podemos começar a exercitar esses conceitos com alguns problemas simples.

Listas ligadas e duplamente ligadas - Meio da lista

Apresentando o problema e a intuição

Vamos exercitar o que nós aprendemos sobre listas ligadas para resolver o problema de encontrar o elemento (ou nó) que está na metade de uma lista.

Temos um exemplo para trabalhar: uma lista com 7 elementos — 3, 2, 32, 16, 23, 5 e 7. O elemento que está na metade da lista tem o valor 16, e é esse que queremos encontrar.

Intuitivamente, para encontrar o elemento do meio, podemos raciocinar assim: se temos 7 elementos na lista, o elemento da metade estará próximo das posições 3 ou 4. Fazemos a conta 7 dividido por 2, que resulta em 3,5. Como não existe a posição 3,5, arredondamos para baixo, ficando com 3. Assim, buscamos o elemento no índice 3 da lista (considerando índices baseados em zero): 0, 1, 2, 3 — que é 16, exatamente o que queremos. Essa já é uma boa intuição de solução, algo que poderíamos expor à pessoa entrevistadora ao descrever a estratégia.

Implementando a contagem inicial

Vamos implementar essa ideia percorrendo a lista. Precisamos de um ponteiro atual apontando para o head. No primeiro passo, precisamos descobrir quantos elementos existem na lista. Para isso, percorremos do começo até o fim, passando por cada elemento e acumulando uma contagem. Criamos a variável count (contagem), inicialmente com valor 0.

Para começar, posicionamos o ponteiro no início:

atual = head

Em seguida, iniciamos a contagem:

count = 0

Utilizamos um laço while: enquanto atual não for nulo (isto é, não chegar ao fim da lista), incrementamos count em 1 (count += 1) e avançamos o ponteiro com atual = atual.next. Vamos verificar esse processo: posicionamos o ponteiro atual de forma a não interferir na visualização, destacamos a variável de contagem, e executamos. No primeiro passo, estamos olhando o primeiro elemento, então a contagem passa a 1. Avançamos para o próximo elemento (ainda não é nulo), somamos mais 1 e continuamos assim até o final. Ao concluir, obtemos count = 7. Primeiro passo concluído.

Começamos escrevendo apenas a condição do laço:

while atual is not None:

Em seguida, adicionamos o incremento da contagem:

while atual is not None:
    count += 1

E por fim avançamos o ponteiro a cada iteração:

while atual is not None:
    count += 1
    atual = atual.next

Calculando o índice do meio e acessando o nó

Agora, queremos descobrir o índice do elemento que está na metade da lista. Pegamos essa contagem, dividimos por 2 e consideramos apenas a parte inteira (equivalente a arredondar para baixo). Em Python, fazemos a divisão inteira com //: count = count // 2. Isso nos dá count = 3.

count = count // 2

Sabemos, então, que queremos encontrar o elemento no índice 3. Para isso, percorremos novamente a lista desde o início, “gastando” essa contagem: a cada passo, decrementamos count e avançamos o ponteiro. Quando count chegar a 0, teremos parado exatamente no nó desejado e, então, imprimimos seu valor.

Fazemos mais um laço: retornamos atual para o começo (apontando para o head) e executamos while count > 0. Enquanto pudermos dar um passo (no exemplo, no máximo 3 passos), decrementamos count e avançamos com atual = atual.next. Ao final, imprimimos atual.data. Executando: após contar os elementos, dividimos count por 2 e obtemos 3. Voltamos o ponteiro para o início e começamos a percorrer novamente, decrementando count a cada passo. Depois de três avanços, chegamos ao nó desejado e imprimimos no console o valor 16.

atual = head

while count > 0:

while count > 0:
    count -= 1
    atual = atual.next

print(atual.data)

Analisando a complexidade

Qual é a complexidade dessa solução? Primeiro, percorremos a lista inteira uma vez, o que é da ordem de O de N. Depois, percorremos até a metade, o que é O de N sobre 2. Para a análise assintótica, o que importa é o termo que cresce mais rápido; ambos são lineares, mas N domina N/2. Portanto, a complexidade de tempo permanece linear: O de N. Em termos de espaço, não utilizamos estrutura auxiliar além da lista original, exceto a variável count, que é constante e independe do tamanho da entrada. Assim, a complexidade de espaço é O de 1.

# Tempo = O(n)
# Espaço = O(1)

Evitando percorrer duas vezes

Vamos pensar agora em uma forma alternativa de resolver esse problema, buscando não percorrer a lista duas vezes. A ideia será tentar percorrer apenas uma vez e já obter o resultado.

Vamos considerar a ideia de que já estamos repetindo o trabalho. Nós já estamos percorrendo todos os elementos. Por que depois precisamos percorrer novamente para chegar ao elemento da metade?

Nós poderíamos aproveitar algum recurso, alguma técnica, para já obter esse resultado quando chegarmos ao final da nossa lista.

Aqui, vamos usar a seguinte intuição: se, de alguma forma, conseguirmos manter a informação de que, por exemplo, estamos olhando para o elemento 3 e sabemos que esse elemento é o elemento da metade da lista, quando avançarmos para o elemento seguinte, saberemos que a metade da lista deveria estar entre esses dois elementos. Nós poderíamos ir guardando essa informação.

Quando avançarmos para o próximo, novamente poderíamos guardar a informação de que esse elemento é o que estaria na metade da lista. Conseguimos repetir isso para todos os elementos. Quando estivermos no 16, ele estará aqui. Quando estivermos no 23, ele estará aqui. É como se, quando estivermos mais à frente, se tivermos andado 5 elementos, tivéssemos outra referência apontando para algo que está na metade desse percurso. Ou seja, um elemento andou 3 e o outro andou 5, em uma proporção aproximada.

Implementando a técnica de dois ponteiros

Vamos resgatar uma técnica que já vimos: a técnica de dois ponteiros. Podemos ter um ponteiro que avança mais rápido à frente, sempre dando dois passos, e um ponteiro que avança mais devagar atrás, na metade da velocidade. Assim, garantimos que, ao olhar para a lista, se estivermos com o ponteiro Fast à frente e o ponteiro Slow atrás, saberemos que Slow percorreu metade dos passos de Fast. Isso significa que Slow está realmente na metade da lista percorrida até aquele momento. Essa é exatamente a intuição que estamos trazendo aqui.

Essa será a ideia da segunda implementação: utilizar a ideia de Slow e Fast — Ponteiro Devagar e Ponteiro Rápido — ou read-write (leitura e escrita), para manter essas duas informações e já responder o que queremos quando chegarmos ao final da lista.

Vamos apagar a implementação inicial e começar a implementar esta abordagem. Inicialmente, os dois ponteiros estarão na mesma posição, no Head da lista: Slow e Fast iguais a Head. Não vamos colocar ainda a condição do while, pois vamos descobri-la conforme implementamos e, em seguida, voltamos para corrigir.

slow = head
fast = head

Em cada passo, o que queremos fazer? Queremos que Slow dê um passo, mas Fast tem que andar no dobro da velocidade. Essa é a ideia: Fast dará dois passos à frente, como se acessássemos .next duas vezes. Teríamos Slow = Slow.next (um passo), e então Fast = Fast.next, repetindo a operação logo abaixo (Fast.next) — para facilitar a leitura, podemos encadear essa operação, de modo que Fast seja igual ao próximo do próximo, ou seja, dois passos à frente.

Primeiro, deixamos apenas o laço sem a condição definitiva:

while True:

Depois, adicionamos o avanço do slow:

while True:
    slow = slow.next

Em seguida, fazemos o fast andar dois passos, inicialmente em duas linhas:

while True:
    slow = slow.next
    fast = fast.next
    fast = fast.next

E, para facilitar a leitura, encadeamos o avanço do fast:

while True:
    slow = slow.next
    fast = fast.next.next

Agora, precisamos determinar a condição para que nada dê errado em cada passo. Para executar a linha que avança Fast dois passos, devemos tomar o seguinte cuidado: para acessar o .next, Fast precisa ser diferente de None. Essa é a primeira regra. Outra condição necessária: Fast.next também precisa ser diferente de None, caso contrário, não conseguimos acessar o próximo .next. Como queremos dar dois passos, tem que ser possível dar esses dois passos. Portanto, as condições são: Fast é diferente de None e Fast.next é diferente de None.

Trocamos, então, o while True pela condição correta e acrescentamos os avanços dentro do laço:

while fast is not None and fast.next is not None:
    slow = slow.next

    fast = fast.next.next

Validando a execução e o invariante

Se esses dois passos forem possíveis, ao terminar o laço, esperamos que o ponteiro Slow esteja na metade do caminho. Ele apontará para o elemento cujo dado queremos imprimir. Vamos, então, simplesmente chegar ao final e fazer um print de SlowData.

print(slow.data)

Ao executar, ocorreu um erro na linha 4: conteúdo inesperado devido a dois pontos a mais. Corrigido o problema, vamos executar novamente.

Temos um ponteiro Slow apontando para o início e um ponteiro Fast que também aponta para o início da lista. Os dois estão no início. Verificamos: Fast é diferente de None e Fast.next também é diferente de None. Podemos avançar e fazer o passo: Slow anda um passo e Fast anda dois passos.

Pela intuição apresentada, se considerarmos a sublista de Head até Fast, sabemos que Slow aponta exatamente para a metade dessa sublista. Esse é o invariante que queremos manter durante todo o algoritmo. Isso ocorre por causa dessa diferença de velocidade entre os ponteiros.

Seguindo, Fast continua diferente de None e Fast.next também continua diferente de None. Fazemos o passo: Slow anda um passo, Fast anda dois, e o invariante continua valendo. Considerando a sublista de Head até Fast, Slow aponta exatamente para o elemento que está na metade.

Chegamos novamente ao while: Fast ainda é válido e Fast.next também é válido. Slow avança uma vez, Fast avança duas vezes, e então verificamos a condição do laço mais uma vez. Fast ainda é diferente de None, o que está ok, mas não conseguimos acessar Fast.next porque ele é None. Se tentássemos fazer Fast.next.next nessa iteração, não daria certo. Portanto, não podemos executar mais um passo. Isso encerra o laço, e imprimimos o dado do nó que está no meio da lista. Chegamos ao resultado desejado.

Analisando complexidade e listas de tamanho par

Quanto à complexidade dessa implementação, podemos olhar para qualquer um dos dois ponteiros. No final das contas, realizamos o mesmo número de operações proporcionais ao percurso. Observando o ponteiro Fast, andamos de 2 em 2 até chegar ao final da lista, o que é equivalente a percorrer n/2.

Nós percorremos a lista pulando de 2 em 2 até o final, ou seja, percorremos metade dos elementos da lista.

Para o slow, percorremos exatamente o número de elementos que representa a metade da lista. Avançamos três posições (1, 2, 3), como fizemos antes.

Isso também será n/2.

Agora temos n/2 mais n/2.

Isso é linear para nós. É mais eficiente que a abordagem anterior, na qual percorremos a lista duas vezes, mas continua sendo linear. Pensando em crescimento de operações, permanece proporcional à quantidade de elementos da lista. Portanto, não muda nada aqui.

Em relação ao espaço, temos duas referências, em vez de um contador. É uma diferença mínima, que não altera o resultado para nós, mas é interessante entendermos essas diferenças sutis de complexidade entre as duas abordagens.

Resolve o nosso problema.

Há um último ponto a trazer: neste caso, convenientemente, tínhamos escolhido uma lista com tamanho ímpar, o que significa que existe um elemento exatamente no meio da lista. Mas e se tivermos uma lista com seis elementos? Por exemplo: vamos remover o último elemento da lista. Se executarmos esse código, qual seria o tipo de resposta que teríamos e o que esperamos do resultado?

Primeiro, vamos executar para garantir que nada quebre. Executamos. Os dois ponteiros estão no início. Avançamos o primeiro passo, depois o segundo passo. O terceiro passo funciona também, porque fast e fast.next ainda são válidos, então fast avança mais uma vez. Chegamos ao final imprimindo 16.

Definindo o meio em listas pares

Assim, para todos os efeitos, quando temos uma lista de tamanho par, consideramos os dois elementos centrais como os elementos que estão na metade da lista. O ideal seria pegar o elemento que está entre os dois, o que não existe. Portanto, podemos considerar qualquer um desses dois elementos como válido para representar o meio da lista. Contudo, por convenção, geralmente se solicita que entreguemos o segundo elemento. Isso facilita a execução de alguns algoritmos.

Um exemplo rápido é verificar se essa lista é um palíndromo. Um palíndromo ocorre quando temos uma sequência até a metade da lista (por exemplo, 3, 2, 32) e, depois, essa sequência se repete em ordem inversa (32, 2, 3). Se já temos o ponteiro apontando para o segundo elemento do meio, podemos pegar a segunda metade da lista ligada, inverter essa lista e comparar elemento a elemento para verificar se correspondem. Se corresponderem, trata-se de um palíndromo. É apenas uma intuição inicial para entendermos por que o segundo elemento pode ser interessante.

Apesar dessa convenção, devemos sempre verificar o enunciado: conferir se não está pedindo para devolver os dois valores, ou o primeiro valor desse par que temos quando a lista é par. A ideia é perguntar e alinhar com a pessoa entrevistadora, entender o que está sendo solicitado e entregar um algoritmo que produza a resposta correta. Esse é o objetivo final.

É isso para este problema. Mencionamos rapidamente a questão de inverter uma lista, e esse será o tema da continuação: como pegar uma lista ligada e realizar a sua inversão.

Sobre o curso Coding Interview: aprenda a resolver problemas com listas, árvores e grafos

O curso Coding Interview: aprenda a resolver problemas com listas, árvores e grafos possui 304 minutos de vídeos, em um total de 68 atividades. Gostou? Conheça nossos outros cursos de Fundamentos de Programação em Back-end, ou leia nossos artigos de Back-end.

Matricule-se e comece a estudar com a gente hoje! Conheça outros tópicos abordados durante o curso:

• Listas ligadas e duplamente ligadas
• Explorando árvores binárias
• Grafos com busca em largura e em profundidade
• Ordenação topológica com o algoritmo de Kahn
• Simulando entrevistas: listas, árvores e grafos na prática