Java中的递归和链表

Question

好吧，假设我有一个在自定义 LinkedList 类中查找特定单词的函数：

public LinkedList find(String word) {
    if (this.word.equals(word))
        return this;
    if (next==null)
        return null;
    if (next.find(word)==next)
        return next;
    return null;
}

此代码工作正常，但它返回第一个找到的与条件匹配的对象。如果我想返回找到的与参数匹配的最后一个对象怎么办？我很难弄清楚这一点。请记住我想使用递归。

编辑：这段代码有什么问题：

public LinkedList findLast(String word) {
    LinkedList temp=new LinkedList(word, null);
    if (next==null && next.word.equals(word))
        return next;
    if (next==null && !next.word.equals(word))
        temp=next.findLast(word);
    return temp;
}

Answer 1

好吧，这样想：您需要向右递归到列表的末尾，然后让返回值向上冒泡。

因此，您的方法的开头应该是递归调用以进一步查看列表，或者注意到我们位于列表的末尾 - 这相当于“进一步”结果为空。

现在，当您返回时，有三个选项：

• 您已经找到晚于当前点的匹配项 - 因此返回该引用
• 您未找到匹配项（因此返回值递归调用为空）并且：
  • 当前点的单词匹配 - 因此返回当前点
  • 当前点不匹配 - 因此返回 null

希望这足以让您实现 - 如果没有，请提出更多问题。当这可能是家庭作业时，我宁愿不给出完整的实现。

Answer 2

存储对找到的最新引用的引用，并继续调用自身，直到返回 null——然后返回最新引用。

请注意，为了澄清：您将必须迭代整个链接列表（除非您有双向链接列表）才能实现此目的 - 每次找到匹配项时都存储一个引用（但只需覆盖相同的引用）每次引用）——然后一旦到达此列表的末尾，就返回引用所保存的任何内容。

public class LinkedList {

  private static int uniqueIdCounter = 0;

  private final String word;
  private int uniqueId;
  private LinkedList next = null;

  public LinkedList( String word ) {

    this.word = word;
    this.uniqueId = uniqueIdCounter++;
  }

  @Override
  public String toString() {

    return this.word + "(" + this.uniqueId + ")";
  }



  public void setNext( LinkedList next ) {

    this.next = next;
  }

  public LinkedList find( String word ) {

    return this.find( word, null );
  }

  public LinkedList find( String word, LinkedList result ) {

    if( this.word.equals( word ) ) {
        result = this;
    }

    if( this.next != null ) {

        result = this.next.find(word, result);
    }

    return result;
  }

  public static void main(String[] args) {

    LinkedList head = new LinkedList( "A");
    System.out.println( "Head is: " + head );

    LinkedList B = new LinkedList( "B" );
    head.setNext( B );
    System.out.println( "B is: " + B );

    LinkedList A2 = new LinkedList( "A" );
    B.setNext( A2 );
    System.out.println( "A2 is: " + A2 );

    LinkedList last = head.find( "A" );
    System.out.println( "Last is: " + last );
  }

}

这是输出：

头是：A(0)

B 为：B(1)

A2 是：A(2)

最后是：A(2)

Answer 3

每个直接递归函数都有两个地方可以执行一些有用的操作：在进一步的方法调用之前和之后：

  function(n){
    doBefore(n);
    function(n+1)
    doAfter(n)
  }

doBefore() 在“前进的路上”执行，doAfter() 在“返回的路上”执行。现在，您的算法会在前进过程中检查单词相等性。您必须修改您的算法，以便在返回时执行此检查。

Answer 4

public LinkedList find(String word, LinkedList result) {
   if (this.word.equals(word))
        result = this;
   if (next != null )
        return next.find(word, result)
   return result;

两句：

public LinkedList find(String word, LinkedList result) {
     result = this.word.equals(word) ? this : result;
     return next == null ? result : next.find(word, result);

@fprime：是的，解释：记住结果，用后面的结果替换它，最后返回。

只有一个参数的方法：

public LinkedList find(String word){
   result = this.word.equals(word) ? this : null;
   if(next != null)
      previous = next.find(word);
      return (previous != null) ? previous : result 
   else 
      return result;

Answer 5

只要从尾部向后跑就可以了。

public LinkedList find(String word) {
        if (this.word.equals(word))
            return this;
        if (prev==null)
            return null;
        if (prev.find(word)==prev)
            return prev;
        return null;
}

Answer 6

首先，您最初的 find(String word) 无法正常工作。

你的第一个 if 语句是完美的。这是您成功的基本案例。

你的第二个 if 语句也很完美。这是你失败的基本情况。

第三个是你出轨的地方。您已经处理了所有（在本例中是两个）基本情况，现在剩下的就是递归情况。您无需在这里检查任何内容。 next.find(word) 将返回正确答案，无论成功还是失败。

对于 findLast(String word)，我无法对 Jon Skeet 所说的内容添加太多内容。关于我可以添加的唯一建议是永远不要让节点检查其邻居。每个节点应该只检查自己。您应该会看到大量 this.word.equals(word)，但不会看到 next.word.equals(word)。

Answer 7

public LinkedList find(String word) {
  if(this.word.equals(word)) return this;
  return next==null?null:next.find(word);
}


公共LinkedList rfind（字符串字）{
  如果（下一个！=空）{
    LinkedList res = next.rfind(word);
    if(res != null) 返回 res;
  }
  return this.word.equals(word)?this:null;
}