Algorithmus zum Überprüfen einer verknüpften Liste für Schleifen

Question

Ich möchte einen Algorithmus finden, die checks a linked-list with n elements for consistency. Die verkettete Liste verwendet einen dummy head (auch bekannt als Sentinel-Knoten). Der Algorithmus muss run in O(n) time und darf use O(1) extra space abgesehen von dem Platz, der benötigt wird, um durch die Liste zu durchlaufen. Die size der Liste is unknown. Außerdem ist es forbidden to modify the list.

Eine Liste gilt als inkonsistent, wenn ein Listenelement auf ein vorheriges Listenelement zeigt. Zuerst dachte ich darüber nach, das erste Element zu speichern und dann die Liste zu durchlaufen, während ich das aktuelle Element mit dem ersten vergleiche.

Answer 1

Hier ist meine Lösung für die zweite Frage.

IsConsistent(LinkedList<Item> list) :N 
    slow = List.Sentinel.next :Element 
    fast = slow.next :Element 
    isConsistent = true :boolean 
    while(fast != list.Sentinel && fast.next != list.Sentinel && isConsistent) do 
     if(slow == fast) 
      isConsistent = false 
     else 
      slow:= slow.next 
      fast:= fast.next.next 
    od 
    if(isConsistent) 
     return 0 
    else 
     position = 0 : N 
     slow:= list.Sentinel 
     while(slow != fast) do 
      slow:= slow.next 
      fast:= fast.next 
      position:= position + 1 
     od 
     return position 

Answer 2

Grundsätzlich bedeutet das Zeigen eines vorherigen Elements, dass eine Schleife in der Liste enthalten ist. In diesem Fall scheint eine Schleifenprüfung angebracht zu sein.

Answer 3

Sie benötigen etwas Arbeitsspeicher dafür, wenn Sie für jedes Element in der verknüpften Liste keine Visited-Eigenschaft haben. Wenn Sie eine Visited-Eigenschaft haben, müssen Sie sie zuerst löschen, bevor Sie den Algorithmus ausführen. Dies wird wahrscheinlich nicht Ihren Big-O-Anforderungen entsprechen.

Es ist nicht klar, was Sie mit "Punkte bei vorherigen Listenelement" meinen. Ist gleich durch Referenz (Objekt) oder gleichen Wert/Menge von Eigenschaftswerten (struct)? Ich nehme Bezug auf. Der folgende Code kann leicht geändert werden, um auch Strukturen zu behandeln.

static void Main(string[] args) 
{ 
    var list = BuildALinkedListFromSomeData(); 
    var isConsitent = IsConsistent(list); 
} 

static bool IsConsistent(LinkedList<Item> list) 
{ 
    var visited = new List<LinkedListNode<Item>>() 
    var runner = list.First; 
    while(runner != null) 
    { 
     if (visited.Contains(runner)) 
      return false; 
     visited.Add(runner); 
     runner = runner.Next; 
    } 
    return true; 
} 

AO (n) Lösung, die einen vorhandenen numerischen VisitCounter verwendet, die bereits Speicherplatz verwendet (keine zusätzliche Speicherung erforderlich):

static bool IsConsistent(LinkedList<Item> list) 
{ 
    var runner = list.First; 
    if (runner == null) 
     return false; // Assume consistent if empty 

    var consistent = true; 
    var runId = runner.Value.VisitCount; 
    while (runner != null) 
    { 
     // Does the traversed item match the current run id? 
     if(runner.Value.VisitCount > runId) 
     { 
      // No, Flag list as inconsistent. It must have been visited previously during this run 
      consistent = false; 
      // Reset the visit count (so that list is ok for next run) 
      runner.Value.VisitCount = runId; 
     } 
     // Increase visit count 
     runner.Value.VisitCount++; 
     // Visit next item in list 
     runner = runner.Next; 
    } 
    return consistent; 
} 

Dies macht Änderungen an den Inhalt eines Elements in der Liste, aber nicht die Liste selbst. Wenn Sie den Inhalt eines Elements in der Liste nicht ändern dürfen, ist dies natürlich auch keine Lösung. Nun, ich denke, das ist keine mögliche Lösung. Wenn die Liste inkonsistent ist, ist sie kreisförmig und der letzte Algorithmus wird nie enden :)

Sie müssen dann die Liste rückwärts von jedem besuchten Element in Ihrer Liste durchlaufen und dies wird Ihre O (n + 1) Anforderung brechen.

Fazit: Nicht so Mission Impossible, wenn Count verfügbar ist. Siehe GrahamS 'Antwort

Answer 4

Enthält die Liste eine Size-Eigenschaft, die Ihnen sagt, wie viele Elemente es enthält (n), ohne es zu durchlaufen?

Wenn dies der Fall ist, dann ist eine einfache Lösung, die alle Ihre großen O-Anforderungen erfüllt, der Versuch, die Liste zu durchlaufen und dabei die Elemente zu zählen. Wenn die Anzahl die erwartete Anzahl von Elementen in der Liste übersteigt, hat sie eine Schleife.

Pseudo-Code würde wie folgt aussehen:

bool isConsistent (List list) 
{ 
    bool consistent = true; 
    Node node = list.Sentinel.Next; 
    int count = 0; 

    while (node != list.Sentinel && consistent) 
    { 
     count++; 

     if (count > list.Size) 
      consistent = false; 

     node = node.Next; 
    } 

    return consistent; 
} 

Die in O (n) abgeschlossen ist und verwendet O (1) Lagerung.

Answer 5

Zuerst dachte ich nicht darüber nach, listen.Sentinel zu verwenden. Jetzt habe ich eine neue Idee.

IsConsistent(LinkedList<Item> list) :boolean 
    slow = List.Sentinel.next :Element 
    fast = slow.next :Element 
    while(slow != list.Sentinel && fast != list.Sentinel) do 
     if(slow == fast) return false 
     else 
       slow:= slow.next 
       fast:= fast.next.next 
    od 
    return true 

Answer 6

Floyd's "Tortoise and Hare" algorithm tut, was man braucht und benötigt nur eine kleine Änderung mit dem Dummy-Kopf/Schwanz (Sentinel) Knoten zu arbeiten.

Hier ist, wie ich die Pseudo-Code schreiben würde:

bool IsConsistent (List list) 
{ 
    Node tortoise = list.Sentinel.Next; 
    Node hare = tortoise.Next; 

    while (tortoise != list.Sentinel && hare != list.Sentinel) 
    { 
     if (tortoise == hare) 
      return false; 

     tortoise = tortoise.Next; 
     hare = hare.Next.Next; 
    } 

    return true; 
}