Jak znaleźć środkowy element połączonej listy w jednym przebiegu?

Jedno z najpopularniejszych pytań dotyczących struktur danych i algorytmu, najczęściej zadawane podczas wywiadu telefonicznego.

Oszukując i wykonując dwa podania jednocześnie. Ale nie wiem, czy rekruterom się spodoba.

Można to zrobić na pojedynczej połączonej liście z fajną sztuczką. Po liście poruszają się dwa wskaźniki, jeden z podwójną prędkością. Kiedy szybki osiąga koniec, drugi jest w połowie drogi.

Jeśli nie jest to lista podwójnie połączona, możesz po prostu policzyć i użyć listy, ale w najgorszym przypadku wymaga to podwojenia pamięci i po prostu nie zadziała, jeśli lista jest zbyt duża, aby zapisać ją w pamięci.

Prostym, prawie głupim rozwiązaniem, jest tylko zwiększanie węzła środkowego co dwa węzły

function middle(start) {
    var middle = start
    var nextnode = start
    var do_increment = false;
    while (nextnode.next != null) {
        if (do_increment) {
             middle = middle.next;
        }
        do_increment = !do_increment;
        nextnode = nextnode.next;
    }
    return middle;
}

Opracowanie odpowiedzi Hendrika

Jeśli jest to lista podwójnie połączona, iteruj z obu końców

function middle(start, end) {
  do_advance_start = false;
  while(start !== end && start && end) {
     if (do_advance_start) {
        start = start.next
     }
     else {
        end = end.prev
     }
     do_advance_start = !do_advance_start
  }
  return (start === end) ? start : null;
}

Dany [1, 2, 3] => 2

1, 3
1, 2
2, 2

Dany [1, 2] => 1

1, 2
1, 1

Dany [1] => 1

Dany [] => null

Utwórz strukturę ze wskaźnikiem, który może wskazywać na węzły połączonej listy, oraz ze zmienną całkowitą, która przechowuje liczbę węzłów na liście.

struct LL{
    struct node *ptr;
    int         count;
}start;

$start.ptr$$start.count = 1$
$start.count$

$start.count$

Utwórz tablicę dynamiczną, w której każdy element tablicy jest wskaźnikiem do każdego węzła na liście w kolejności przejścia, zaczynając od początku. Utwórz liczbę całkowitą, zainicjowaną na 1, która będzie śledzić liczbę odwiedzonych węzłów (która zwiększa się za każdym razem, gdy przejdziesz do nowego węzła). Kiedy dojdziesz do końca, wiesz, jak duża jest lista, i masz uporządkowaną tablicę wskaźników do każdego węzła. Na koniec podziel rozmiar listy przez 2 (i odejmij 1 dla indeksowania opartego na 0) i pobierz wskaźnik umieszczony w tym indeksie tablicy; jeśli wielkość listy jest nieparzysta, możesz wybrać, który element ma zostać zwrócony (nadal zwracam pierwszy).

Oto trochę kodu Java, który ma sens (nawet jeśli pomysł na dynamiczną tablicę będzie nieco nieporadny). Zapewniłbym C / C ++, ale jestem bardzo zardzewiały w tym obszarze.

public Node getMiddleNode(List<Node> nodes){

    int size = 1;
    //add code to dynamically increase size if at capacity after adding
    Node[] pointers = new Node[10];

    for (int i = 0; i < nodes.size(); i++){
        //remember to dynamically allocate more space if needed
        pointers[i] = nodes.get(i);
        size++;
    }

    return pointers[(size - 1)/2];

}

Czy rekurencja jest uważana za więcej niż jeden przebieg?

Przejrzyj listę do końca, przekazując liczbę całkowitą przez odniesienie. Wykonaj lokalną kopię tej wartości na każdym poziomie do późniejszego wykorzystania i zwiększ liczbę odwołań przechodząc do następnego połączenia.

W ostatnim węźle podziel liczbę przez dwa i skróć / floor () wynik (jeśli chcesz, aby pierwszy węzeł był „środkowy”, gdy są tylko dwa elementy) lub zaokrąglij w górę (jeśli chcesz, aby drugi węzeł był środek"). Stosuj odpowiednio indeks zerowy lub indeks jeden.

Odwijając, dopasuj liczbę odwołań do lokalnej kopii (która jest numerem węzła). Jeśli jest równy, zwróć ten węzeł; w przeciwnym razie zwróci węzeł zwrócony z wywołania rekurencyjnego.
.

Są na to inne sposoby; niektóre z nich mogą być mniej kłopotliwe (myślałem, że widziałem, jak ktoś powiedział, wczytaj go do tablicy i użyj długości tablicy do określenia środka - kudos). Ale szczerze mówiąc, nie ma dobrych odpowiedzi, ponieważ jest to głupie pytanie podczas wywiadu. Numer jeden, który nadal korzysta z powiązanych list ( opinia wspierająca ); Po drugie, znalezienie środkowego węzła jest arbitralnym, akademickim ćwiczeniem bez wartości w rzeczywistych scenariuszach; Po trzecie, gdybym naprawdę potrzebował znać środkowy węzeł, moja połączona lista ujawniłaby liczbę węzłów. Łatwiej jest utrzymać tę właściwość niż tracić czas na przeglądanie całej listy za każdym razem, gdy chcę środkowy węzeł. I wreszcie, po czwarte, każdy ankieter polubi lub odrzuci różne odpowiedzi - co jeden z nich uważa za sprytny, inny nazywa śmieszne.

Prawie zawsze odpowiadam na pytania z wywiadu, zadając więcej pytań. Jeśli otrzymam takie pytanie (nigdy nie miałem), zapytałbym (1), co przechowujesz na tej połączonej liście i czy istnieje bardziej odpowiednia struktura, aby skutecznie uzyskać dostęp do środkowego węzła, jeśli naprawdę jest to konieczne ; (2) Jakie są moje ograniczenia? Mogę przyspieszyć, jeśli pamięć nie stanowi problemu (np. Odpowiedź tablicy), ale jeśli ankieter uważa, że ​​powiększanie pamięci jest marnotrawstwem, odejdę. (3) W jakim języku będę się rozwijał? Niemal każdy współczesny język, który znam, ma wbudowane klasy do obsługi powiązanych list, które sprawiają, że przeglądanie listy jest niepotrzebne - po co wymyślać coś, co zostało zoptymalizowane pod kątem wydajności przez twórców tego języka?

Za pomocą 2 wskaźników. Przyrost jeden przy każdej iteracji i drugi przy każdej drugiej iteracji. Gdy pierwszy wskaźnik wskazuje koniec połączonej listy, poszedł drugi wskaźnik wskazuje środkowy tryb połączonej listy.