Implementieren Sie einen Algorithmus, um einen Knoten in eine kreisförmige verkettete Liste einzufügen, ohne ihn zu durchlaufen

Question

Ich dachte an eine Lösung für dieses Problem.

Meine Eingabe:
1. Haben Sie einen Tail-Zeiger, der auf den letzten Knoten zeigt.
2. Sobald Sie den letzten Zeiger kennen, können Sie leicht einen neuen Knoten daneben hinzufügen.

Void Insert(Node N) 
{ 
    if (head == null) // linked list is empty 
    { 
     head = N; tail = N; tail.Next = head; 
    } 
    else 
    {   
     Node temp = tail.Next; // since this is circular tail will point to head 
     Tail.Next = N; 
     N.Next = temp; // correct 
     tail = N;  
    } 
} 

Kann any1 bessere Lösung ohne Verwendung von Tail-Pointer denken? Auch wie im Problem angegeben ohne zu verfahren? Dies ist eine Interviewfrage, die nur einige Eingaben benötigt, um die beste Lösung zu finden.

Answer 1

Ich vermute, dass Sie eine einfach verknüpfte zirkuläre Liste haben, und nur einen Zeiger auf ein Element (nennen Sie das den Kopfknoten). Jeder Knoten der Liste besteht somit aus einem Wert und einem Zeiger auf das nächste Element. Der Endknoten zeigt auf den Kopfknoten. Das Einfügen eines Knotens direkt nach dem Kopfknoten ist trivial. Ich denke, dass Sie einen Knoten direkt vor den Kopf Knoten einfügen möchten. Dazu muss der neue Knoten der letzte Knoten sein, auf den vom vorherigen letzten Knoten aus gezeigt wird und der auf den Kopfknoten zeigt. Jetzt möchten Sie vermeiden, die Liste zu durchsuchen, um den letzten Knoten zu finden. Dies bedeutet, dass Sie nicht auf diesen letzten Knoten zugreifen können und somit seinen Zeiger nicht ändern können. Die einzige andere Möglichkeit, diese Arbeit zu machen, ist die Stelle, die Punkte letzter Knoten zu ändern, um, das heißt:

1. legen Sie einen neuen Knoten nach den Kopfknoten
2. des aktuellen Kopfknoten des Wert auf diesen neuen Knoten kopieren
3. setzen den neuen Wert in den aktuellen Kopfknoten
4. den neuen Knoten

Answer 2

Nein, Sie brauchen den Schwanzzeiger. Andernfalls müssen Sie die Liste durchlaufen. Wie sonst würden Sie wissen, wo die Liste endet.

Sie könnten eine schlaue Indexierungsarithmetik entwickeln, aber es wäre immer noch ein Zeiger auf den Kopf/Schwanz.

Answer 3

Sie haben auch den Kopfknoten. Sie können es auch einfügen. Ich gehe davon aus, dass es keine Einschränkung gibt, wo der neue Knoten eingefügt werden soll (Frage spezifiziert das nicht explizit).

Das Einfügen auf den Kopf ist trivial.

bearbeiten es nach dem Kopfeinsatz

Answer 4

Wenn Ihr Maß für „besser“ ist nicht sowohl die Kopf- und Endzeiger zu halten, könnten Sie stattdessen nur den Schwanz Zeiger halten. Der Kopfzeiger ist implizit (gegeben durch tail.Next).

In der Praxis ist der Zugriff auf eine Liste häufig (z. B. wenn Sie die Ringliste als Warteschlange verwenden) und ein zusätzlicher Schritt für den Zugriff auf den Kopf kann zusätzlichen Aufwand verursachen. In einem Test für ein Projekt, das ich gemacht habe, hat die Eliminierung des Kopfzeigers auf diese Weise den Speicher etwas gesenkt (unsere Listen waren typischerweise kurz, aber wir hatten viele), aber die Zeit erhöhte sich, da wir oft auf den Kopf der Liste zugegriffen haben. YMMV.

Answer 5

ich habe vereinfacht Ihren Code ein wenig der neue Kopfknoten machen. Keine Notwendigkeit für die Variable temp, Sie haben es nicht einmal für etwas verwendet, nachdem Sie es eingestellt haben.

Void Insert(Node N) { 
    if (head == null) { // linked list is empty 
     head = tail = N; 
    } 
    else { // insert after tail 
     tail.Next = N; 
     tail = N;  
    } 
    tail.Next = head; 
} 

Answer 6

Anstatt den Kopf und den Schwanz zu speichern, speichern Sie einfach den Schwanz.

Void Insert(Node N) 
{ 
    if (tail == null) // linked list is empty 
    { 
     tail = N.Next = N; 
    } 
    else 
    { 
     N.Next = tail.Next; 
     tail = tail.Next = N; 
    } 
} 
Node Head() { return tail == null ? null : tail.next; }