Intersection of Two Linked Lists

Q: Jaka jest złożoność czasowa znajdowania części wspólnej dwóch list jednokierunkowych?

Metody dwóch wskaźników i długości działają w czasie O(m + k) i wymagają O(1) dodatkowej pamięci. Zapamiętanie jednej listy w zbiorze lub tablicy znaczników również ma złożoność liniową, ale wymaga pamięci na tę listę. Porównanie każdej pary węzłów zajmuje O(m·k) .

ŁatweLista wiązana Dwa wskaźniki

+10

Dwie jednokierunkowe listy połączone są przechowywane w jednej puli węzłów. Węzeł i prowadzi do węzła next[i], a -1 oznacza koniec listy. Lista A zaczyna się od węzła headA, a lista B od węzła headB. Węzły nie są przechowywane w określonej kolejności, więc podążaj za połączeniami.

Listy mogą się łączyć: od pewnego węzła biegną dalej przez te same węzły aż do końca. Zwróć indeks pierwszego węzła występującego na obu listach albo -1, jeśli nie mają wspólnych węzłów.

Funkcja

getIntersectionNode(next: integer-array, headA: integer, headB: integer) → integer

nextinteger-array: indeks węzła, z którym łączy się dany węzeł, lub -1 dla ostatniego węzła listy
headAinteger: pierwszy węzeł listy A
headBinteger: pierwszy węzeł listy B
Zwracainteger: pierwszy węzeł wspólny dla obu list lub -1

Ograniczenia

2 ≤ n ≤ 10⁴, gdzie n jest długością next.
Każde next[i] ma wartość -1 lub jest indeksem węzła od 0 do n-1.
0 ≤ headA, headB ≤ n-1 i headA ≠ headB.
Obie listy kończą się na -1 bez odwiedzania węzła dwa razy. Nie ma cyklu.
Każdy węzeł znajduje się na liście A, na liście B albo na obu listach.

Przykłady

Wejście: next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
Wyjście: 1
Wyjaśnienie: A odwiedza 3, 5, 1, 4, 0, a B odwiedza 2, 1, 4, 0. Od węzła 1 dalej mają wspólny każdy węzeł, a żaden wcześniejszy węzeł A nie znajduje się na ścieżce B, więc odpowiedzią jest 1.

Wejście: next = [2, 3, 4, -1, -1]headA = 0headB = 1
Wyjście: -1
Wyjaśnienie: Lista A to 0, 2, 4, a lista B to 1, 3. Obie kończą się na -1, nie dotykając wspólnego węzła, więc odpowiedź to -1.

Wejście: next = [3, 2, 0, -1]headA = 1headB = 0
Wyjście: 0
Wyjaśnienie: Lista A to 1, 2, 0, 3, a lista B to 0, 3. Lista B jest ogonem listy A, więc pierwszym wspólnym węzłem jest samo headB, węzeł 0.

Pytanie dodatkowe

Czy potrafisz znaleźć węzeł w czasie O(m + k), używając dodatkowej pamięci O(1)?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Węzeł ma jedno next, więc dwie listy, które się spotkają, już się nie rozdzielą. Tworzą kształt Y: dwa osobne początki połączone ze wspólnym ogonem, a odpowiedzią jest punkt połączenia. Początki mogą różnić się długością, więc jednoczesne przechodzenie obu list sprawi, że miniesz punkt połączenia. Poniżej m i k to długości list A i B.

Sprawdź każdy węzeł A względem wszystkich węzłów B

Poprawne, ale nie kończy się na największych testach

Intuicja

Wskaźnik to indeks węzła, a przejście dalej to node = next[node]. Dla każdego węzła a z A, w kolejności, przejdź przez wszystkie węzły B i porównaj każdy węzeł z a. Pierwszy pasujący a jest odpowiedzią, ponieważ każdy wcześniejszy węzeł A już nie pasował. Dla każdego węzła A ponownie przeszukuje B: przy 5000 węzłów na każdej liście i bez wspólnych węzłów daje to 2.5 × 10^7 porównań.

Algorytm

Ustaw a = headA.
Dopóki a nie jest równe -1, przechodź przez b od headB do -1.
Jeśli w dowolnym momencie b == a, zwróć a.
W przeciwnym razie przesuń a = next[a] i powtórz.
Jeśli lista A się skończy, zwróć -1.

def getIntersectionNode(next, headA, headB):
    a = headA
    while a != -1:
        # Is node a also on list B? Walk all of B to find out.
        b = headB
        while b != -1:
            if a == b:
                return a
            b = next[b]
        a = next[a]
    return -1

Oznacz węzły listy B

Intuicja

Odpowiedz „czy ten węzeł należy do B?” dla każdego węzła: przejdź po B i zaznacz każdy węzeł w tablicy wartości logicznych o rozmiarze n. Indeksy węzłów są małymi liczbami całkowitymi, więc tablica sprawdzi się jako zbiór haszujący. Następnie przejdź po A, zaczynając od jego głowy. Pierwszy zaznaczony węzeł należy do obu list i jest pierwszym takim węzłem, ponieważ przechodzisz po A w kolejności. W pierwszym przykładzie B zaznacza 2, 1, 4, 0, a przechodząc po A, mijasz 3 i 5, zanim zatrzymasz się na 1. Każda lista jest przechodzona raz, więc złożoność czasowa wynosi O(m + k), kosztem n znaczników.

Algorytm

Utwórz onB, tablicę n wartości logicznych ustawionych na false.
Przejdź przez listę B od headB i ustaw onB[node] = true dla każdego węzła.
Przejdź przez listę A od headA. Zwróć pierwszy węzeł, dla którego onB[node] ma wartość true.
Jeśli lista A się skończy, zwróć -1.

def getIntersectionNode(next, headA, headB):
    # Mark every node of list B.
    on_b = [False] * len(next)
    node = headB
    while node != -1:
        on_b[node] = True
        node = next[node]
    # The first marked node on list A is the meeting point.
    node = headA
    while node != -1:
        if on_b[node]:
            return node
        node = next[node]
    return -1

Dwa wskaźniki, które zamieniają się listami

Intuicja

Podziel każdą listę w miejscu połączenia: A zawiera x prywatnych węzłów, a następnie c wspólnych, natomiast B zawiera y prywatnych węzłów, a następnie te same c. Wskaźnik a przechodzi przez A, trafia na -1, a następnie zaczyna od nowa od headB i po x + c + 1 + y ruchach po raz drugi dociera do miejsca połączenia. Wskaźnik b przechodzi przez B, a następnie przez A i dociera tam po y + c + 1 + x ruchach. Suma ruchów jest taka sama. W pierwszym przykładzie x = 2, y = 1 i c = 3, a po siedmiu ruchach oba wskaźniki znajdują się na węźle 1.

Jeśli nie ma wspólnego końcowego fragmentu, oba wskaźniki znajdują się na -1 po m + 1 + k ruchach (po m, gdy m = k), a pętla zwraca -1. To wspólne miejsce zatrzymania wyjaśnia, dlaczego każdy wskaźnik trafia na -1, zanim się przełączy. Każdy wskaźnik wykonuje najwyżej m + k + 1 ruchów, przy użyciu pamięci na dwa indeksy.

Algorytm

Ustaw a = headA i b = headB.
Dopóki a != b: przesuń a do headB, jeśli ma wartość -1, w przeciwnym razie do next[a].
W tej samej rundzie przesuń b do headA, jeśli ma wartość -1, w przeciwnym razie do next[b].
Gdy pętla się zakończy, zwróć a. Jest to pierwszy wspólny węzeł albo -1.

def getIntersectionNode(next, headA, headB):
    a, b = headA, headB
    # Each pointer walks its own list, then the other one. Both cover
    # the same number of nodes, so they reach the meeting node together,
    # or reach -1 together when there is none.
    while a != b:
        a = headB if a == -1 else next[a]
        b = headA if b == -1 else next[b]
    return a

Pułapki i przypadki brzegowe

Przejście z ostatniego węzła bezpośrednio do drugiej głowy, z pominięciem zatrzymania na -1. Gdy listy nie mają żadnych wspólnych elementów, wskaźniki nigdy nie przyjmują tej samej wartości, a pętla działa bez końca.
Ponowne ustawienie wskaźnika na własnej głowie. Każdy wskaźnik okrąża wtedy własną listę i spotykają się tylko wtedy, gdy ich okrążenia się zgrają, co może wymagać nawet (m + 1)·(k + 1) ruchów.
Traktowanie kolejności w tablicy jako kolejności na liście. Węzeł 0 jest głową tylko wtedy, gdy wskazuje na to headA lub headB, a sąsiednie elementy tablicy nie są sąsiadami na liście.
W Lua i R pamiętaj, że tablice zaczynają się od 1. Zachowaj indeksy węzłów liczone od 0 i odczytuj next[node + 1].

Najczęstsze pytania3

Jak znaleźć miejsce przecięcia dwóch list jednokierunkowych bez użycia dodatkowej pamięci?

Uruchom dwa wskaźniki. Każdy przechodzi własną listę, a po dojściu do jej końca kontynuuje od początku drugiej listy. Oba pokonują tę samą łączną odległość, więc docierają do pierwszego wspólnego węzła w tym samym momencie albo razem do końca, jeśli takiego węzła nie ma.

Czy potrafisz znaleźć część wspólną, porównując długości list?

Tak. Policz węzły obu list, przesuń wskaźnik na dłuższej liście do przodu o różnicę, a następnie przesuwaj oba wskaźniki po jednym kroku, aż będą na równi. Zajmuje to również O(m + k) czasu i O(1) pamięci; metoda przełączania zapewnia takie samo wyrównanie bez dwóch przebiegów zliczających.

Jaka jest złożoność czasowa znajdowania części wspólnej dwóch list jednokierunkowych?

Metody dwóch wskaźników i długości działają w czasie O(m + k) i wymagają O(1) dodatkowej pamięci. Zapamiętanie jednej listy w zbiorze lub tablicy znaczników również ma złożoność liniową, ale wymaga pamięci na tę listę. Porównanie każdej pary węzłów zajmuje O(m·k).

def getIntersectionNode(next, headA, headB):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

next = [-1, 4, 1, 5, 0, 1]
headA = 3
headB = 2

Oczekiwany wynik

Intersection of Two Linked Lists

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Sprawdź każdy węzeł A względem wszystkich węzłów B

Oznacz węzły listy B

Dwa wskaźniki, które zamieniają się listami

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania