Reverse Linked List

Q: Como inverter uma lista encadeada no próprio lugar?

Percorra a lista com dois ponteiros: prev começando em nada e node começando na cabeça. Em cada nó, salve o próximo nó, aponte seu link para prev e, em seguida, avance prev e node um passo. Quando node chegar ao fim, prev será a cabeça da lista invertida.

Q: Qual é a complexidade de tempo e espaço para inverter uma lista encadeada?

A versão iterativa visita cada nó uma vez, tempo O(n) , e mantém três ponteiros, espaço extra O(1) . Copiar a ordem para um array primeiro também leva tempo O(n) , mas precisa de espaço extra O(n) . Uma versão recursiva usa O(n) de espaço para a pilha de chamadas.

FácilLista ligada

+10

Você recebe uma lista simplesmente encadeada armazenada no array next: o nó i aponta para o nó next[i], -1 encerra a lista e o início é o nó 0. Os nós não estão armazenados na ordem da lista, então siga os links.

Inverta a lista invertendo cada link, de modo que o antigo último nó se torne o início e o nó 0 se torne o último, apontando para -1. Retorne o array next atualizado, que tem o mesmo tamanho que a entrada.

Função

reverseList(next: integer-array) → integer-array

nextinteger-array: o índice do nó ao qual cada nó está ligado, ou -1 para o último nó
Retornainteger-array: o próximo array da lista invertida

Restrições

1 ≤ next.length ≤ 5000
Cada next[i] é -1 ou um índice de nó de 0 a next.length-1.
A partir do nó 0, a lista visita cada nó exatamente uma vez e então chega a -1. Não há ciclo.

Exemplos

Entrada: next = [1, 2, 3, -1]
Saída: [-1, 0, 1, 2]
Explicação: A lista é 0 → 1 → 2 → 3. Invertida, ela fica 3 → 2 → 1 → 0, então o nó 3 aponta para 2, o nó 2 para 1, o nó 1 para 0 e o nó 0 para -1.

Entrada: next = [2, -1, 3, 1]
Saída: [-1, 3, 0, 2]
Explicação: A lista é 0 → 2 → 3 → 1 e, invertida, fica 1 → 3 → 2 → 0. Escrever cada novo link no índice do seu nó resulta em [-1, 3, 0, 2]. Inverter o próprio array resultaria em [1, 3, -1, 2], o que não é a mesma coisa.

Entrada: next = [-1]
Saída: [-1]
Explicação: Um nó é o seu próprio reverso. Ele continua sendo a cabeça e a cauda, e ainda aponta para -1.

+11 testes ocultos ao enviar

Para ir além

Você consegue inverter apenas a parte da lista entre a posição left e a posição right, deixando os nós anteriores e posteriores no mesmo lugar?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Inverter uma lista não move nenhum nó; isso apenas inverte cada ligação. O problema é que a ligação de um nó é a única maneira de acessar o restante da lista, então, no momento em que você a sobrescreve, tudo o que vem depois se perde. Você pode evitar o problema anotando a ordem primeiro ou percorrendo a lista uma vez com três ponteiros que salvam o caminho adiante antes de cada ligação ser invertida.

Escreva a ordem e, em seguida, refaça os vínculos

Intuição

Neste problema, um ponteiro é um índice de nó, e avançar é node = next[node]. Percorra a lista a partir do nó 0 até chegar a -1 e anote todos os nós pelos quais passar. No segundo exemplo, isso resulta na ordem [0, 2, 3, 1].

Na lista invertida, cada nó aponta para o nó que veio antes dele nessa ordem: 1 aponta para 3, 3 para 2, 2 para 0. O primeiro nó da ordem, a antiga cabeça, não tem nada antes dele, então aponta para -1. Preencha um novo array com esses apontamentos e retorne-o.

Como cada apontamento é gravado em um array novo, nada é sobrescrito enquanto você ainda precisa dele, o que torna difícil errar nesta versão. Ela leva tempo O(n) e usa memória extra O(n) para a ordem e o novo array.

Algoritmo

Percorra os nós de 0 a -1 e acrescente cada nó a order.
Crie um novo array com o mesmo comprimento.
Defina a entrada de order[0] como -1.
Para todo k ≥ 1, defina a entrada de order[k] como order[k-1].
Retorne o novo array.

def reverseList(next):
    order = []
    node = 0
    while node != -1:
        order.append(node)
        node = next[node]
    reversed_next = [0] * len(next)
    reversed_next[order[0]] = -1  # the old head ends the new list
    for k in range(1, len(order)):
        reversed_next[order[k]] = order[k - 1]
    return reversed_next

Inverta os links de uma só vez

Intuição

Você pode inverter cada ligação no momento em que chega ao nó correspondente, se lembrar de qual nó veio. Mantenha prev, o nó atrás de você, começando em -1, porque a antiga cabeça se tornará o último nó. Em node, a ligação next[node] aponta para a frente; defina-a como prev para que aponte para trás.

Essa gravação destrói seu único caminho para a frente, então salve-o primeiro em uma terceira variável, after = next[node]. Em seguida, inverta a ligação e avance os dois ponteiros uma posição: prev = node, node = after. A todo momento, os nós atrás de você formam uma lista invertida encabeçada por prev, e os nós à frente são o restante ainda não alterado, começando em node. Quando node chega a -1, todas as ligações foram invertidas e prev é a nova cabeça.

No segundo exemplo, os ponteiros percorrem os nós 0, 2, 3, 1, gravando next[0] = -1, next[2] = 0, next[3] = 2 e next[1] = 3. Cada nó é visitado uma vez: tempo O(n), e a única memória usada são três inteiros: O(1).

Algoritmo

Defina prev = -1 e node = 0.
Enquanto node não for -1, salve after = next[node].
Defina next[node] = prev.
Avance: prev = node, depois node = after.
Retorne next.

def reverseList(next):
    prev = -1  # the node behind the current one; the old head will point to -1
    node = 0
    while node != -1:
        after = next[node]  # save the rest of the list before cutting the link
        next[node] = prev
        prev = node
        node = after
    return next

Armadilhas e casos extremos

Quase todos os bugs aqui têm a ver com a ordem das três atribuições ou com as duas extremidades da lista.

Sobrescrever next[node] antes de salvá-lo. Depois de next[node] = prev, o link antigo para a frente se perde, e o percurso volta para trás em vez de seguir para o próximo nó.
Iniciar prev com qualquer valor diferente de -1. A antiga cabeça deve terminar a nova lista. Iniciar com 0 faz o nó 0 apontar para si mesmo.
Inverter o array em vez dos links. Os nós não são armazenados na ordem da lista, e a resposta mantém cada nó no próprio índice; apenas os valores mudam. Inverter [2, -1, 3, 1] resulta em [1, 3, -1, 2], não em [-1, 3, 0, 2].
Parar um nó antes usando um loop com next[node] != -1. O link do último nó também precisa ser invertido, então faça o loop enquanto node != -1.
Inverter usando recursão em uma lista longa. Uma lista de 5000 nós exige 5000 chamadas aninhadas, ultrapassando o limite de 1000 do Python.
Esquecer o deslocamento em Lua e R, onde os arrays começam em 1. Mantenha os índices dos nós baseados em 0 e leia next[node + 1]. Ruby e R reservam a palavra next, então, nos códigos iniciais, o parâmetro recebe o nome next_.

Perguntas frequentes4

Como inverter uma lista encadeada no próprio lugar?

Percorra a lista com dois ponteiros: prev começando em nada e node começando na cabeça. Em cada nó, salve o próximo nó, aponte seu link para prev e, em seguida, avance prev e node um passo. Quando node chegar ao fim, prev será a cabeça da lista invertida.

Qual é a complexidade de tempo e espaço para inverter uma lista encadeada?

A versão iterativa visita cada nó uma vez, tempo O(n), e mantém três ponteiros, espaço extra O(1). Copiar a ordem para um array primeiro também leva tempo O(n), mas precisa de espaço extra O(n). Uma versão recursiva usa O(n) de espaço para a pilha de chamadas.

Você consegue inverter uma lista encadeada recursivamente?

Sim. Inverta tudo depois da cabeça, depois faça o antigo próximo nó da cabeça apontar de volta para a cabeça e defina o link da cabeça como vazio. A leitura é boa, mas isso faz uma chamada aninhada por nó, então uma lista longa pode exceder a capacidade da pilha de chamadas. Por padrão, Python interrompe após 1000 chamadas, limite excedido por uma lista de 5000 nós.

Por que inverter uma lista encadeada requer três ponteiros?

Para inverter o link de um nó, você precisa do próprio nó e do nó anterior a ele, ou seja, de dois ponteiros. O terceiro mantém o nó seguinte, porque inverter o link apaga a única referência ao restante da lista. Sem ele, não é possível continuar a percorrê-la.

Python

def reverseList(next):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

next = [1, 2, 3, -1]

Esperado

[-1, 0, 1, 2]