Während ich LeetCode arbeitete, stieß ich auf Problem 141. Da ich JavaScript als meine Hauptprogrammiersprache verwende, in der es keine Datenstruktur mit verknüpften Listen gibt, hatte ich Mühe, die Idee zu verstehen und eine Lösung zu finden. LeetCode verfügt über eine integrierte Implementierung der Linked List für JavaScript und Sie müssen nur die Lösung schreiben. Deshalb dachte ich, warum es nicht auch anderen, die möglicherweise vor dem gleichen Problem stehen, einfacher machen? Dieser Artikel kann Ihnen helfen, einige Konzepte zu verstehen, also lesen Sie ihn bis zum Ende. Beginnen wir damit, die offensichtliche Frage zu stellen ...

Was ist eine verknüpfte Liste?

Eine verknüpfte Liste ist eine lineare Datenstruktur ähnlich einem Array. Im Gegensatz zu Arrays werden Elemente jedoch nicht an einem bestimmten Speicherort oder Index gespeichert. Vielmehr ist jedes Element ein separates Objekt, das einen Zeiger oder einen Link zum nächsten Objekt in dieser Liste enthält.

Jedes Element (im Allgemeinen als Knoten bezeichnet) enthält zwei Elemente: die gespeicherten Daten und einen Link zum nächsten Knoten. Die Daten können jeder gültige Datentyp sein. Sie können dies im Diagramm unten sehen.

In JavaScript sieht es so aus:

const list = {
    head: {
        data: 6
        next: {
            data: 10                                             
            next: {
                data: 12
                next: {
                    data: 3
                    next: null	
                    }
                }
            }
        }
    }
};

class ListNode {
    constructor(data, next = null) {
        this.data = data
        this.next = next               
    }
}

class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}

function getLinkedList (arr){
  const head = arr.reverse().reduce((a,b) => {
  if (!a) {
    a = new ListNode(b);
  } else {
    a = new ListNode(b, a);
  }
  return a;
}, null);

return new LinkedList(head);
}

const list = getLinkedList([2,5,1,7])
console.log(list.head)
// ListNode { data: 2, next: ListNode { data: 5, next: ListNode { data: 1, next: [ListNode] } }}
console.log(list.head.next.data)
// 5

Was ist ein Linked-List-Zyklus?

Ein Zyklus tritt auf, wenn die verknüpfte Liste nicht mehr linear mit Anfang und Ende ist, sondern eine Schleife von Knoten durchläuft.

Wir können dies erreichen, indem wir den nächsten Endknoten auf einen beliebigen anderen Knoten in der Liste verweisen. Nehmen wir an, wir möchten, dass der Zyklus bei Position 2 beginnt. Das können wir erreichen, indem wir Folgendes tun:

let tail = head
// get the tail
while(tail.next) {
   tail = tail.next
}

// get the cycle node
let pos = 2;
let cycleNode = head
while(pos > 0 && cycleNode.next) {
    cycleNode = cycleNode.next
    pos--
}
// point the next of tail to cycle node
tail.next = cycleNode;

Der Hase und die Schildkröte

Das Problem, in einer verknüpften Liste nach einem Zyklus zu suchen, mag zunächst einschüchternd erscheinen, aber mit Floyds Tortoise-and-Hare-Algorithmus ist es leicht zu verstehen und zu lösen. Die Idee besteht darin, einen langsamen Zeiger, z. B. „Schildkröte“, und einen schnellen Zeiger, z. B. „Hase“, zu verwenden. Die Schildkröte beginnt an der 0-Position und der Hase beginnt an der 1-Position. Wenn sich die Schildkröte jeweils um einen Ort bewegt und der Hase jeweils um 2 Orte, treffen sie sich irgendwann an einer Stelle in einem Zyklus. Sie können jede Bewegung zur Überprüfung zeichnen.

Stellen wir uns einen Zyklus in einer verknüpften Liste mit Länge vor, bei dem der Schwanz auf den zweiten Knoten in der Liste zeigt.

Hier ist der Algorithmus, den wir in JavaScript implementieren müssen.

create a slow node pointer and a fast node pointer
while: two pointers exists and fast pointer has a next value
       move the slow pointer by one node and fast pointer by two nodes
       if: at any time, slow pointer equals fast pointer
          linked list contains a cycle.

function hasCycle (head) {
// create 2 pointers
let slow = head;
let fast = head;

while(fast && fast.next){ // while pointers exist and fast pointer has a next value
    fast = fast.next.next; // move fast pointer by two nodes
    slow = slow.next; // move slow pointer by one node
    if(fast === slow) return true; // linked list has a cycle
    }

return false;
}

Ihr erster Gedanke könnte sein: Lassen Sie uns einfach den Knoten zurückgeben, an dem sich Hase und Schildkröte treffen. Aber wie Sie in den obigen Abbildungen sehen können, beginnt der Zyklus am zweiten Knoten, während sich Hase und Schildkröte am dritten Knoten treffen. Es wird also nicht funktionieren.

Die Lösung erfordert einen dritten Zeiger. Nachdem wir den Knoten gefunden haben, an dem sich Hase und Schildkröte treffen, dh schneller Zeiger gleich langsamer Zeiger, verschieben wir den langsamen Zeiger und den dritten Zeiger weiter um einen Knoten, und sie treffen sich schließlich dort, wo der Zyklus beginnt. Der Algorithmus, den wir in JavaScript implementieren müssen, ist wie folgt.

create a slow node pointer and a fast node pointer
while: two pointers exists and fast pointer has a next value
       move the slow pointer by one node and fast pointer by two nodes
       if: at any time, slow pointer equals fast pointer
           stop
if: fast pointer has no next and slow pointer doesnot equals fast pointer
    linked list doesn't contain a cycle
else: 
     while: slow pointer doesn't equal third pointer
            move both slow pointer and third pointer by one node
slow pointer/third pointer is the node where linked list cycle starts.

function cycleNode (head) {
   if(!head || !head.next) return null // head has no next value
    // create 3 pointers
    let fast = head;
    let slow = head;
    let start = head; // third pointer
    
    while(fast && fast.next){ // while pointers exist and fast pointer has a next value
      fast = fast.next.next; // move fast pointer by two nodes
      slow = slow.next; // move slow pointer by one node
      if(fast === slow) break; // stop if slow pointer equals fast pointer
    }
    
    if(slow !== fast) return null // linked list doesn't contain a cycle
    
    while(start !== slow){ // while slow pointer doesn't equal third pointer
      start = start.next; // move third pointer by one node
      slow = slow.next; // move slow pointer by one node
    }
    return start; // where cycle starts
}

Frieden.