2013-07-01 107 views
0

我想定義一個遞歸方法,它刪除單鏈表中等於目標值的所有實例。我定義了一個remove方法和一個removeAux方法。我該如何改變這種情況,以便如果頭部需要移除,頭部也會重新分配?以下是我迄今爲止:鏈接列表遞歸removeAll方法

public class LinkedList<T extends Comparable<T>> { 

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

    private Node(T data) { 
     this.data = data; 
     next = null; 
    } 
} 

private Node head; 

public LinkedList() { 
    head = null; 
} 

public void remove(T target) { 
    if (head == null) { 
     return; 
    } 

    while (target.compareTo(head.data) == 0) { 
     head = head.next; 
    } 

    removeAux(target, head, null); 
} 

public void removeAux(T target, Node current, Node previous) { 
    if (target.compareTo(current.data) == 0) { 
     if (previous == null) { 
      head = current.next; 
     } else { 
      previous.next = current.next; 
     } 
     current = current.next; 
     removeAux(target, current, previous); // previous doesn't change 

    } else { 
     removeAux(target, current.next, current); 
    } 
} 
+1

這是一個非常糟糕的數據結構和算法不匹配。列表是_linear_,在列表中使用遞歸沒有多大意義。如果它是一個_tree_,那麼遞歸將是適當的。 –

+0

如果您有時間,請查看我的解決方案 –

回答

0

我寧願傳遞到上一參考,當你刪除切換之前的下一個像這樣

public void remove(T target){ 
    removeAux(target,head, null); 
} 


public void removeAux(T target, Node current, Node previous) { 
     //case base 
     if(current == null) 
       return; 

    if (target.compareTo(current.data) == 0) { 

     if (previous == null) { 
      // is the head 
      head = current.next; 
     } else { 
      //is not the head 
      previous.next = current.next; 
     } 
     current = current.next; 
     removeAux(target, current, previous); // previous doesn't change 

    } else { 
     removeAux(target, current.next, current); 
    } 
} 

檢查這個答案graphically linked list可以幫助你思考如何實施它。 如果這對訓練是好的,但你可以用迭代的方式做。

+0

感謝您的幫助。我稍微改變了我的方法,並在第一次調用removeAux方法時傳遞removeAux(target,head,head.next)。我嘗試這樣做:public void removeAux(T target,Node previous,Node current){ \t \t if(current == null){ \t \t \t return; \t \t}否則{ \t \t \t如果(target.compareTo(current.data)== 0){ \t \t \t \t previous.next = current.next; \t \t \t \t current = previous.next; \t \t \t} \t \t \t removeAux(target,previous,current); \t \t} \t}但現在我得到一個堆棧溢出錯誤。有任何想法嗎? – Chip

+0

我不明白你發佈的所有內容,但在第一次打電話給你應該打電話=實際=頭和以前=空...並在如果不比較下..與實際 – nachokk

+0

@ user2506781我編輯和張貼一些代碼,希望它幫助我沒有測試可能我做了一些錯誤,但這是idead,這是因爲你有一個單一的鏈表 – nachokk

0

你可以試着設計你的功能,以便它能像這樣工作。

head = removeAux(target, head); // returns new head 

我從Coursera的算法類中學習的一個巧妙的技巧。

其餘的代碼如下。

public void removeAux(T target, Node current) { 
    //case base 
    if(current == null) 
      return null; 

    current.next = removeAux(target, current.next); 

    return target.compareTo(current.data) == 0? current.next: current; // the actual deleting happens here 
}