LinkedListなぜここにダミーを作成する必要がありますか？

Question

私は、データ構造に関連したアルゴリズムの解決に新しいですし、私は疑問に遭遇次のコードがわからないよ：

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; 
} 

私たちはここにダミーを作成しなければならないのはなぜ？

これについて私が助けてくれるなら、大きな助けになるでしょう。リンクされたリストに対して何らかの操作を実行する必要があるときも、同様の手順を実行しました。

Answer 1

ダミーノードを追加する必要はありません。実際、ダミーノードを先頭に追加してリンクリストの先頭を変更しています。あなたのコードはダミーノードなしで動作するはずです。

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

リンクされたリスト内の2つのノードを交換する場合は、それらのノードと前のノードにnextポインタを変更する必要があります。

たとえば、あなたがリストA->B->Cを持っている、とあなたはBとCを交換したい、あなたはそれらのノードの全てにnextポインタを変更する必要があります。

あなたは最初つのノードを交換したい場合は、しかし、あなたは、リストの先頭にこれら二つのノードとポインタでnextポインタを変更する必要があります。

あなたがしなければならないことは、リストの始めに入れ替えているかどうかによって決まります...しかし、あなたの関数の作成者は怠け者であり、2つ書く必要はありませんでした異なる種類のスワップコード。

氏Lazyプログラマは、したがって、彼が交換しなければならないすべてのものの前にダミーノードに詰まっていました。そうすれば、彼は最初に何かを交換する必要はなく、すべてのスワップに同じコードを使用することができます。彼は最後にこのノードを削除するので、害はありません。

ダミーノードを作成することは、Javaではそれほど高価ではありませんが、私はこのようにしませんでした。

私はこのような二つの方法出て記述します。この関数はどこから来たの

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; 
}