Reverse Linked List

Q: Jak odwrócić listę jednokierunkową w miejscu?

Przejdź przez listę za pomocą dwóch wskaźników: prev zaczyna od niczego, a node od głowy listy. Przy każdym węźle zapisz jego następny węzeł, ustaw jego łącze na prev , a następnie przesuń prev i node o jeden krok do przodu. Gdy zabraknie węzłów, prev będzie głową odwróconej listy.

Q: Jaka jest złożoność czasowa i pamięciowa odwracania listy połączonej?

Wersja iteracyjna odwiedza każdy węzeł raz, czas O(n) , i przechowuje trzy wskaźniki, dodatkowa pamięć O(1) . Najpierw skopiowanie kolejności do tablicy również zajmuje czas O(n) , ale wymaga dodatkowej pamięci O(n) . Wersja rekurencyjna używa O(n) pamięci na stos wywołań.

ŁatweLista wiązana

+10

Otrzymujesz listę jednokierunkową przechowywaną w tablicy next: węzeł i wskazuje na węzeł next[i], -1 oznacza koniec listy, a głową jest węzeł 0. Węzły nie są przechowywane w kolejności występowania na liście, więc podążaj za odnośnikami.

Odwróć listę, odwracając każdy odnośnik, tak aby dawny ostatni węzeł stał się głową, a węzeł 0 stał się ostatnim węzłem i wskazywał na -1. Zwróć zaktualizowaną tablicę next, która ma taką samą długość jak dane wejściowe.

Funkcja

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

nextinteger-array: indeks węzła, do którego prowadzi każdy węzeł, lub -1 dla ostatniego węzła
Zwracainteger-array: następna tablica odwróconej listy

Ograniczenia

1 ≤ next.length ≤ 5000
Każdy element next[i] ma wartość -1 lub indeks węzła od 0 do next.length-1.
Rozpoczynając od węzła 0, lista odwiedza każdy węzeł dokładnie raz, a następnie dociera do -1. Nie ma cyklu.

Przykłady

Wejście: next = [1, 2, 3, -1]
Wyjście: [-1, 0, 1, 2]
Wyjaśnienie: Lista to 0 → 1 → 2 → 3. Po odwróceniu jest to 3 → 2 → 1 → 0, więc węzeł 3 łączy się z 2, węzeł 2 z 1, węzeł 1 z 0, a węzeł 0 z -1.

Wejście: next = [2, -1, 3, 1]
Wyjście: [-1, 3, 0, 2]
Wyjaśnienie: Lista to 0 → 2 → 3 → 1, a po odwróceniu 1 → 3 → 2 → 0. Zapisanie każdego nowego łącza pod indeksem jego węzła daje [-1, 3, 0, 2]. Odwrócenie samej tablicy dałoby [1, 3, -1, 2], co nie jest tym samym.

Wejście: next = [-1]
Wyjście: [-1]
Wyjaśnienie: Jeden węzeł jest swoim własnym odwróceniem. Pozostaje głową i ogonem, a nadal wskazuje na -1.

+11 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy możesz odwrócić tylko część listy między pozycją left a pozycją right i pozostawić wcześniejsze oraz późniejsze węzły na swoich miejscach?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Odwrócenie listy nie przesuwa żadnego węzła; zmienia kierunek każdego łącza. Problem polega na tym, że łącze węzła to jedyny sposób dotarcia do pozostałej części listy, więc gdy tylko je nadpiszesz, wszystko, co znajduje się za nim, zostaje utracone. Możesz uniknąć tego problemu, najpierw zapisując kolejność, albo przejść listę raz, używając trzech wskaźników, które przed zmianą kierunku każdego łącza zachowują drogę naprzód.

Zapisz kolejność, a następnie połącz ponownie

Intuicja

W tym zadaniu wskaźnik to indeks węzła, a przejście do przodu wykonuje się za pomocą node = next[node]. Idź od węzła 0, aż dotrzesz do -1, i zapisuj każdy mijany węzeł. W drugim przykładzie otrzymasz kolejność [0, 2, 3, 1].

Na odwróconej liście każdy węzeł wskazuje węzeł, który w tej kolejności znajdował się przed nim: 1 wskazuje 3, 3 wskazuje 2, a 2 wskazuje 0. Pierwszy węzeł w kolejności, czyli stara głowa, nie ma nic przed sobą, więc wskazuje -1. Wypełnij nową tablicę tymi odwołaniami i ją zwróć.

Ponieważ każde odwołanie zapisujesz w nowej tablicy, nic nie zostaje nadpisane, gdy nadal jest potrzebne, dzięki czemu trudno popełnić błąd w tej wersji. Zajmuje ona O(n) czasu i O(n) dodatkowej pamięci na kolejność oraz nową tablicę.

Algorytm

Przejdź od węzła 0 do -1 i dołącz każdy węzeł do order.
Utwórz nową tablicę o tej samej długości.
Ustaw element order[0] na -1.
Dla każdego k ≥ 1 ustaw element order[k] na order[k-1].
Zwróć nową tablicę.

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

Odwróć kierunek linków w jednym przebiegu

Intuicja

Możesz odwracać każde połączenie w chwili, gdy dotrzesz do jego węzła, jeśli pamiętasz węzeł, z którego przyszedłeś. Przechowuj prev, czyli węzeł za tobą, zaczynając od -1, ponieważ dotychczasowa głowa stanie się ostatnim węzłem. W węźle node połączenie next[node] wskazuje do przodu; ustaw je na prev, aby wskazywało do tyłu.

Ten zapis niszczy jedyną drogę naprzód, więc najpierw zachowaj ją w trzeciej zmiennej: after = next[node]. Następnie odwróć połączenie i przesuń oba wskaźniki o jeden krok: prev = node, node = after. W każdej chwili węzły za tobą tworzą odwróconą listę, której głową jest prev, a węzły przed tobą stanowią nienaruszoną resztę, zaczynającą się od node. Gdy node osiągnie wartość -1, wszystkie połączenia zostaną odwrócone, a prev będzie nową głową.

W drugim przykładzie wskaźniki przechodzą przez węzły 0, 2, 3, 1, zapisując next[0] = -1, next[2] = 0, next[3] = 2 i next[1] = 3. Każdy węzeł jest odwiedzany raz, co zajmuje czas O(n), a jedyna potrzebna pamięć to trzy liczby całkowite, czyli O(1).

Algorytm

Ustaw prev = -1 i node = 0.
Dopóki node nie jest równe -1, zapisz after = next[node].
Ustaw next[node] = prev.
Przejdź dalej: prev = node, następnie node = after.
Zwróć 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

Pułapki i przypadki brzegowe

Prawie każdy błąd tutaj dotyczy kolejności trzech przypisań albo dwóch końców listy.

Nadpisanie next[node] przed zapisaniem tej wartości. Po next[node] = prev stare łącze do przodu znika, a przejście prowadzi wstecz zamiast do następnego węzła.
Ustawienie początkowej wartości prev na coś innego niż -1. Stara głowa musi zakończyć nową listę. Ustawienie początkowej wartości na 0 powoduje, że węzeł 0 wskazuje sam na siebie.
Odwrócenie tablicy zamiast łączy. Węzły nie są przechowywane w kolejności listy, a odpowiedź pozostawia każdy węzeł pod jego własnym indeksem — zmieniają się tylko wartości. Odwrócenie [2, -1, 3, 1] daje [1, 3, -1, 2], a nie [-1, 3, 0, 2].
Zakończenie o jeden węzeł za wcześnie przez użycie pętli z warunkiem next[node] != -1. Łącze ostatniego węzła też musi zostać odwrócone, więc wykonuj pętlę, dopóki node != -1.
Odwracanie długiej listy za pomocą rekurencji. Lista zawierająca 5000 węzłów wymaga 5000 zagnieżdżonych wywołań, co przekracza limit Pythona wynoszący 1000.
Zapomnienie o przesunięciu w Lua i R, gdzie indeksowanie tablic zaczyna się od 1. Pozostaw indeksy węzłów numerowane od 0 i odczytuj next[node + 1]. Ruby i R rezerwują słowo next, dlatego w rozwiązaniach startowych parametr nosi nazwę next_.

Najczęstsze pytania4

Jak odwrócić listę jednokierunkową w miejscu?

Przejdź przez listę za pomocą dwóch wskaźników: prev zaczyna od niczego, a node od głowy listy. Przy każdym węźle zapisz jego następny węzeł, ustaw jego łącze na prev, a następnie przesuń prev i node o jeden krok do przodu. Gdy zabraknie węzłów, prev będzie głową odwróconej listy.

Jaka jest złożoność czasowa i pamięciowa odwracania listy połączonej?

Wersja iteracyjna odwiedza każdy węzeł raz, czas O(n), i przechowuje trzy wskaźniki, dodatkowa pamięć O(1). Najpierw skopiowanie kolejności do tablicy również zajmuje czas O(n), ale wymaga dodatkowej pamięci O(n). Wersja rekurencyjna używa O(n) pamięci na stos wywołań.

Czy potrafisz odwrócić listę łączoną rekurencyjnie?

Tak. Odwróć wszystko po głowie, a następnie spraw, by dawny następny węzeł głowy wskazywał z powrotem na głowę i ustaw odnośnik głowy na nic. Wygląda to dobrze, ale wykonuje jedno zagnieżdżone wywołanie na węzeł, więc długa lista może przepełnić stos wywołań. Python domyślnie zatrzymuje się po 1000 wywołaniach, a lista 5000 węzłów przekracza ten limit.

Dlaczego odwrócenie listy jednokierunkowej wymaga trzech wskaźników?

Aby odwrócić połączenie węzła, potrzebujesz samego węzła i poprzedzającego go węzła, czyli dwóch wskaźników. Trzeci przechowuje węzeł, który znajduje się za nim, ponieważ odwrócenie połączenia usuwa jedyne odwołanie do reszty listy. Bez niego nie można kontynuować przechodzenia.

Python

def reverseList(next):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

[-1, 0, 1, 2]