Reorder List

Q: Dlaczego odwracać drugą połowę listy?

Odpowiedź odczytuje drugą połowę od ostatniego węzła do pierwszego, a lista jednokierunkowa pozwala poruszać się tylko do przodu. Jednokrotne odwrócenie drugiej połowy w czasie O(n) pozwala scalić obie połowy, przechodząc przez nie do przodu.

Q: Caka jest złożoność czasowa funkcji Reorder List?

Metoda działająca w miejscu wykonuje się w czasie O(n) i wymaga O(1) dodatkowej pamięci: znalezienie środka, odwrócenie i przeplatanie odwiedzają każdy węzeł stałą liczbę razy. Skopiowanie wartości do tablicy również zajmuje czas O(n) , ale wymaga O(n) pamięci, a przesuwanie ogona do przodu po jednym węźle zajmuje O(n²) .

Q: Gdzie znajduje się środek, gdy lista ma parzystą liczbę węzłów?

Zatrzymaj wolny wskaźnik na ostatnim węźle przedniej połowy. Przy sześciu węzłach połówki mają po trzy węzły, a przy pięciu — trzy i dwa. Dodatkowy węzeł wyznacza wtedy koniec odpowiedzi, czyli miejsce, w którym kolejność umieszcza środkową wartość.

ŚrednieLista wiązana Szybki i wolny wskaźnik Dwa wskaźniki

+10

Otrzymujesz jednokierunkową listę połączoną przechowywaną w dwóch tablicach o tej samej długości. Węzeł i przechowuje wartość values[i] i wskazuje węzeł next[i], -1 oznacza koniec listy, a głową jest węzeł 0. Węzły nie są przechowywane w kolejności listy, więc podążaj za odsyłaczami.

Oznacz węzły w kolejności listy jako L0, L1, ..., Lk. Zmień kolejność listy tak, aby wyglądała następująco: L0, Lk, L1, Lk-1, L2, Lk-2, ...: najpierw pierwszy węzeł, potem ostatni, następnie drugi, potem przedostatni i tak dalej. Zwróć wartości w tej nowej kolejności.

Funkcja

reorderList(next: integer-array, values: 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
valuesinteger-array: wartość przechowywana w każdym węźle
Zwracainteger-array: wartości w kolejności przestawionej listy

Ograniczenia

1 ≤ n ≤ 4000, gdzie n jest długością next i values.
-1000 ≤ values[i] ≤ 1000
Każde next[i] ma wartość -1 lub jest indeksem węzła od 0 do n-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 = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
Wyjście: [1, 5, 2, 4, 3]
Wyjaśnienie: Podążając za łączami z węzła 0, lista zawiera 1, 2, 3, 4, 5. Pierwszy, ostatni, drugi i przedostatni element dają 1, 5, 2, 4, a środkowa wartość 3 pojawia się na końcu.

Wejście: next = [2, 3, 1, -1]values = [10, 30, 20, 40]
Wyjście: [10, 40, 20, 30]
Wyjaśnienie: Lista odwiedza węzły 0, 2, 1, 3 i odczytuje 10, 20, 30, 40. Pierwszy i ostatni dają 10, 40, a następnie para wewnętrzna daje 20, 30.

Wejście: next = [-1]values = [7]
Wyjście: [7]
Wyjaśnienie: Lista z jednym węzłem nie ma nic do przesunięcia, więc odpowiedzią jest [7].

Pytanie dodatkowe

Czy możesz zmienić kolejność samych linków, używając dodatkowo O(1) pamięci?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Nowa kolejność zmienia się naprzemiennie między początkiem a końcem, ale lista jednokierunkowa pozwala poruszać się tylko do przodu. Podziel zadanie na trzy standardowe operacje na liście: znajdź środek za pomocą wolnych i szybkich wskaźników, odwróć tylną połowę i przeplataj obie połowy, łącząc po jednym węźle naraz.

Przesuwaj ogon do przodu, po jednym węźle naraz

Intuicja

Wskaźnik to tutaj indeks węzła, a przejście dalej to node = next[node]. Po pierwszym węźle znajduje się ostatni, więc odłącz ostatni węzeł i wstaw go za bieżącym, a następnie powtórz operację dwa węzły dalej. Dla 1, 2, 3, 4, 5 otrzymujemy 1, 5, 2, 3, 4, a następnie 1, 5, 2, 4, 3. Zatrzymaj się, gdy za bieżącym węzłem pozostanie mniej niż dwa węzły.

Znalezienie węzła przed ostatnim wymaga przejścia do końca w każdej rundzie. Trasy skracają się o dwa węzły na rundę, co daje łącznie około n²/4 kroków: cztery miliony dla 4000 węzłów.

Algorytm

Ustaw cur = 0.
Dopóki za cur znajdują się co najmniej dwa węzły, przesuwaj before od cur, aż next[next[before]] == -1, tak aby tail = next[before] był ostatnim węzłem.
Odłącz go za pomocą next[before] = -1, a następnie wstaw: next[tail] = next[cur] i next[cur] = tail.
Przesuń cur do next[tail] i powtórz.
Przejdź od węzła 0 i zbierz wartości.

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

Skopiuj wartości i odczytuj je z obu końców

Intuicja

Tablica osiąga ostatni element w jednym kroku. Skopiuj wartości w kolejności z listy, [1, 2, 3, 4, 5] w pierwszym przykładzie, a następnie odczytuj je za pomocą lo od początku i hi od końca: weź lo, weź hi i przesuwaj oba wskaźniki do środka, dopóki lo < hi. Otrzymasz 1, 5, 2, 4; przy nieparzystej długości oba wskaźniki spotkają się na środkowym 3, które zostanie dodane na końcu.

Złożoność czasowa wynosi O(n), a dodatkowa pamięć O(n); połączenia nigdy się nie zmieniają.

Algorytm

Przejdź od węzła 0 i dodaj każdą wartość do inOrder.
Ustaw lo = 0, a hi ustaw na ostatni indeks.
Dopóki lo < hi, dodawaj inOrder[lo] i inOrder[hi], a następnie zwiększaj lo i zmniejszaj hi.
Jeśli lo == hi, dodaj środkową wartość.

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

Znajdź środek, odwróć drugą połowę, przepleć

Intuicja

Dla 1, 2, 3, 4, 5, 6 odpowiedź to 1, 6, 2, 5, 3, 4: pierwsza połowa 1, 2, 3 w kolejności, na przemian z drugą połową 4, 5, 6 odczytaną od tyłu. Podziel więc listę w środku, odwróć drugą połowę i przeplataj elementy.

slow przesuwa się o jedno ogniwo, a fast o dwa, więc slow zatrzymuje się na ostatnim węźle pierwszej połowy: 3, zarówno przy pięciu, jak i sześciu węzłach. Podział za tym węzłem sprawia, że przy nieparzystej długości pierwsza połowa ma o jeden węzeł więcej, a ten węzeł znajduje się na końcu odpowiedzi. Przeplatanie pobiera po jednym węźle z każdej połowy, na przemian, aż wyczerpie się druga połowa.

Każdy węzeł jest odwiedzany stałą liczbę razy, przy użyciu kilku indeksów pamięci. R kopiuje wektor linków przy jego pierwszej zmianie, więc w R pamięć wynosi O(n).

Algorytm

Przesuń slow o jedno ogniwo, a fast o dwa ogniwa, dopóki next[fast] i next[next[fast]] nie są równe -1.
Ustaw second = next[slow], a następnie next[slow] = -1.
Odwróć listę zaczynającą się od second; jej nową głową jest prev.
Przeplataj: dopóki second nie jest równe -1, połącz first z second oraz second ze starą wartością next[first], a następnie przesuń oba.
Przejdź od węzła 0 i zbierz wartości.

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

Pułapki i przypadki brzegowe

Nieucinanie listy za jej środkiem. Bez next[slow] = -1 przednia połowa nadal wskazuje na tylną połowę, a po przeplataniu lista zapętla się.
Nadpisanie odwołania, zanim zostanie zapisane. Podczas odwracania i przeplatania najpierw odczytaj next[node] do zmiennej, bo w przeciwnym razie reszta listy zostanie utracona.
Przeplatanie aż do końca przedniej połowy. Przy nieparzystej długości ta pętla wykona się jeszcze raz, gdy second ma wartość -1, i odczyta next[-1].
Odczytywanie kolejności tablicy jako kolejności listy. W pierwszym przykładzie values to [1, 3, 5, 2, 4], ale lista odczytywana jest jako 1, 2, 3, 4, 5.
W Lua i R indeksowanie tablic zaczyna się od 1. Zachowaj indeksy węzłów liczone od 0 i odczytuj next[node + 1].

Najczęstsze pytania3

Dlaczego odwracać drugą połowę listy?

Odpowiedź odczytuje drugą połowę od ostatniego węzła do pierwszego, a lista jednokierunkowa pozwala poruszać się tylko do przodu. Jednokrotne odwrócenie drugiej połowy w czasie O(n) pozwala scalić obie połowy, przechodząc przez nie do przodu.

Caka jest złożoność czasowa funkcji Reorder List?

Metoda działająca w miejscu wykonuje się w czasie O(n) i wymaga O(1) dodatkowej pamięci: znalezienie środka, odwrócenie i przeplatanie odwiedzają każdy węzeł stałą liczbę razy. Skopiowanie wartości do tablicy również zajmuje czas O(n), ale wymaga O(n) pamięci, a przesuwanie ogona do przodu po jednym węźle zajmuje O(n²).

Gdzie znajduje się środek, gdy lista ma parzystą liczbę węzłów?

Zatrzymaj wolny wskaźnik na ostatnim węźle przedniej połowy. Przy sześciu węzłach połówki mają po trzy węzły, a przy pięciu — trzy i dwa. Dodatkowy węzeł wyznacza wtedy koniec odpowiedzi, czyli miejsce, w którym kolejność umieszcza środkową wartość.

def reorderList(next, values):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik

[1, 5, 2, 4, 3]

Reorder List

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Przesuwaj ogon do przodu, po jednym węźle naraz

Skopiuj wartości i odczytuj je z obu końców

Znajdź środek, odwróć drugą połowę, przepleć

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania