Java：LinkedList Reverse

Question

reverseの機能を実装しようとしています。LinkedListの実装です。

public class LinkedList<T> { 
    public Node head; 

    public LinkedList(){ 
     // Add HEAD 
     head = new Node(null); 
    } 

    public void add(T data){ 
     getLastNode().next = new Node(data); 
    } 

    public void insert(int index, T data){ 
     if(index == 0){ 
      throw new Error(); // TODO: What is the Error Type? 
     } 

     Node current = head; 

     for (int i = 0; i != index - 1 ; i ++) { 
      current = current.next; 
      if (current == null){ 
       throw new IndexOutOfBoundsException(); 
      } 
     } 

     Node next = current.next; 
     Node newNode = new Node(data); 
     current.next = newNode; 
     newNode.next = next; 
    } 

    public T get(int index){ 
     return getNode(index).data; 
    } 

    public void delete(int index){ 
     if (index == 0){ 
      throw new IndexOutOfBoundsException("Cannot delete HEAD node"); 
     } 

     Node prev = getNode(index - 1); 
     Node next = prev.next.next; 
     prev.next = null; 

     prev.next = next; 
    } 

    public void reverse(){ // TODO: Last node links to a null node 
     Node prev = null; 
     Node current = head; 
     Node next = null; 

     while(current != null){ 
      next = current.next; 
      current.next = prev; 
      prev = current; 
      current = next; 
     } 

     head = new Node(null); 
     head.next = prev; 
    } 

    public void display(){ 
     Node current = head; 

     String diagram = String.format("head->"); 
     while(current.next != null){ 
      current = current.next; 
      diagram += String.format("%s->", current.data); 
     } 
     System.out.println(diagram); 
    } 

    private Node getNode(int index){ 
     Node node = head; 

     for(int i = 0; i != index; i++){ 
      node = node.next; 
      if(node == null){ 
       throw new IndexOutOfBoundsException(); 
      } 
     } 

     return node; 
    } 

    private Node getLastNode(){ 
     Node current = head; 

     while(current.next != null){ 
      current = current.next; 
     } 

     return current; 
    } 

    public class Node { 
     private Node next; 
     private T data; 

     public Node(T data){ 
      this.data = data; 
     } 

     public Node getNext(){ 
      return this.next; 
     } 
    } 
} 

そしてこのmain機能：

LinkedList list = new LinkedList(); 
    list.add("e1"); 
    list.add("e2"); 
    list.add("e3"); 
    list.add("e4"); 

    list.display(); 
    list.reverse(); 
    list.display(); 

表示された結果は次のとおりです。私のLinkedListの実装を使用して

これが原因E1がまだに接続されているという事実のために起こっている

head->e1->e2->e3->e4-> 
head->e4->e3->e2->e1->null-> 

頭。私は逆利用できるオンラインの実装を使用する場合：私はここでやっている何head->e3->e2->e1->null->

：

Node prev = null; 
    Node current = head; 
    Node next = null; 

    while(current != null){ 
     next = current.next; 
     current.next = prev; 
     prev = current; 
     current = next; 
    } 

    head = prev; 

は、その後の結果はE4を捨てるだろうか？実装が他のすべてのものと異なるのはなぜですか？

headを持つすべての人がreverse関数を使用していますが、これは開発者が別のノードに入ると問題になる可能性がありますか？

Answer 1

リストの先頭に最初のノードを使用しています。逆関数の解は次のようになります。

head.next = prev; 

「ヘッド」ノードを保存して、「次へ」フィールドを変更する必要があります。

機能の残りの部分は全く変化していない：あなたのコンストラクタで

public void reverse(){ // TODO: Last node links to a null node 
    Node prev = null; 
    Node current = head.next; 
    Node next = null; 

    while(current != null){ 
     next = current.next; 
     current.next = prev; 
     prev = current; 
     current = next; 
    } 

    head.next = prev; // *** The only change *** 
} 

をあなたは持っている：

public LinkedList(){ 
    // Add HEAD 
    head = new Node(null); 
} 

そして、「頭」は、最初は何を指すのノードです。

逆の機能では、 'head'ノードは変更されません。別のノードを作成する必要はありません。しかし、正しい最初のノードを指し示す必要があります。

リストが空の場合、この 'head'はnullを指します。 リストにノードが1つしかない場合、この 'head'はまだノードを指しています。 リストに複数のノードがある場合、この 'head'は最後のノードを指し示す必要があります。

このため、「次へ」フィールドを変更する必要があります。