遞歸刪除最後一次出現在鏈接列表，爪哇

class Link{ 
    private int value; 
    private Link next; 
}

我要求寫一個遞歸的方法來刪除某個值的最後出現，說4遞歸刪除最後一次出現在鏈接列表，爪哇

之前2-> 3-> 4- > 5-> 4-> 2 在2-> 3-> 4-> 5-> 2之後

僅最後一次出現。我知道如何刪除所有的發生，但我不知道它是否是最後一次發生。不允許使用輔助方法。

的一個刪除所有發生

public Link deleteAll(){ 
    if (next == null){ 
     return value==4？ null:this; 
    }else{ 
     if (value == 4){ 
      return next.deleteAll(); 
     } 
     next = next.deleteAll(); 
     return this; 
    } 
}

來源

2016-12-13 Bobby

你有完整的代碼，用列表初始化？ –

這聽起來像是一個學校項目。由於數據結構沒有嵌套，因此沒有任何理智的人會爲此問題使用遞歸（至少在語言爲Java的情況下不會）。我認爲這個任務的想法是，你試圖編寫一些代碼，並自己解決這個問題;） –

'沒有幫助方法'。您不允許編寫和調用其他方法，或者您不允許使用Internet上的LinkedList jar？ –

可以聲明一個指針到最後發生的節點，當到達列表中的最後一個元素刪除節點。以下步驟解釋 -

聲明兩個指針之一是下一個在上面的代碼中另一個可以是臨時的。
使用next來遍歷列表，就像你在deleteAll方法中做的那樣。
如果你發現你要找的節點分配給該節點的溫度。在你的情況下4.
當下一個爲null時，你到達列表的末尾，現在刪除，無論節點在臨時刪除該節點。如果temp仍然爲null，則不會在給定密鑰中找到任何節點。

編輯：在遞歸的情況下，可能的僞代碼：

public void deleteLast(Node node,Node temp,Node prev, int data) 
    { 
     if(node==null) 
     { 
      if(temp!=null && temp.next.next!=null){ 
      temp.next = temp.next.next;} 
      if(temp.next.next==null) 
      temp.next = null; 
      return; 
     } 
     if(node.data==data) 
     { 
      temp = prev; 
     } 

     prev = node; 
     deleteLast(node.next, temp, prev, int data); 

    }

上面的代碼應該能夠解決您的問題。我做了一些編輯我的方法，這應該是明顯的代碼，但讓我描述下面

我加了一個prev指針。因爲如果我們想要刪除一個特定的節點，我們需要將它的下一個分配給prev節點的下一個。因此，我們需要prev節點而不是我們想要刪除的節點。

我認爲這種改變也會在迭代方法中出現。

來源

2016-12-13 22:47:18 denis

這很有趣。但它不符合遞歸方法，是嗎？您需要解析列表兩次，才能返回到您要刪除的節點。 –

你說得對，我的答案並不是針對遞歸方法。儘管如此，也可以將它用於遞歸算法。讓我嘗試給一個僞代碼。 – denis

我認爲它會工作！我會嘗試。謝謝！ – Bobby

沒有真正回答您的確切問題，但作爲替代方案，您可能會考慮以下問題。

寫遞歸方法來刪除指定的值的第一次出現，是這樣的：

public Link deleteFirst(int target) { 
    if (value == target) { 
    return next; 
    } 
    next = (next == null) ? null : next.deleteFirst(target); 
    return this; 
}

然後，你可以寫一個reverse()方法，是一種迭代或遞歸方法，您看合適。我沒有包括這一點，但谷歌搜索應該顯示一些有用的想法。

最後從鏈表中刪除值最後一次出現的方法，然後可以這樣寫：

public Link deleteLast(int target) { 
    return reverse().deleteFirst(target).reverse(); 
}

需要注意的是，只要你的reverse()方法是線性的複雜性，這一操作將是線性複雜性也是如此，儘管常數會高於必要值。

來源

2016-12-14 00:27:47 msandiford

的訣竅是做在回來的路上工作 - 有不需要額外的參數，助手或假設都：

Link deleteLast(int target) { 
    if (next == null) { 
    return null; 
    } 
    Link deleted = next.deleteLast(target); 
    if (deleted == null) { 
    return value == target ? this : null; 
    } 
    if (deleted == next) { 
    next = deleted.next; 
    } 
    return deleted; 
}

來源

2016-12-14 00:45:05

遞歸刪除最後一次出現在鏈接列表，爪哇

回答

相關問題