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

12

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

Gilles „SO- przestań być zły”
źródło
5
Jeśli odpowiedzi przedstawione w tym wątku są zgodne z oczekiwaniami ankietera, pytanie to nie sprawdza umiejętności technicznych, ale to, jak dobrze kandydat potrafi uniknąć prawnika.
G. Bach
2
To okropne pytanie podczas wywiadu, ponieważ opiera się krytycznie na określeniu „ pass ”, które jest niejasne, dwuznaczne, subiektywne. Prawie wszystkie dobre odpowiedzi na to pytanie obejmują nadużywanie definicji, aby można ją było skutecznie zignorować.
RBarryYoung 20.04.16
2
To pytanie budzi wiele dyskusji. Oznacza to, że jest to dobre pytanie do rozmowy kwalifikacyjnej pod jednym względem: zaczyna myśleć.
Hendrik Jan
3
Tak więc chcę odpowiedzieć „wczytaj wszystkie elementy do wektora, a następnie uzyskaj dostęp do elementu w pozycji size () / 2”
Cort Ammon,
1
@HendrikJan Właściwie myślę, że jest to całkowicie okropne pytanie podczas rozmowy kwalifikacyjnej. Po pierwsze, może prowadzić do kłótni o to, co dokładnie znaczy „w jednym przejściu”, a nie do produktywnej dyskusji. Po drugie, kandydat mógł zrozumieć „poprawną” odpowiedź, a następnie odrzucić ją, ponieważ uważał, że narusza ona kryterium „za jednym przejściem”. Po trzecie, ponieważ jest to dobrze znane pytanie, jest to lepszy test „Czy znasz popularne pytania podczas wywiadów?” niż „Czy dobrze pasujesz do tej pracy?” Każdy z nich powinien wystarczyć, by zadać to pytanie; wszystkie trzy jednocześnie są katastrofą.
David Richerby 21.04.16

Odpowiedzi:

24

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.

Hendrik Jan
źródło
1
Tak, nie jest jasne, czy to jest pojedyncze przejście. Pytanie w tej kwestii jest niejasne.
David Richerby,
2
Nawiasem mówiąc, jest to związane z łamigłówką, w której masz dwie świece, z których każda pali się godzinę, i jesteś proszony o zmierzenie 45 minut.
Hendrik Jan
2
Czy to naprawdę coś innego niż iteracja listy, zliczanie elementów, a następnie iteracja po raz drugi do połowy? Jedyne, co jest inne, to iteracja dodatkowej połowy. Jak wspomniała @RBarryYoung na innej podobnej odpowiedzi, tak naprawdę to nie jest pojedyncze przejście, to przejście półtora.
2
Jeśli lista jest długa, przesunięcie obu wskaźników „równolegle” spowoduje mniej błędów w pamięci podręcznej niż powtórzenie od początku po raz drugi.
zwolnić
2
Wykorzystuje to tę samą zasadę, co algorytm żółwia i zająca do wykrywania cyklu.
Joshua Taylor
7

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;
}
00500005
źródło
Drugą opcją jest poprawna odpowiedź (oczywiście IMHO).
Matthew Crumley,
1
W rzeczywistości wykonuje 1 1/2 przejścia przez połączoną listę.
RBarryYoung 20.04.16
6

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

00500005
źródło
Jak to jest wydajne? Ty również iterujesz n razy, a nie n / 2.
Karan Khanna
3

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;

stzart.ptrstzart.doount=1
stzart.doount

stzart.doount

Prateek
źródło
-2

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];

}
Andonaeus
źródło
-3

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?

James K.
źródło
6
Nie wiesz, kto głosował za czymś, więc twoja konkluzja, że ​​jedna osoba oceniła wszystko może, ale nie musi być prawdą, ale z pewnością nie ma podstaw w dostępnych faktach. Ale odrzucam twoją odpowiedź, ponieważ szukamy wyjaśnień, a nie stosów kodu.
David Richerby,
To może być założenie, ale kiedy patrzę chwilę i mniej niż 30 sekund później każdy post ma dokładnie -1, nie jest to nieracjonalne. Nawet jeśli było to 5 lub 6 różnych osób, żadna z nich nie pozostawiła komentarza dlaczego. Ale dziękuję przynajmniej za podanie przyczyny. Nie rozumiem, dlaczego kiepskie wyjaśnienie jest lepsze niż kod - tak, to jest na rozmowę telefoniczną, ale nie udzielam OPowi puszkowanej odpowiedzi na regurgitację, pokazuję mu sposób na zrobienie tego. IE Wydaje mi się, że głosowanie w dół na pocztę, ponieważ zawiera kod, jest nieuzasadnione, ale dziękuję, że przynajmniej powiedziałeś, dlaczego tak zrobiłeś.
James K
Słuszny punkt - nie przyszło mi do głowy, że znasz czas głosowania (myślę, że ładowanie strony w czasie, gdy się one odbywają, jest, jak sądzę, jedynym sposobem, w jaki zwykli użytkownicy, tacy jak my, mogliby się tego dowiedzieć). Mamy kilka postów na temat tego, dlaczego staramy się unikać faktycznego kodu tutaj: (1) (2) .
David Richerby 22.04.16
Dzięki za meta linki. Przeczytałem FAQ, ale nic tam nie widziałem - nie dlatego, że zauważyłem coś takiego, najprawdopodobniej czegoś, czego bym się nie spodziewał. Ale nie mogłem też znaleźć niczego, kiedy ponownie sprawdziłem po tym, jak się zwariowałem. Być może nadal to przeoczam, ale spojrzałem. Rozumowanie w słupkach meta ma sens; Dzięki za odpowiedzi.
James K
-5

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.

b dharuni
źródło
To po prostu powiela odpowiedź Hendricka . Nie odpowiadaj, chyba że masz coś nowego do powiedzenia.
David Richerby 21.04.16