Reorder List

Q: Por que inverter a segunda metade da lista?

A resposta percorre a segunda metade do último nó até o primeiro, e uma lista simplesmente encadeada só avança. Inverter a segunda metade uma vez, em O(n) , permite que a intercalação percorra as duas metades para a frente.

Q: Qual é a complexidade de tempo de Reorder List?

O método no próprio local é executado em tempo O(n) com memória extra O(1) : encontrar o meio, inverter e entrelaçar percorrem cada nó um número constante de vezes. Copiar os valores para um array também leva tempo O(n) , mas requer memória O(n) , e avançar a cauda um nó de cada vez leva O(n²) .

Q: Onde fica o meio quando a lista tem um número par de nós?

Pare o ponteiro lento no último nó da metade da frente. Com seis nós, as metades têm três e três; com cinco, têm três e dois. O nó extra encerra a resposta, que é onde a ordem coloca o valor do meio.

MédioLista ligada Ponteiros rápido e lento Dois ponteiros

+10

Você recebe uma lista simplesmente encadeada armazenada em dois arrays de mesmo comprimento. 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 links.

Chame os nós na ordem da lista de L0, L1, ..., Lk. Reordene a lista para que ela fique na sequência L0, Lk, L1, Lk-1, L2, Lk-2, ...: primeiro o primeiro nó, depois o último, depois o segundo, depois o penúltimo, e assim por diante. Retorne os valores nessa nova ordem.

Função

reorderList(next: integer-array, values: integer-array) → integer-array

nextinteger-array: o índice do nó para o qual cada nó aponta, ou -1 para o último nó
valuesinteger-array: o valor armazenado por cada nó
Retornainteger-array: os valores na ordem reordenada da lista

Restrições

1 ≤ n ≤ 4000, em que n é o comprimento de next e de values.
-1000 ≤ values[i] ≤ 1000
Cada next[i] é -1 ou um índice de nó de 0 a n-1.
Começando no nó 0, a lista visita cada nó exatamente uma vez e então chega a -1. Não há ciclo.

Exemplos

Entrada: next = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
Saída: [1, 5, 2, 4, 3]
Explicação: Seguindo os links a partir do nó 0, a lista é 1, 2, 3, 4, 5. Primeiro, último, segundo e penúltimo resultam em 1, 5, 2, 4, e o valor do meio 3 vem por último.

Entrada: next = [2, 3, 1, -1]values = [10, 30, 20, 40]
Saída: [10, 40, 20, 30]
Explicação: A lista visita os nós 0, 2, 1, 3 e lê 10, 20, 30, 40. O primeiro e o último fornecem 10, 40; depois, o par interno fornece 20, 30.

Entrada: next = [-1]values = [7]
Saída: [7]
Explicação: Uma lista com um nó não tem nada para mover, então a resposta é [7].

Para ir além

Você consegue reordenar os próprios links usando memória extra O(1)?

Dicas

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

0 de 3 abertas

Solução

A nova ordem alterna entre o início e o fim, mas uma lista simplesmente encadeada só percorre para a frente. Divida o trabalho em três operações padrão de listas: encontre o meio com ponteiros lento e rápido, inverta a metade de trás e intercale as duas metades, um nó de cada vez.

Avance a cauda, um nó de cada vez

Intuição

Um ponteiro aqui é um índice de nó, e avançar é node = next[node]. Depois do primeiro nó vem o último, então desvincule o último nó e insira-o depois do atual; em seguida, repita dois nós adiante. Para 1, 2, 3, 4, 5, isso resulta em 1, 5, 2, 3, 4 e, depois, em 1, 5, 2, 4, 3. Pare quando houver menos de dois nós depois do atual.

Encontrar o nó anterior ao último exige percorrer a lista até o fim a cada rodada. Os percursos diminuem em dois nós por rodada, totalizando cerca de n²/4 movimentos: quatro milhões para 4000 nós.

Algoritmo

Defina cur = 0.
Enquanto pelo menos dois nós vierem depois de cur, percorra before a partir de cur até que next[next[before]] == -1, de modo que tail = next[before] seja o último nó.
Desvincule-o com next[before] = -1 e, em seguida, insira-o: next[tail] = next[cur] e next[cur] = tail.
Mova cur para next[tail] e repita.
Percorra a partir do nó 0 e colete os valores.

def reorderList(next, values):
    cur = 0
    # While at least two nodes follow cur, move the last node right after cur.
    while next[cur] != -1 and next[next[cur]] != -1:
        before = cur
        while next[next[before]] != -1:  # find the node before the tail
            before = next[before]
        tail = next[before]
        next[before] = -1
        next[tail] = next[cur]
        next[cur] = tail
        cur = next[tail]
    result = []
    node = 0
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Copie os valores e leia de ambas as extremidades

Intuição

Um array chega ao seu último elemento em uma etapa. Copie os valores na ordem da lista, [1, 2, 3, 4, 5] no primeiro exemplo, depois leia usando lo na frente e hi atrás: pegue lo, pegue hi e mova ambos para dentro enquanto lo < hi. Isso resulta em 1, 5, 2, 4; com um comprimento ímpar, ambos se encontram no 3 do meio, que fica por último.

Isso leva O(n) de tempo e O(n) de memória extra, e os links nunca mudam.

Algoritmo

Percorra a partir do nó 0 e acrescente cada valor a inOrder.
Defina lo = 0 e hi como o último índice.
Enquanto lo < hi, acrescente inOrder[lo] e inOrder[hi], depois incremente lo e decremente hi.
Se lo == hi, acrescente o valor do meio.

def reorderList(next, values):
    # Write the values out in list order.
    in_order = []
    node = 0
    while node != -1:
        in_order.append(values[node])
        node = next[node]
    # Take from the front and the back in turn.
    result = []
    lo, hi = 0, len(in_order) - 1
    while lo < hi:
        result.append(in_order[lo])
        result.append(in_order[hi])
        lo += 1
        hi -= 1
    if lo == hi:  # odd length: the middle value comes last
        result.append(in_order[lo])
    return result

Encontre o meio, inverta a metade de trás, entrelace

Intuição

Para 1, 2, 3, 4, 5, 6, a resposta é 1, 6, 2, 5, 3, 4: a metade da frente 1, 2, 3 em ordem, alternando com a metade de trás 4, 5, 6 lida de trás para frente. Portanto, corte a lista no meio, inverta a metade de trás e intercale.

slow avança um link enquanto fast avança dois, então slow para no último nó da metade da frente: o 3, tanto para cinco quanto para seis nós. Cortar depois dele faz com que a metade da frente tenha um nó a mais quando o comprimento é ímpar, e esse nó encerra a resposta. A intercalação pega um nó de cada metade, alternadamente, até que a metade de trás acabe.

Cada nó é acessado um número constante de vezes, com alguns índices de memória. R copia o vetor de links na primeira alteração, então, em R, a memória é O(n).

Algoritmo

Mova slow um elo e fast dois elos enquanto next[fast] e next[next[fast]] não forem -1.
Defina second = next[slow], depois next[slow] = -1.
Inverta a lista que começa em second; sua nova cabeça é prev.
Entrelace: enquanto second não for -1, ligue first a second e second ao antigo next[first], depois avance ambos.
Percorra a partir do nó 0 e colete os valores.

def reorderList(next, values):
    # 1. Find the middle: slow stops on the last node of the first half.
    slow = fast = 0
    while next[fast] != -1 and next[next[fast]] != -1:
        slow = next[slow]
        fast = next[next[fast]]
    second = next[slow]
    next[slow] = -1  # cut the list in two
    # 2. Reverse the second half.
    prev = -1
    while second != -1:
        after = next[second]
        next[second] = prev
        prev = second
        second = after
    # 3. Weave: one node from the front half, one from the reversed back half.
    first, second = 0, prev
    while second != -1:
        first_after, second_after = next[first], next[second]
        next[first] = second
        next[second] = first_after
        first, second = first_after, second_after
    result = []
    node = 0
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Armadilhas e casos extremos

Não cortar a lista depois do meio. Sem next[slow] = -1, a metade da frente ainda aponta para a metade de trás e, após a intercalação, a lista volta para si mesma em um loop.
Sobrescrever um link antes de salvá-lo. Na inversão e na intercalação, leia next[node] em uma variável primeiro, ou o restante da lista será perdido.
Intercalar até o fim da metade da frente. Com um comprimento ímpar, esse loop executa mais uma vez com second em -1 e lê next[-1].
Ler a ordem do array como a ordem da lista. No primeiro exemplo, values é [1, 3, 5, 2, 4], mas a lista é 1, 2, 3, 4, 5.
Em Lua e R, os arrays começam em 1. Mantenha os índices dos nós baseados em 0 e leia next[node + 1].

Perguntas frequentes3

Por que inverter a segunda metade da lista?

A resposta percorre a segunda metade do último nó até o primeiro, e uma lista simplesmente encadeada só avança. Inverter a segunda metade uma vez, em O(n), permite que a intercalação percorra as duas metades para a frente.

Qual é a complexidade de tempo de Reorder List?

O método no próprio local é executado em tempo O(n) com memória extra O(1): encontrar o meio, inverter e entrelaçar percorrem cada nó um número constante de vezes. Copiar os valores para um array também leva tempo O(n), mas requer memória O(n), e avançar a cauda um nó de cada vez leva O(n²).

Onde fica o meio quando a lista tem um número par de nós?

Pare o ponteiro lento no último nó da metade da frente. Com seis nós, as metades têm três e três; com cinco, têm três e dois. O nó extra encerra a resposta, que é onde a ordem coloca o valor do meio.

def reorderList(next, values):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

next = [3, 4, -1, 1, 2]
values = [1, 3, 5, 2, 4]

Saída Esperada

[1, 5, 2, 4, 3]

Reorder List

Função

Restrições

Exemplos

Dicas

Solução

Avance a cauda, um nó de cada vez

Copie os valores e leia de ambas as extremidades

Encontre o meio, inverta a metade de trás, entrelace

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos