在java中實現一個鏈表在

Question

我正在閱讀關於java中的鏈表，我編寫了這個代碼，當我運行它時，我得到了3作爲輸出，它應該打印出插入數字的反向順序如下：10 7 3 ..我的代碼有什麼問題？

public class List { 
    private class ListNode { 
     private int contents; 
     private ListNode next; 

     ListNode(int contents) { 
      this.contents = contents; 
      this.next = null; 
     } 
    } 

    private ListNode head; 

    public List() { 
     head = null; 
    } 

    public void insert(int contents) { 

     ListNode newNode = new ListNode(contents); 
     if (head == null) { 
      head = newNode; 
     } 

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

     current = newNode; 

    } 

    public void reverse() { 

     ListNode current = head; 
     ListNode nodeNext = current.next; 

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

     head = current; 
    } 

    public String toString() { 

     String s = ""; 
     ListNode current = head; 
     while (current != null) { 
      s = current.contents + s; 
      current = current.next; 
     } 

     return s; 
    } 

    public static void main(String[] args) { 

     List l = new List(); 
     l.insert(3); 
     l.insert(7); 
     l.insert(10); 
     l.reverse(); 
     System.out.println(l.toString()); 

    } 
} 

感謝

Answer 1

private ListNode head; 
private ListNode tail; 
public void insert(int contents) { 

    ListNode newNode = new ListNode(contents); 
    if (head == null) { 
     head = newNode; 
     tail = newNode; 
     return; 
    } 
    tail.next = newNode; 
    tail = newNode; 
} 

保持爲O（1）插入一個尾節點參考。

你reverse()方法是有點不對：

// this loop will run forever if there are more than 1 nodes 
while (nodeNext != null) { 
    current.next = null; 
    nodeNext.next = current; // you lose the reference to the entire list here 
    current = nodeNext; 
} 

重寫功能：

public void reverse() { 
    ListNode cursor = head; 
    ListNode newHead = null; 

    while (cursor != null) { 
     ListNode next = cursor.next; 
     cursor.next = newHead; 
     newHead = cursor; 
     cursor = next; 
    } 
    head = newHead; 
} 

做cursor.next = newHead，失去原有的參考cursor.next。所以你需要採取臨時變量的cursor.next參考：ListNode next = cursor.next;

打印功能

public void print() { 
    ListNode cursor = head; 
    while (cursor != null) { 
     System.out.println(cursor.contents); 
     cursor = cursor.next; 
    } 
} 

Answer 2

你insert法新節點無法連接到現有列表的最後一個節點。你必須到新節點分配給現有列表的最後一個節點的node.next：

public void insert(int contents) { 

    ListNode newNode = new ListNode(contents); 
    if (head == null) { 
     head = newNode; 
     return; 
    } 

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

    current.next = newNode; 

}