Wywiad: usuń pętlę na liście linked - Java

Rozwiązanie 1 - dzięki uprzejmości Career Cup i książce "Cracking the Coding Interview" :

public static LinkedListNode findStartOfLoop(LinkedListNode head) {
    LinkedListNode n1 = head;
    LinkedListNode n2 = head; 

    // find meeting point using Tortoise and Hare algorithm
    // this is just Floyd's cycle detection algorithm
    while (n2.next != null) { 
        n1 = n1.next; 
        n2 = n2.next.next; 
        if (n1 == n2) { 
            break; 
        }
    }

    // Error check - there is no meeting point, and therefore no loop
    if (n2.next == null) {
        return null;
    }

    /* Move n1 to Head. Keep n2 at Meeting Point.  Each are k steps
    /* from the Loop Start. If they move at the same pace, they must
     * meet at Loop Start. */
    n1 = head; 
    while (n1 != n2) { 
        n1 = n1.next; 
        n2 = n2.next; 
    }
    // Now n2 points to the start of the loop.
    return n2;
}

Wyjaśnienie tego rozwiązania jest prosto z książki:

Jeśli przesuniemy Dwa wskaźniki, jeden z prędkość 1 i drugi z prędkością 2, oni skończy się spotkanie, jeśli połączone lista ma pętlę. Dlaczego? Pomyśl o dwóch samochody jadące po torze; szybszy samochód zawsze będzie mijał wolniejszy!

Najtrudniejszą częścią jest znalezienie początku z pętla. Wyobraź sobie, jako analogię, dwie osoby ścigające się po torze, jeden biegający dwa razy szybciej niż inne. Jeśli zaczną w tym samym miejsce, kiedy się spotkają? Oni następne spotkanie odbędzie się na początku następne okrążenie.

Załóżmy, że Fast Runner miał przewagę k metrów na okrążeniu. Kiedy będą następne spotkać? Spotkają się przed początek następnego okrążenia. (Dlaczego? Szybko Runner zrobiłby k + 2 (n-k) kroki, w tym jego fory, oraz Slow Runner zrobiłby n-k kroki oba będą krokami k przed początek pętli).

Teraz, wracając do problemu, kiedy Fast Runner (n2) i Slow Runner (n1) poruszają się po naszym okrągła lista powiązana, n2 będzie miała początek pętli, gdy n1 wchodzi. W szczególności będzie miał początek K, gdzie k jest liczbą węzłów przed pętlą. Ponieważ n2 ma początek węzłów k, n1 i n2 spotka węzły k przed rozpoczęciem na pętla.

Więc teraz wiemy, co następuje:

1. Head to węzły k z LoopStart (z definicji)
2. MeetingPoint dla n1 i n2 to węzły k z Loopstartu (jak pokazano powyżej)

Tak więc, jeśli przesuniemy n1 z powrotem do głowy i utrzymamy n2 na Meetingpoincie, i poruszymy ich oboje w tym samym tempie, spotkają się w LoopStart

Rozwiązanie 2 - dzięki uprzejmości mnie:)

public static LinkedListNode findHeadOfLoop(LinkedListNode head) {

    int indexer = 0;
    Map<LinkedListNode, Integer> map = new IdentityHashMap<LinkedListNode, Integer>();
    map.put(head, indexer);
    indexer++;

    // start walking along the list while putting each node in the HashMap
    // if we come to a node that is already in the list, 
    // then that node is the start of the cycle 
    LinkedListNode curr = head;
    while (curr != null) {

        if (map.containsKey(curr.next)) {
            curr = curr.next;
            break;
        }
        curr = curr.next;
        map.put(curr, indexer);
        indexer++;
    }
    return curr;
}

Ta odpowiedź nie ma na celu konkurowania o odpowiedź, ale raczej Wyjaśnienie nieco więcej na temat spotkania dwóch węzłów w algorytmie żółwia i zająca.

1. Oba węzły w końcu wejdą w pętlę. Ponieważ jeden porusza się szybciej (F) niż drugi (S), (F) W końcu okrąży (S).

2. Jeśli początek pętli znajduje się w nagłówku listy, (F) musi się spotkać (s) z powrotem w nagłówku listy. To tylko dlatego, że (F)'S prędkość jest 2X (S)'S; jeśli to było 3X to nie byłoby Bądź prawdziwy. Jest to prawdą ponieważ (F) ukończy jedno okrążenie kiedy (S) ukończy pół okrążenia, więc kiedy (S) ukończy swoje pierwsze okrążenie, (F) ukończy dwa okrążenia - i jest z powrotem na początku pętli z (s).

3. Jeśli początek pętli nie znajduje się w nagłówku listy, to do czasu (s) wejścia do pętli, (F) miał początek (k) węzłów w pętli. Ponieważ prędkość (S) jest tylko jednym węzłem na raz, spotka (F) Na (K) węzłach od początku pętli - jak w (k) więcej kroków przed osiągnięciem start, a nie (K) kroki po starcie. Nie byłoby to prawdą, gdyby prędkość (s) nie była jedna, a stosunek prędkości nie był 2:1 między (F) I (S).

   3.1. To tutaj robi się trochę trudne do wyjaśnienia. Możemy się zgodzić, że (F) będzie kontynuować docieranie (S) aż w końcu się spotkają (Patrz 1 powyżej), ale dlaczego na (k) węzłach od początku pętli? Rozważmy następujące równanie, gdzie M to liczba węzłów lub odległość pętli, a k to początek (F); równanie przedstawia odległość przejechany przez (F) podany czas t z lewej strony pod względem odległości przejechanej przez (S) z prawej:

   D_F (t) = 2 * d_S (t) + k

   Więc kiedy (S) wchodzi w pętlę i przebył 0 odległość w pętli, (F) przebył tylko (K) odległość. W czasie d_S = M - k, d_F = 2m - k. ponieważ musimy również użyć matematyki modularnej, biorąc pod uwagę, że M reprezentuje całkowitą odległość pojedynczego okrążenia w pętli, pozycja (F) I (S) W dowolnej całości m (bez reszty) wynosi 0. Więc w kategoriach Pozycja (lub różnica), pozostawia k (a raczej-k).

   I tak wreszcie, (S) I (F) spotkają się w pozycji (0 - k), lub (k) węzłów Od początku pętli.

4. Biorąc pod uwagę [3] powyżej, ponieważ (k) reprezentuje początek (F) i ponieważ (F) przebył 2X odległość (s) przejechaną, aby wejść do pętli od początku listy, (k) reprezentuje również odległość od początku listy, która następnie reprezentuje początek pętli.

It ' s a bit late tutaj, więc mam nadzieję, że udało mi się skutecznie wyartykułować. Daj mi znać inaczej, a postaram się zaktualizować odpowiedź.

Jeśli użycie mapy hashowej tożsamości (np. IdentityHashMap) jest dozwolone, jest to niezwykle łatwe do rozwiązania. Ale zużywa więcej miejsca.

Przemierzaj listę węzłów. Dla każdego napotkanego węzła dodaj go do mapy tożsamości. Jeśli węzeł już istniał na mapie tożsamości, to lista ma okrągłe łącze i węzeł, który był przed tym konfliktem jest znany (sprawdź przed przeniesieniem lub zachowaj "ostatni węzeł") -- wystarczy ustawić" następny " odpowiednio, aby złamać cykl.

Podążanie za tym prostym podejściem powinno być zabawnym ćwiczeniem: kod jest pozostawiony jako ćwiczenie dla czytelnika.

Szczęśliwe kodowanie.

 0--->1---->2---->3---->4---->5---->6
                  ▲                 |
                  |                 ▼
                 11<—-22<—-12<—-9<—-8  

Wstaw atrapa węzła za każdym węzłem listy linków i przed wstawieniem sprawdź, czy węzeł obok jest atrapa czy nie. Jeśli next to next jest atrybutem, Wstaw null W next tego węzła.

 0-->D->1-->D->2-->D->3->D-->4->D-->5->D-->6
                     ▲                      |
                  /                         ▼
                 11<—D<-22<—D<-12<—D<-9<—D<--8 


Node(11)->next->next == D
Node(11)->next =null

//Find a Loop in Linked List and remove link between node

    public void findLoopInList() {
            Node fastNode = head;
            Node slowNode = head;
            boolean isLoopExist = false;
            while (slowNode != null && fastNode != null && fastNode.next != null) {
                fastNode = fastNode.next.next;
                slowNode = slowNode.next;
                if (slowNode == fastNode) {
                    System.out.print("\n Loop Found");
                    isLoopExist = true;
                    break;
                }
            }
            if (isLoopExist) {
                slowNode = head;
                Node prevNode = null;
                while (slowNode != fastNode) {
                    prevNode = fastNode;
                    fastNode = fastNode.next;
                    slowNode = slowNode.next;
                }
                System.out.print("Loop Found Node : " + slowNode.mData);
                prevNode.next = null; //Remove the Loop
            }
        }

:)GlbMP