Middle of the Linked List
Você recebe uma lista simplesmente encadeada armazenada em dois arrays de mesmo tamanho. O nó i contém o valor values[i] e aponta para o nó next[i]; -1 encerra a lista, e a cabeça é o nó 0. Os nós não estão armazenados na ordem da lista, então siga os ponteiros.
Retorne o valor do nó do meio. Quando a lista tem um número par de nós, há dois nós do meio; retorne o valor do segundo.
Função
- valuesinteger-array
- o valor armazenado por cada nó
- nextinteger-array
- o índice do nó ao qual cada nó se conecta, ou -1 para o último nó
- Retornainteger
- o valor do nó do meio, o segundo nó do meio quando o comprimento é par
Restrições
1 ≤ n ≤ 5000, em quené o comprimento devaluese denext.-104 ≤ values[i] ≤ 104- Cada
next[i]é-1ou um índice de nó de0an-1. - A partir do nó
0, a lista visita cada nó exatamente uma vez e depois chega a-1. Não há ciclo.
Exemplos
- Entrada
- values = [4, 9, 2, 7, 5]next = [3, -1, 1, 4, 2]
- Saída
- 5
- Explicação
- Seguindo os links a partir do nó
0, chegamos aos nós0, 3, 4, 2, 1, então a lista é4, 7, 5, 2, 9. O terceiro dos cinco é o nó4, cujo valor é5. A entrada do meio do próprio array,values[2] = 2, é um nó diferente.
- Entrada
- values = [10, 20, 30, 40, 50, 60]next = [1, 2, 3, 4, 5, -1]
- Saída
- 40
- Explicação
- Aqui os nós são armazenados em ordem. Com seis nós, há dois nós do meio,
30e40, e o segundo é escolhido.
- Entrada
- values = [8]next = [-1]
- Saída
- 8
- Explicação
- Uma lista com um nó tem a si mesma como elemento do meio.
+13 testes ocultos ao enviar
Para ir além
Você consegue retornar o nó que está a um terço do início da lista em uma única passagem? Com que velocidade cada ponteiro se moveria e onde você pararia?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Você não sabe o comprimento da lista até chegar ao final dela. E se dois caminhantes começassem no início e um deles se movesse duas vezes mais rápido que o outro?
Quando o ponteiro mais rápido chega ao fim, o mais lento percorreu metade da distância, então está no nó do meio. O único detalhe que falta é quando parar para que, em uma lista de tamanho par, ele fique no segundo nó do meio.
Comece
slowefastno nó0. Enquantofastnão for-1enext[fast]não for-1, avance slow um elo e fast dois elos. Em seguida, retornevalues[slow].
Solução
Em um array, o meio fica no índice n / 2. Uma lista encadeada não tem índice: você só descobre o tamanho dela percorrendo-a até o fim e, quando chega lá, já passou do meio. Você pode copiar a lista para um array ou contar os elementos primeiro e percorrê-la novamente. A solução elegante envia dois ponteiros pela lista em velocidades diferentes, de modo que o ponteiro lento esteja na metade quando o rápido chegar ao fim.
Copie os valores para um array
Intuição
Neste problema, um ponteiro é o índice de um nó. Avançar para o próximo nó é node = next[node], e chegar a -1 significa que você passou do fim. No primeiro exemplo, o percurso a partir do nó 0 segue 0 → 3 → 4 → 2 → 1 → -1.
O problema de uma lista é que não dá para saltar para uma posição. Então transforme-a em algo que permita isso: percorra a lista uma vez e, ao passar por cada valor, acrescente-o a um novo array. Esse array contém os valores na ordem da lista — [4, 7, 5, 2, 9] no primeiro exemplo —, e o meio fica no índice length / 2, usando divisão inteira.
Esse índice, por si só, fornece o segundo elemento do meio quando o comprimento é par: seis valores dão o índice 3, o quarto valor, que é 40 no segundo exemplo. O percurso leva O(n) tempo, e a cópia usa O(n) de memória extra, o que as próximas duas abordagens evitam.
Algoritmo
- Comece com um array vazio e
node = 0. - Enquanto
nodenão for-1, adicionevalues[node]e avance paranext[node]. - Retorne a entrada no índice
length / 2, arredondado para baixo.
def middleNode(values, next):
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
return in_order[len(in_order) // 2]Conte e, em seguida, caminhe até a metade
Intuição
Você não precisa da cópia inteira, apenas do comprimento. Percorra a lista uma vez e conte os nós. Depois, recomece pela cabeça e avance length / 2 passos, arredondando para baixo. O nó em que você parar é o do meio.
Por que esse número de passos: após k passos, você estará no nó da posição k, contando a cabeça como posição 0. O meio de uma lista de 5 está na posição 2, e o segundo nó do meio de uma lista de 6 está na posição 3; ambos correspondem a length / 2. No primeiro exemplo, você conta 5, avança dois passos 0 → 3 → 4 e lê values[4] = 5.
Agora, o uso de memória é O(1). O custo é uma segunda passagem por metade da lista, totalizando 1.5n movimentos, o que ainda é O(n).
Algoritmo
- Percorra do nó
0ao nó-1e conte os nós. - Volte ao nó
0. - Execute
node = next[node]exatamentecount / 2vezes, arredondando para baixo. - Retorne
values[node].
def middleNode(values, next):
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
node = 0
for _ in range(length // 2):
node = next[node]
return values[node]Dois ponteiros: rápido e lento
Intuição
Coloque dois ponteiros no início. A cada rodada, slow avança um nó e fast avança dois. Após k rodadas, slow está na posição k e fast na posição 2k, então slow sempre percorreu metade da distância de fast. Quando fast chega ao fim, slow está no meio, e você não precisou saber o comprimento.
A condição de parada determina qual meio você obtém. Continue enquanto fast for um nó válido e houver um nó depois dele: fast != -1 e next[fast] != -1. Com um comprimento ímpar, fast para no último nó. Com um comprimento par, fast sai do fim e vai para -1, o que faz slow avançar mais um passo, até o segundo nó do meio. No segundo exemplo, slow percorre 0, 1, 2, 3, enquanto fast percorre 0, 2, 4, -1, e values[3] é 40.
No primeiro exemplo, slow visita os nós 0, 3, 4, enquanto fast visita 0, 4, 1; o nó 1 é o último, então o loop para com slow no nó 4 e a resposta é 5. Fast faz cerca de n movimentos e slow, n / 2, em uma única passagem e usando dois inteiros de memória.
Algoritmo
- Defina
slow = 0efast = 0. - Enquanto
fast != -1enext[fast] != -1, definaslow = next[slow]efast = next[next[fast]]. - Retorne
values[slow].
def middleNode(values, next):
slow = fast = 0
# Stop when fast is on the last node or has stepped past it.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
return values[slow]
Armadilhas e casos extremos
O loop é curto, então os erros estão em onde ele começa, onde termina e o que retorna.
- Retornar
values[n / 2]. Os nós não são armazenados na ordem da lista, então a entrada do meio do array geralmente é algum outro nó. No primeiro exemplo, isso retorna2em vez de5. - Obter o primeiro nó do meio quando o comprimento é par. Um loop que executa enquanto
next[fast]enext[next[fast]]forem ambos válidos para uma rodada antes e retorna30em vez de40no segundo exemplo. - Verificar
next[fast]antes defast != -1. Quando o comprimento é par, fast se torna-1, e acessarnext[-1]causa um erro na maioria das linguagens. Em Python, esse acesso lê silenciosamente a última entrada, o que é pior. - Percorrer
count / 2 - 1passos ou arredondar para cima na abordagem de contagem. Conte a cabeça como posição0e avance exatamentecount / 2passos, arredondando para baixo. - Retornar o índice do nó em vez do seu valor.
- Esquecer o deslocamento em Lua e R, onde os arrays começam em 1. Mantenha os índices dos nós baseados em 0 e acesse
next[node + 1]. Ruby e R reservam a palavranext, então as soluções iniciais dessas linguagens chamam o parâmetro denext_.
Perguntas frequentes4
Por que os ponteiros rápido e lento encontram o meio de uma lista encadeada?
Ambos começam no início, e a cada rodada o ponteiro rápido avança dois nós, enquanto o lento avança um. Após k rodadas, o ponteiro rápido está na posição 2k e o lento, na posição k, exatamente à metade da distância. Portanto, quando o ponteiro rápido chega ao fim da lista, o lento está no meio dela.
Qual é a complexidade de tempo e espaço para encontrar o meio de uma lista encadeada?
As três abordagens levam O(n) tempo, já que não é possível encontrar o meio sem percorrer cerca de metade da lista ou mais. Copiar os valores usa O(n) de memória extra. Contar primeiro e usar os ponteiros rápido e lento consomem O(1), e os ponteiros precisam de apenas uma passagem.
Como retornar o primeiro nó do meio em vez do segundo?
Altere a condição de parada para que o ponteiro rápido pare uma rodada antes: faça o loop enquanto next[fast] != -1 e next[next[fast]] != -1. Para seis nós, o ponteiro lento então para na posição 2 em vez de 3. Na abordagem de contagem, percorra (count - 1) / 2 passos em vez de count / 2.
Onde mais a técnica dos ponteiros rápido e lento é usada?
As mesmas duas velocidades detectam um ciclo em uma lista encadeada: em um ciclo, o ponteiro rápido dá uma volta no lento, e eles se encontram. Elas também encontram onde um ciclo começa e dividem uma lista ao meio para a ordenação por intercalação ou para verificar se uma lista é lida da mesma forma nas duas direções.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def middleNode(values, next):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
values = [4, 9, 2, 7, 5] next = [3, -1, 1, 4, 2]
Esperado
5