顛倒鏈表

Question

顛倒列表時我正在使用下面的代碼，但它添加了最後一個元素兩次。

public void reverse() 
    { 
     Node current,previous,next; 
     current=head; 
     previous=null; 
     while(current!=null) 
     { 
      next=current.getNext(); 
      current.setNext(previous); 
      previous=current; 
      current=next; 
     } 
     head=previous; 
    } 

節點類以下

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

    public Node(String dataValue) { 
     next = null; 
     data = dataValue; 
    } 

    public Node getNext() { 
     return next; 
    } 

    public void setNext(Node next) { 
     this.next = next; 
    } 

    public String getData() { 
     return data; 
    } 

    public void setData(String data) { 
     this.data = data; 
    } 
} 

我按照

public void add(String data) 
    { 
     if(head==null) 
     { 
      head=new Node(data); 
     } 
     Node temp=new Node(data); 
     Node current=head; 
     if(current!=null) 
     { 
      while(current.getNext()!=null) 
      { 
       current=current.getNext(); 
      } 
      current.setNext(temp); 
     } 
    } 

倒車列表我得到的輸出後添加在列表中的數據是繼

原始列表：[1] [2] [3] [4] [5] 逆向列表：[4] [3] [2] [1] [1 ]

Answer 1

你的問題是在add方法時，有no head到目前爲止，你需要添加一個return聲明，以避免將自身添加爲next node，爲下一個：

public void add(String data) 
{ 
    if(head==null) 
    { 
     head=new Node(data); 
     // Exit of the method to prevent adding the head as next element 
     // of the head 
     return; 
    } 
    ... 
} 

有了這個簡單的變化，如果我做：

// Create the list 
MyList list = new MyList(); 
list.add("1"); 
list.add("2"); 
list.add("3"); 
list.add("4"); 
list.add("5"); 

// Print the list content 
current = list.head; 
while(current != null){ 
    System.out.println(current.getData()); 
    current = current.getNext(); 
} 

// Inverse the list 
list.reverse(); 
System.out.println("****"); 
// Print again the list content 
current = list.head; 
while(current != null){ 
    System.out.println(current.getData()); 
    current = current.getNext(); 
} 

輸出：

1 
2 
3 
4 
5 
**** 
5 
4 
3 
2 
1 

Answer 2

填充列表時，頭部設置爲[1]，然後在此頭部後面插入節點[1]。 所以你總是有你的列表的第一個元素兩次。

你最好使用java.list.LinkedList，你可以用Node

List<Node> yourList = new LinkedList<Node>(); 
yourList.add(new Node(1)); 
yourList.add(new Node(2)); 

填補然後，您可以扭轉你的列表，只需運行：

Collections.reverse(yourList);