递归删除最后一次出现在链接列表，爪哇

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

递归删除最后一次出现在链接列表，爪哇

回答

相关问题