LinkedList Warum müssen wir hier den Dummy erstellen?

Question

Ich bin die Algorithmen auf die Datenstrukturen im Zusammenhang mit der Lösung, und ich bin nicht sicher, der folgende Code, den ich auf die Frage gestoßen:

public ListNode swapPairs(ListNode head) { 
    ListNode dummy = new ListNode(0); 
    dummy.next = head; 

    head = dummy; 
    while (head.next != null && head.next.next != null) { 
     ListNode n1 = head.next, n2 = head.next.next; 

     head.next = n2; 
     n1.next = n2.next; 
     n2.next = n1;     
     head = n1; 
    } 
    return dummy.next; 
} 

Warum müssen wir hier den Dummy schaffen?

Es wäre eine große Hilfe, wenn Sie mir dabei helfen könnten. Ich habe ähnliche Schritte beobachtet, wenn Sie eine Operation in der verknüpften Liste ausführen müssen.

Answer 1

Das Hinzufügen eines Dummy-Knotens ist überhaupt nicht notwendig. In der Tat ändern Sie den Kopf der verknüpften Liste, indem Sie Dummy-Knoten als Kopf hinzufügen. Ihr Code sollte ohne Dummy-Knoten funktionieren.

public void swapPairs(ListNode head) { 

    if(head!=null) { 
     while (head.next != null && head.next.next != null) { 
     ListNode n1 = head.next, n2 = head.next.next; 

     head.next = n2; 
     n1.next = n2.next; 
     n2.next = n1; 

     head = n1; 
     } 
    } 
} 

Answer 2

Wenn Sie zwei Knoten in einer verknüpften Liste zu wechseln, müssen Sie die next Zeiger in diesem Knoten und der vorhergehende Knoten ändern.

Zum Beispiel haben Sie eine Liste A->B->C, und Sie wollen B und C tauschen, müssen Sie die next Zeiger in alle dieser Knoten ändern.

Wenn Sie die ersten zwei Knoten, aber tauschen wollen, dann müssen Sie die next Zeiger in diesen beiden Knoten der Liste und der Zeiger auf den Kopf ändern.

Also, was Sie tun müssen, hängt davon ab, ob Sie am Anfang der Liste tauschen oder nicht ... Aber der Autor Ihrer Funktion ist faul, und er wollte nicht zwei schreiben müssen verschiedene Arten von Swap-Code.

Mr. Lazy Programmierer stecken daher in einem Dummy-Knoten vor all den Sachen, die er tauschen muss. Auf diese Weise muss er am Anfang nichts austauschen und er kann den gleichen Code für alle Swaps verwenden. Er entfernt diesen Knoten am Ende, so dass kein Schaden entsteht.

Das Erstellen eines Dummy-Knotens ist in Java nicht so teuer, aber ich hätte es nicht so gemacht.

Ich würde die zwei Möglichkeiten, wie dieses schreiben:

public ListNode swapPairs(ListNode head) { 

    if (head != null || head.next != null) { 

     //swap first 2 nodes 
     ListNode n1 = head; 
     ListNode n2 = n1.next; 

     head = n2; 
     n1.next = n2.next; 
     n2.next = n1;     
     ListNode pred = n1; 

     //swap remainder 
     while (pred.next != null && pred.next.next != null) { 
      n1 = pred.next; 
      n2 = n1.next; 

      pred.next = n2; 
      n1.next = n2.next; 
      n2.next = n1;     
      pred = n1; 
     } 
    } 
    return head; 
}