Remove Nth Node From End of List
Otrzymujesz jednokierunkową listę połączoną przechowywaną w dwóch tablicach tej samej długości. Węzeł i zawiera wartość values[i] 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.
Usuń n-ty węzeł, licząc od końca listy, gdzie ostatni węzeł jest 1. od końca. Zwróć wartości pozostałych węzłów w kolejności występowania na liście.
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
- ninteger
- który węzeł usunąć, licząc od końca, gdzie 1 oznacza ostatni węzeł
- Zwracainteger-array
- pozostałe wartości w kolejności na liście; pusta, gdy usunięty zostanie jedyny węzeł
Ograniczenia
1 ≤ L ≤ 5000, gdzieLjest długościąvaluesinext.-100 ≤ values[i] ≤ 1001 ≤ n ≤ L- Każdy element
next[i]jest równy-1lub indeksowi węzła od0doL-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 = [5, 9, 2, 7, 6]next = [2, 3, 4, -1, 1]n = 2
- Wyjście
- [5, 2, 6, 7]
- Wyjaśnienie
- Podążając za linkami od węzła
0, odwiedzamy węzły0, 2, 4, 1, 3, więc lista ma postać5, 2, 6, 9, 7. Drugim węzłem od końca jest węzeł1o wartości9, a bez niego lista ma postać5, 2, 6, 7. Wpis tablicyvalues[5-2] = 7odpowiada ostatniemu węzłowi, a nie temu, który należy usunąć.
- Wejście
- values = [10, 20, 30, 40]next = [1, 2, 3, -1]n = 4
- Wyjście
- [20, 30, 40]
- Wyjaśnienie
- Cztery węzły i
n = 4: węzeł czwarty od końca jest głową. Lista zaczyna się teraz od węzła1i zawiera20, 30, 40.
- Wejście
- values = [42]next = [-1]n = 1
- Wyjście
- []
- Wyjaśnienie
- Jedyny węzeł jest jednocześnie głową i ostatnim węzłem. Jego usunięcie pozostawia pustą listę, więc odpowiedzią jest
[].
+14 ukrytych testów przy wysłaniu
Pytanie dodatkowe
Czy potrafisz znaleźć i odłączyć węzeł w jednym przebiegu, bez wcześniejszego liczenia długości?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Lista porusza się tylko do przodu, a węzeł jest określony przez jego odległość od końca. Gdyby znać jej długość
L, na której pozycji od początku by się znajdował? A którego węzła łącze trzeba zmienić, aby go usunąć?Możesz zmierzyć odległość do końca bez znajomości długości. Ustaw jeden wskaźnik
nwęzłów przed drugim i przesuwaj je razem. Gdy pierwszy wskaźnik znajdzie się na ostatnim węźle, drugi będzie tuż przed węzłem do usunięcia.Przesuń
fastdo przodunrazy. Jeśli teraz ma wartość-1, głową jest węzeł do usunięcia, więc lista zaczyna się odnext[0]. W przeciwnym razie przesuwaj jednocześnieslowifast, dopókinext[fast] != -1, a następnie ustawnext[slow] = next[next[slow]]. Przejdź listę od głowy i zbierz wartości.
Rozwiązanie
Cel jest określony przez odległość od końca, ale po liście jednokierunkowej można poruszać się tylko do przodu, a o tym, gdzie jest koniec, dowiadujesz się dopiero wtedy, gdy do niego dotrzesz. Usunięcie węzła oznacza też ustawienie się na węźle przed nim, ponieważ to właśnie łącze tego węzła trzeba zmienić. Możesz skopiować listę do tablicy albo ją policzyć i przejść ponownie. Klasyczne rozwiązanie polega na utrzymywaniu dwóch wskaźników oddalonych od siebie o n łączy, tak aby gdy przedni wskaźnik dotrze do ostatniego węzła, tylny znajdował się tuż przed celem. Poniżej L oznacza liczbę węzłów.
Skopiuj wartości do tablicy
Intuicja
W tym zadaniu wskaźnik to indeks węzła. Przejście do przodu 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 → 2 → 4 → 1 → 3 → -1.
Liczenie od końca jest trudne tylko dlatego, że lista nie ma pozycji. Nadajmy jej więc pozycje: przejdź po niej raz i dodaj każdą wartość do tablicy. W pierwszym przykładzie ta tablica to [5, 2, 6, 9, 7]. W tablicy zawierającej L wartości ostatnia z nich znajduje się pod indeksem L-1, więc n-ta wartość od końca znajduje się pod indeksem L-n. W tym przypadku jest to 5-2 = 3, czyli 9. Usuń ją i zwróć [5, 2, 6, 7].
To rozwiązanie jest poprawne i działa w czasie O(L), ale kopiuje całą listę i nie modyfikuje żadnego łącza. Celem zadania jest modyfikowanie samej listy przy użyciu dodatkowej pamięci O(1) — właśnie tak działają dwa kolejne podejścia.
Algorytm
- Zacznij od pustej tablicy i
node = 0. - Dopóki
nodenie jest równe-1, dodawajvalues[node]i przechodź donext[node]. - Usuń element o indeksie
length - n. - Zwróć tablicę.
def removeNthFromEnd(values, next, n):
# Write the values out in list order.
order = []
node = 0
while node != -1:
order.append(values[node])
node = next[node]
# Counting from the end, the n-th value sits at index len(order) - n.
del order[len(order) - n]
return orderPolicz węzły, a następnie je odłącz
Intuicja
Aby usunąć węzeł z listy, zmień odnośnik węzła przed nim tak, aby go pomijał: next[prev] = next[next[prev]]. Usunięty węzeł nadal znajduje się w tablicach, ale żadne przejście od głowy listy już do niego nie dotrze.
Znajdź więc prev. Policz węzły podczas pierwszego przejścia. Przyjmując, że głowa ma pozycję 0, element docelowy znajduje się na pozycji L-n, a węzeł przed nim na pozycji L-n-1; od głowy docierasz do niego po L-n-1 krokach. W pierwszym przykładzie L = 5 i n = 2: dwa kroki 0 → 2 → 4 prowadzą do węzła 4, który wskazuje na węzeł 1, czyli 9. Ustawienie next[4] = next[1] = 3 sprawia, że lista ma postać 5, 2, 6, 7.
W jednym przypadku przed elementem docelowym nie ma żadnego węzła: n = L, gdy elementem docelowym jest głowa. Wtedy nie trzeba niczego przepinać. Lista zaczyna się od next[0] zamiast od 0, jak w drugim przykładzie. Następnie przejdź od głowy, aby zebrać odpowiedź. Dwa przejścia po liście wymagają około 2L kroków, a pamięć zużywana poza odpowiedzią to kilka liczb całkowitych.
Algorytm
- Przejdź od węzła
0do-1i policz węzły jakoL. - Jeśli
n == L, nową głową jestnext[0]. - W przeciwnym razie ustaw
prevna węźle0i przesuń goL-n-1razy, a następnie ustawnext[prev] = next[next[prev]]. - Przejdź od głowy i zbierz
values[node]w kolejności.
def removeNthFromEnd(values, next, n):
# First pass: count the nodes.
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
head = 0
if n == length:
# The node to remove is the head, so the list starts at its second node.
head = next[0]
else:
# Second pass: stop on the node just before position length - n.
prev = 0
for _ in range(length - n - 1):
prev = next[prev]
next[prev] = next[next[prev]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return resultDwa wskaźniki oddalone od siebie o n łączy
Intuicja
Możesz zmierzyć „n od końca” bez znajomości L. Przesuń fast o n węzłów do przodu, podczas gdy slow czeka na początku. Następnie przesuwaj oba wskaźniki o jeden węzeł naraz. Odległość między nimi pozostaje równa n, więc gdy fast znajdzie się na ostatnim węźle (next[fast] == -1, pozycja L-1), slow będzie na pozycji L-1-n: na węźle bezpośrednio przed docelowym. Jedno przypisanie next[slow] = next[next[slow]] usuwa docelowy węzeł z listy.
Prześledź pierwszy przykład. fast wykonuje dwa kroki: 0 → 2 → 4. Teraz przesuwają się oba wskaźniki: slow przechodzi do 2, a fast do 1, następnie slow przechodzi do 4, a fast do 3. Węzeł 3 jest ostatni, więc zatrzymujesz się. next[4] wskazuje węzeł 1, czyli 9, a ustawienie next[4] = next[1] = 3 usuwa go.
Przypadek głowy listy pojawia się sam. Ponieważ n ≤ L, fast dociera do -1 podczas początkowego przesunięcia tylko wtedy, gdy n = L, a właśnie wtedy głowa listy jest węzłem docelowym. W przypadku obiektów reprezentujących węzły można wstawić węzeł wartowniczy przed głową, aby wyeliminować ten przypadek; tutaj tę samą rolę pełni sprawdzenie fast == -1. Znalezienie i odłączenie węzła wymaga jednego przejścia. Wypisanie odpowiedzi wymaga jeszcze jednego przejścia, którego potrzebuje każde podejście.
Algorytm
- Ustaw
fast = 0i przesuń jenrazy, używającfast = next[fast]. - Jeśli
fast == -1, głowa jest celem: nową głową jestnext[0]. - W przeciwnym razie ustaw
slow = 0i przesuwaj obie zmienne, dopókinext[fast] != -1. - Ustaw
next[slow] = next[next[slow]]. - Przejdź od głowy i zbierz kolejno wartości
values[node].
def removeNthFromEnd(values, next, n):
# Send fast n links ahead of slow.
fast = 0
for _ in range(n):
fast = next[fast]
head = 0
if fast == -1:
# Fast fell off the end, so the list has exactly n nodes: remove the head.
head = next[0]
else:
# Move both, keeping the gap. When fast stands on the last node,
# slow stands just before the node to remove.
slow = 0
while next[fast] != -1:
slow = next[slow]
fast = next[fast]
next[slow] = next[next[slow]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return result
Pułapki i przypadki brzegowe
Większość błędnych odpowiedzi wynika z tego, gdzie zatrzymuje się wolny wskaźnik, oraz z przypadku, w którym usuwana jest głowa.
- Usuwanie elementu o indeksie
L-nw tablicy. Węzły nie są przechowywane w kolejności listy, więc pod tym indeksem zwykle znajduje się inny węzeł. W pierwszym przykładzievalues[3] = 7to ostatni węzeł, a nie9. - Zatrzymywanie się, gdy
fast == -1, zamiast gdynext[fast] == -1. To przesuwaslowo jeden krok za daleko, na sam cel, a na liście jednokierunkowej nie można odłączyć węzła, wskazując na niego samego. - Zapominanie o przypadku z głową. Gdy
n = L, po początkowym przesunięciufastma wartość-1, a odczytnext[fast]powoduje błąd w większości języków. Python odczytujenext[-1]bez zgłaszania błędu i zwraca nieprawidłową listę, co trudniej zauważyć. - Odłączanie za pomocą
next[slow] = next[slow] + 1lubslow + 2. Sąsiednie węzły na liście nie są sąsiednimi elementami tablic; jedynym sposobem dotarcia do węzła za celem jestnext[next[slow]]. - Zbieranie odpowiedzi, zaczynając od węzła
0, po usunięciu głowy. Rozpocznij końcowe przejście od nowej głowy. - Zapominanie o przesunięciu w Lua i R, gdzie indeksowanie tablic zaczyna się od 1. Pozostaw indeksy węzłów jako liczone od 0 i odczytuj
next[node + 1]. Ruby i R rezerwują słowonext, dlatego w kodach początkowych parametr nosi nazwęnext_.
Najczęstsze pytania4
Jak usunąć n-ty węzeł od końca listy jednokierunkowej w jednym przebiegu?
Użyj dwóch wskaźników z odstępem wynoszącym n. Przesuń pierwszy o n węzłów do przodu, a następnie przesuwaj oba razem, aż pierwszy znajdzie się na ostatnim węźle. Drugi będzie wtedy tuż przed węzłem do usunięcia, więc ustaw jego łącze tak, by wskazywało za ten węzeł. Jeśli podczas początkowego przesuwania pierwszy wskaźnik wyjdzie poza listę, węzłem do usunięcia jest głowa listy.
Dlaczego rozwiązania tego problemu używają węzła wartowniczego?
Usunięcie węzła oznacza zmianę łącza węzła, który go poprzedza, a głowa nie ma węzła przed sobą. Wstawienie węzła wartownika przed głową daje każdemu węzłowi, także głowie, poprzednik, dzięki czemu jedna linia odłączająca węzeł obsługuje wszystkie przypadki. Odpowiedź zaczyna się wtedy od następnego węzła wartownika. Sprawdzenie, czy wskaźnik prowadzący wyszedł poza listę po n krokach, obsługuje ten sam przypadek bez dodatkowego węzła.
Jaka jest złożoność czasowa i pamięciowa usuwania n-tego węzła od końca?
Dla listy zawierającej L węzłów zajmuje to O(L) czasu, ponieważ musisz dotrzeć do końca, aby wiedzieć, gdzie znajduje się cel. Zarówno wcześniejsze policzenie elementów, jak i metoda dwóch wskaźników wymagają O(1) dodatkowej pamięci. Skopiowanie wartości do tablicy wymaga O(L).
Czy rozwiązanie z dwoma wskaźnikami jest szybsze niż wcześniejsze policzenie długości?
Niewiele: oba mają złożoność O(L), a oba wskaźniki razem wykonują mniej więcej tyle samo ruchów co dwa przejścia. Prawdziwa korzyść polega na tym, że długość nie jest potrzebna z góry, więc metoda działa również wtedy, gdy lista jest dostarczana jako strumień, który można odczytać tylko raz. Właśnie o takie jednokrotne przejście zwykle proszą rekruterzy podczas rozmów kwalifikacyjnych.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def removeNthFromEnd(values, next, n):
# Wpisz kod tutajPrzypadek 1
Przypadek 2
Przypadek 3
Wejście
values = [5, 9, 2, 7, 6] next = [2, 3, 4, -1, 1] n = 2
Oczekiwane
[5, 2, 6, 7]