递归如何在Java中递归地附加两个链表？

Question

基本上，我的代码遍历链表，原始方法应该返回链表，但是它似乎没有添加我在递归方法中链接的节点，我不知道为什么。有人能帮我吗

    // Append MyStringBuilder2 b to the end of the current MyStringBuilder2, and
    // return the current MyStringBuilder2.  Be careful for special cases!
    public MyStringBuilder2 append(MyStringBuilder2 b)
    {
        //Test if Invalid
        if(b.firstC==null){
            
            return this;
        }
        //Test if condition is met
        else {
            CNode lastNode =firstC;
            recurseAppendBuild(lastNode, b);
            
            return this;
            
        }
    }
    private void recurseAppendBuild(CNode lastNode, MyStringBuilder2 BPoint) {
        //Test if all nodes have been added
        if(lastNode.next==null&&BPoint.firstC==null) {
            System.out.println("finished");
        }
        //Tests if all nodes in the original linked list have been passed through
        else if(lastNode.next==null) {
            
            lastNode.next= new CNode(BPoint.firstC.data);
            BPoint.firstC=BPoint.firstC.next;
            recurseAppendBuild(lastNode.next, BPoint);
        }
        //Recurse until condition is met
        else {
            
            recurseAppendBuild(lastNode.next, BPoint);
        }
    }
    ```

Answer 1

好的，你的代码需要修改。让我们看看你的第一种方法。我要重写它

public MyStringBuilder2 append(MyStringBuilder2 fromBuilder)
{
    if (fromBuilder.firstC != null) {
        recurseAppendBuild(fromBuilder.firstC);
    }

    return this;
}

我改变了很多事情

1. 我在辩论中使用了一个更有意义的名字。最好给变量起一个有意义的名字，而不仅仅是“b”。请注意，我从不使用一个字符的名称。如果没有别的东西，那就很难在上面搜索了。如果你做“inti”然后搜索i，你会得到很多根本不是i的点击率

这是一件非常琐碎的事情，不会影响代码的质量

1. 在所有情况下，您总是返回自己，因此return语句可以位于if-else结构之后，这样更容易看出它是相同的

2. 这就完全消除了top if块，所以我颠倒了逻辑

3. 我更改了递归方法的方法签名，原因如下所述

最终的结果是简短、甜蜜且易于理解

---

现在，让我们看看你的第二种方法：

private void recurseAppendBuild(CNode lastNode, MyStringBuilder2 BPoint) {
    //Test if all nodes have been added
    if(lastNode.next==null&&BPoint.firstC==null) {
        System.out.println("finished");
    }
    //Tests if all nodes in the original linked list have been passed through
    else if(lastNode.next==null) {
        
        lastNode.next= new CNode(BPoint.firstC.data);
        BPoint.firstC=BPoint.firstC.next;
        recurseAppendBuild(lastNode.next, BPoint);
    }
    //Recurse until condition is met
    else {
        
        recurseAppendBuild(lastNode.next, BPoint);
    }
}

1. 名为BPoint的变量违反了JAVA命名标准。它应该以小写字母开头

2. 如果你把一个MyStringBuilder2作为第二个参数传入，那么当你把东西从BPoint移到列表的末尾并递归时，你必须把它们从BPoint中移除，这是一件很麻烦的事。所以，我没有指向包装器。在上面的代码中，我输入了列表的开头（fromBuilder.firstC）

3. 当要从中追加的列表（BPoint）为空时，而不是lastNode为空时，就完成了。你的第一个if有缺陷

4. 您没有递归地添加项。你在递归地寻找列表的末尾。我觉得这不是你真正想要的

5. 你把BPoint的完整性搞砸了。在添加节点时，您会创建节点的副本，但随后会从BPoint中删除旧节点，但根本不会维护lastC

6. 如果列表开始时为空，则会出现一个严重的问题，因为firstC和lastNode都将为空

---

所以让我们这样想。首先，递归地这样做是愚蠢的，但这是一个任务，所以我们将使用它

递归定义是：

AppendedList=原始列表+第一项+附加列表尾部

私有void recurseAppendBuild（CNode headToAppend）{ if（headToAppend==NULL）{ //都搞定了。 回来 }

   CNode nodeToAppend = new CNode(headToAppend.data);
   if (lastC == nullptr) {
       // Original list is empty.
       firstC = lastC = nodeToAppend;
   else {
       lastC.next = nodeToAppend;
       lastC = nodeToAppend;  // Point the tail at the new tail
   }

   // And here you recurse, always.
   recurseAppendBuild(headToAppend.next);

}

让我们看看这个

1. 我假设你的建筑中同时保留了firstC和lastC。否则的话，效率将非常低下。因此，您只需要传递节点链，而不需要传递周围的包装器

2. 通过在这个方法的顶部放置一个空检查，可以消除其他空检查。注意，这意味着我们可以在第一个方法中消除空检查

3. 立即创建新副本。那部分很简单，对吧

4. 如果lastC为null，则列表为空，因此只需将列表的前面和后面都指向新节点

5. 否则，将旧尾部的下一个指针指向新节点，并更新尾部指针以保持指向尾部

6. 无论哪种方式，都可以安全地使用原始列表中的下一个对象递归

除了工作之外，这种方法的优点是不破坏原始列表，而且阅读起来非常清晰