Middle of the Linked List
Otrzymujesz jednokierunkową listę połączoną zapisaną w dwóch tablicach o tej samej długości. Węzeł i przechowuje wartość values[i] i wskazuje na węzeł next[i], -1 oznacza koniec listy, a głową listy jest węzeł 0. Węzły nie są zapisane w kolejności występowania na liście, więc podążaj za wskazaniami.
Zwróć wartość środkowego węzła. Jeśli lista ma parzystą liczbę węzłów, ma dwa środkowe węzły; zwróć wartość drugiego z nich.
Funkcja
- valuesinteger-array
- wartość przechowywana przez każdy węzeł
- nextinteger-array
- indeks węzła, do którego prowadzi każdy węzeł, lub -1 dla ostatniego węzła
- Zwracainteger
- wartość środkowego węzła, drugiego środkowego w przypadku parzystej długości
Ograniczenia
1 ≤ n ≤ 5000, gdzienjest długościąvaluesinext.-104 ≤ values[i] ≤ 104- Każde
next[i]ma wartość-1lub jest indeksem węzła od0don-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
- values = [4, 9, 2, 7, 5]next = [3, -1, 1, 4, 2]
- Wyjście
- 5
- Wyjaśnienie
- Podążając za połączeniami z węzła
0, otrzymujemy węzły0, 3, 4, 2, 1, więc lista ma postać4, 7, 5, 2, 9. Trzeci z pięciu węzłów to węzeł4, którego wartość wynosi5. Środkowy element samej tablicy,values[2] = 2, to inny węzeł.
- Wejście
- values = [10, 20, 30, 40, 50, 60]next = [1, 2, 3, 4, 5, -1]
- Wyjście
- 40
- Wyjaśnienie
- Tutaj węzły są przechowywane w kolejności. Przy sześciu węzłach są dwa środkowe:
30i40, a wygrywa ten drugi.
- Wejście
- values = [8]next = [-1]
- Wyjście
- 8
- Wyjaśnienie
- Lista zawierająca jeden węzeł ma ten węzeł w środku.
+13 ukrytych testów przy wysłaniu
Pytanie dodatkowe
Czy potrafisz zwrócić w jednym przejściu węzeł znajdujący się w jednej trzeciej długości listy? Jak szybko poruszałby się każdy wskaźnik i gdzie byś się zatrzymał?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Nie znasz długości listy, dopóki nie dotrzesz do jej końca. Co by było, gdyby dwóch wędrowców zaczęło od początku listy, a jeden z nich poruszał się dwa razy szybciej niż drugi?
Gdy szybszy wędrowiec dotrze do końca, wolniejszy pokona połowę dystansu, więc znajdzie się na środkowym węźle. Pozostaje tylko ustalić, kiedy się zatrzymać, aby przy parzystej długości trafić na drugi środkowy węzeł.
Ustaw
slowifastna węźle0. Dopókifastnie jest równe-1inext[fast]nie jest równe-1, przesuwaj slow o jedno ogniwo, a fast o dwa ogniwa. Następnie zwróćvalues[slow].
Rozwiązanie
W tablicy środek znajduje się pod indeksem n / 2. Lista połączona nie ma indeksów: dowiadujesz się, jak jest długa, dopiero gdy dojdziesz do końca, a wtedy masz już za sobą środek. Możesz skopiować listę do tablicy albo najpierw ją policzyć, a potem przejść ją ponownie. Sprytne rozwiązanie polega na wysłaniu dwóch wskaźników przez listę z różnymi prędkościami, tak aby wolniejszy znalazł się w połowie, gdy szybszy dotrze do końca.
Skopiuj wartości do tablicy
Intuicja
W tym zadaniu wskaźnik to indeks węzła. Przejście do następnego węzła to node = next[node], a dotarcie do -1 oznacza, że wyszedłeś poza koniec. W pierwszym przykładzie przejście od węzła 0 przebiega tak: 0 → 3 → 4 → 2 → 1 → -1.
Problem z listą polega na tym, że nie możesz przeskoczyć do określonej pozycji. Możesz jednak zamienić ją w coś, co to umożliwia: przejdź raz przez listę i dodawaj każdą napotkaną wartość do nowej tablicy. Ta tablica przechowuje wartości w kolejności z listy: w pierwszym przykładzie jest to [4, 7, 5, 2, 9], a jej środek znajduje się pod indeksem length / 2, przy dzieleniu całkowitym.
Ten indeks sam wskazuje drugi środkowy element dla parzystej długości: sześć wartości daje indeks 3, czyli czwartą wartość — w drugim przykładzie jest to 40. Przejście zajmuje O(n) czasu, a kopiowanie wymaga dodatkowej pamięci O(n), czego unikają dwa kolejne podejścia.
Algorytm
- Zacznij od pustej tablicy i
node = 0. - Gdy
nodenie jest równe-1, dodajvalues[node]i przejdź donext[node]. - Zwróć element o indeksie
length / 2, zaokrąglonym w dół.
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]Policz, a następnie przejdź połowę drogi
Intuicja
Nie potrzebujesz całej kopii, tylko długości. Przejdź raz przez listę i policz węzły. Następnie zacznij ponownie od głowy i wykonaj length / 2 kroków, zaokrąglając w dół. Węzeł, na którym się zatrzymasz, jest środkowy.
Dlaczego tyle kroków: po k krokach znajdujesz się na węźle o pozycji k, licząc głowę jako pozycję 0. Środek listy o długości 5 znajduje się na pozycji 2, a drugi środkowy węzeł listy o długości 6 — na pozycji 3; w obu przypadkach jest to length / 2. W pierwszym przykładzie liczysz 5, wykonujesz dwa kroki 0 → 3 → 4 i odczytujesz values[4] = 5.
Pamięć wynosi teraz O(1). Ceną jest ponowne przejście przez połowę listy, łącznie 1.5n ruchów, co nadal daje O(n).
Algorytm
- Przejdź od węzła
0do-1i policz węzły. - Wróć do węzła
0. - Wykonaj
node = next[node]dokładniecount / 2razy, zaokrąglając w dół. - Zwróć
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]Szybkie i wolne wskaźniki
Intuicja
Umieść dwa wskaźniki na głowie. W każdej rundzie slow przesuwa się o jeden węzeł, a fast o dwa. Po k rundach slow znajduje się na pozycji k, a fast na pozycji 2k, więc slow zawsze pokonał połowę dystansu fast. Gdy fast dotrze do końca, slow jest w środku i nie trzeba było znać długości.
Warunek zatrzymania decyduje, który środkowy element uzyskasz. Kontynuuj, dopóki fast jest rzeczywistym węzłem i ma za sobą kolejny węzeł: fast != -1 oraz next[fast] != -1. Przy nieparzystej długości fast zatrzymuje się na ostatnim węźle. Przy parzystej długości fast wychodzi poza koniec na -1, co przesuwa slow o jeden węzeł dalej, na drugi środkowy element. W drugim przykładzie slow przechodzi przez 0, 1, 2, 3, a fast przez 0, 2, 4, -1, a values[3] to 40.
W pierwszym przykładzie slow odwiedza węzły 0, 3, 4, a fast odwiedza 0, 4, 1; węzeł 1 jest ostatni, więc pętla zatrzymuje się, gdy slow znajduje się na węźle 4, a odpowiedzią jest 5. Fast wykonuje około n ruchów, a slow n / 2, w jednym przebiegu i przy użyciu dwóch liczb całkowitych pamięci.
Algorytm
- Ustaw
slow = 0ifast = 0. - Gdy
fast != -1inext[fast] != -1, ustawslow = next[slow]ifast = next[next[fast]]. - Zwróć
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]
Pułapki i przypadki brzegowe
Pętla jest krótka, więc błędy dotyczą jej początku, końca i tego, co zwraca.
- Zwracanie
values[n / 2]. Węzły nie są przechowywane w kolejności na liście, więc środkowy element tablicy to zwykle jakiś inny węzeł. W pierwszym przykładzie zwraca2zamiast5. - Znajdowanie pierwszego środkowego elementu przy parzystej długości. Pętla, która działa, gdy zarówno
next[fast], jak inext[next[fast]]wskazują istniejące elementy, zatrzymuje się o jedną iterację za wcześnie i w drugim przykładzie zwraca30zamiast40. - Sprawdzanie
next[fast]przedfast != -1. Przy parzystej długości fast przyjmuje wartość-1, a odczytnext[-1]powoduje błąd w większości języków. W Pythonie po cichu odczytuje ostatni element, co jest jeszcze gorsze. - Przechodzenie
count / 2 - 1kroków lub zaokrąglanie w górę w podejściu z liczeniem. Licz głowę jako pozycję0i wykonaj dokładniecount / 2kroków, zaokrąglając w dół. - Zwracanie indeksu węzła zamiast jego wartości.
- Zapominanie o przesunięciu w Lua i R, gdzie tablice zaczynają się od 1. Pozostaw indeksy węzłów numerowane od 0 i odczytuj
next[node + 1]. Ruby i R rezerwują słowonext, więc w ich przykładach parametr nazwanonext_.
Najczęstsze pytania4
Dlaczego szybki i wolny wskaźnik znajdują środek listy połączonej?
Oba zaczynają od głowy listy, a w każdej rundzie szybki wskaźnik przesuwa się o dwa węzły, a wolny o jeden. Po k rundach szybki wskaźnik znajduje się na pozycji 2k, a wolny na pozycji k, czyli dokładnie w połowie drogi. Gdy więc szybki wskaźnik dotrze do końca listy, wolny będzie w jej środku.
Jaka jest złożoność czasowa i pamięciowa znajdowania środkowego elementu listy połączonej?
Wszystkie trzy podejścia działają w czasie O(n), ponieważ nie da się znaleźć środka bez przejścia przez około połowę listy lub więcej. Kopiowanie wartości wymaga dodatkowej pamięci O(n). Najpierw liczenie oraz szybkie i wolne wskaźniki wymagają po O(1), a wskaźniki potrzebują tylko jednego przejścia.
Jak zwrócić pierwszy środkowy węzeł zamiast drugiego?
Zmień warunek zatrzymania, aby szybki wskaźnik zatrzymywał się o jedno przejście wcześniej: wykonuj pętlę, gdy next[fast] != -1 i next[next[fast]] != -1. Dla sześciu węzłów wolny wskaźnik zatrzyma się wtedy na pozycji 2 zamiast 3. W podejściu z liczeniem przejdź (count - 1) / 2 kroków zamiast count / 2.
Gdzie jeszcze stosuje się technikę szybkiego i wolnego wskaźnika?
Te same dwie prędkości pozwalają wykryć cykl w liście wiązanej: w pętli szybki wskaźnik dogania wolny i spotykają się. Pozwalają też znaleźć początek cyklu oraz podzielić listę na połowy na potrzeby sortowania przez scalanie lub sprawdzenia, czy lista jest taka sama czytana w obu kierunkach.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def middleNode(values, next):
# Wpisz kod tutajPrzypadek 1
Przypadek 2
Przypadek 3
Wejście
values = [4, 9, 2, 7, 5] next = [3, -1, 1, 4, 2]
Oczekiwane
5