java中的鏈接列表

Question

我必須爲鏈表列類編寫一個非常簡單的方法，但我遇到了一些問題。此方法稱爲squish()，它取得此列表，並且在連續兩個或多個項目 相等（使用equals()進行比較）的任何位置，它將刪除重複節點，以便只保留一個連續副本。因此，在該程序完成後，該列表中沒有兩個連續項目是相等的。

執行squish()後，列表可能會比squish()開始時短。沒有額外的項目被添加來彌補那些被刪除。

例如，如果輸入列表是[ 0 0 0 0 1 1 0 0 0 3 3 3 1 1 0 ]，則輸出列表是[ 0 1 0 3 1 0 ]。

這是我的方法：

public void squish() { 
SListNode current = head; 
boolean end =false; 

    while(end == false) 
    { 


     if(!current.item.equals(current.next.item)) 
      current=current.next; 
     else 
     { 
      while(current.item.equals(current.next.item) && current.next !=null) 
       current.next=current.next.next; 
      current=current.next; 

     } 
    if (current==null) 
     end=true; 
    } 


     } 

，這是一個小的主要執行代碼。

public class main { 
public static void main(String args[]) 
{ 



    int[] test6 = {6, 6, 6, 6, 6, 3, 6, 3, 6, 3, 3, 3, 3, 3, 3}; 
    SList list6 = new SList(); 
    for (int i = 0; i < test6.length; i++) { 
     list6.insertEnd(new Integer(test6[i])); 
    } 
    System.out.println("squishing " + list6.toString() + ":"); 
    list6.squish(); 
    String result = list6.toString(); 
    System.out.println(result); 


    int[] test5 = {3, 7, 7, 7, 4, 5, 5, 2, 0, 8, 8, 8, 8, 5}; 
    SList list5 = new SList(); 
    for (int i = 0; i < test5.length; i++) { 
     list5.insertEnd(new Integer(test5[i])); 
    } 

    System.out.println("squishing " + list5.toString() + ":"); 
    list5.squish(); 
    result = list5.toString(); 
    System.out.println(result); 

} 

} 

調試代碼我可以看到該方法工作正常..只在列表的末尾，他trhows空異常指針。你可以幫我嗎？感謝

Answer 1

我會做這樣的：

public void squish() { 
    SListNode current = head; //1 

    if(current = null) return; //1a 

    while(current.next != null) { //2 
     if(current.item.equals(currennt.next.item)) 
      current.next = current.next.next; //3 
     else 
      current = current.next; //4 
    } 
} 

這是什麼樣的是PROFS想要分配遞歸的事情，而大部分專業人士不使用遞歸我已經設置了方法途徑。

第1行是init，您將指定將遍歷列表到指向鏈表的開始的指針。

第1a行如果列表中沒有元素，則返回。

第2行是基本情況。如果我們在列表中只有一個元素，那麼就沒有任何事情要做。

3號線是感應如果我們在一個節點的指點下，我們考察隔壁的節點。如果它們具有相同的值，那麼我們可以移除隔壁的節點。

4號線3號線的東西，我們都看着隔壁的節點，並認爲這是不相等的。因此我們遍歷這個列表。

這可能是一個有用的練習遍歷用手問題所提供的測試數據，然後添加一些的System.out.println對我的例子，看看你是正確的。我必須這麼做，今天有一些棘手的代碼弄清楚發生了什麼事情。

Answer 2

當行if(!current.item.equals(current.next.item))在最後一次迭代中執行，current.next點null爲current是列表中的最後一個項目，實際上有沒有下一個項目。

編輯

在你的評論，現在我看到你在該行

while(current.item.equals(current.next.item) && current.next !=null) 

順利拿到了NullPointerException，你應該只是互相替換這些兩個條件：首先確認current.next不null，然後等於current和next：

while(current.next !=null && current.item.equals(current.next.item)) 

順便說一句，當你的列表只有一個元素時，你仍然可以在行if(!current.item.equals(current.next.item))中得到NPE。例如，要解決這個問題，只需檢查head.next == null。如果是這樣，首先不要啓動while循環。

Answer 3

的問題是在這條線：

while(current.item.equals(current.next.item) && current.next !=null) 

這裏，條件的第一部分存取current.next.item，即使current.next爲空，由於條件的第二部分（current.next !=null）被之後檢查第一個（並且僅當第一個評估爲true時，見下文）。爲了解決這個問題，只是反轉條件：

while(current.next !=null && current.item.equals(current.next.item)) 

這種方式，表達如果current.next !=null是真的current.item.equals(current.next.item)纔會執行（short-circuit evaluation），即，當它是安全的這樣做。

另外，我認爲你可以放棄第一個if聲明。看一下@ Pete的答案，如何簡化方法。