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

Question

所以基本上我的代码遍历列表，原始方法应该 return linked 列表但是它似乎没有添加我 link 在递归方法中，我对为什么感到困惑。谁能帮帮我？

    // 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;
}

我改变了很多东西。

我在参数中使用了一个更有意义的名称。给变量起有意义的名字是个好主意，而不仅仅是 'b'。请注意，我从不使用 one-character 名称。如果没有别的，真的很难搜索它。如果您执行“int i”然后搜索 i，您会得到很多根本不是 i 的结果。

这是一件非常微不足道的事情，不会影响您的代码质量。

在任何情况下，你总是return自己，所以return语句可以在if-else结构之后，这样更容易看出是一样。
完全消除了顶部 if-block，所以我颠倒了逻辑。
并且我更改了递归方法的方法签名，原因我将在下面描述。

最终结果短小精悍，易于理解。

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

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);
    }
}

您名为 BPoint 的变量违反了 JAVA 命名标准。它应该以小写字母开头。
如果您传入 MyStringBuilder2 作为第二个参数，那么当您将内容从 BPoint 移动到列表末尾并递归时，您必须将它们从 BPoint 中删除，这在屁股。所以相反，我没有指向包装器。在我上面的代码中，我传入了列表的头部 (fromBuilder.firstC)。
当您的 list-to-append-from (BPoint) 为空时您就完成了，而不是当 lastNode 为空时。你的第一个 if 有缺陷。
您没有递归地添加项目。您正在递归地寻找列表的末尾。我不认为那是你真正想要的。
你在破坏 BPoint 的完整性。您在添加节点时制作了节点的副本，但是您随后从 BPoint 中删除了旧节点，但根本不维护 lastC。
如果你的列表开始时是空的，你就会遇到严重的问题，因为 firstC 和 lastNode 都是空的。

所以让我们这样考虑。首先，递归执行此操作很愚蠢，但这就是赋值，所以我们将使用它。

一个递归定义是：

AppendedList = OriginalList + firstItem + Append Tail of List.

private void recurseAppendBuild(CNode headToAppend) { 如果（headToAppend == NULL）{ // 全部做完。 return; }

   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);

}

让我们看看这个。

我假设您在构建器中保留了 firstC 和 lastC。否则效率将非常低下。所以你只需要传入节点链，而不是周围的包装器。
通过将 null-check 放在该方法的顶部，您可以消除其他空值检查。注意——这意味着我们可以消除第一种方法中的空检查。
立即创建新副本。这部分很简单，对吧？
如果 lastC 为 null，则您有一个空列表，因此您只需将列表的前后都指向您的新节点。
否则你将旧尾部的下一个指针指向新节点并更新尾部指针以保持指向尾部。
无论哪种方式，您都可以安全地递归原始列表中的下一个对象。

这种方法的优点，除了工作之外，就是你不会破坏原来的列表，而且读起来很清楚。

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

How do I recursively append two linked lists in Java?

java

recursion

append

pass-by-reference

singly-linked-list