如何在Java中递归地将两个链表进行追加?

huangapple go评论73阅读模式
英文:

How do I recursively append two linked lists in Java?

问题

基本上,我的代码通过迭代列表,原始方法应该返回链接列表,但似乎没有将我在递归方法中链接的节点添加进去,我对此感到困惑。有人能帮助我吗?

	// 将 MyStringBuilder2 b 追加到当前 MyStringBuilder2 的末尾,
	// 并返回当前的 MyStringBuilder2。要注意特殊情况!
	public MyStringBuilder2 append(MyStringBuilder2 b)
	{
		// 测试是否无效
		if(b.firstC == null){
			return this;
		}
		// 测试条件是否满足
		else {
			CNode lastNode = firstC;
			recurseAppendBuild(lastNode, b);
			
			return this;
		}
	}
	
	private void recurseAppendBuild(CNode lastNode, MyStringBuilder2 BPoint) {
		// 测试是否所有节点都已添加
		if(lastNode.next == null && BPoint.firstC == null) {
			System.out.println("finished");
		}
		// 测试是否原链接列表中的所有节点都已通过
		else if(lastNode.next == null) {
			lastNode.next = new CNode(BPoint.firstC.data);
			BPoint.firstC = BPoint.firstC.next;
			recurseAppendBuild(lastNode.next, BPoint);
		}
		// 递归,直到满足条件为止
		else {
			recurseAppendBuild(lastNode.next, BPoint);
		}
	}

注意:以上是你提供的代码的中文翻译部分,不包含代码的原始内容。

英文:

So basically my code iterates through the list and the original method is supposed to return the linked list however it doesn't seem to be adding the nodes that I link in the recursive method and I'm confused as to why. Can anyone help me?

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

</details>


# 答案1
**得分**: 0

好的,你的代码还需要一些改进。让我们来看看你的第一个方法。我将对其进行重写。

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

    return this;
}

我做了一些改动。

  1. 我在参数上使用了一个更有意义的名称。给变量起一个有意义的名称是个好主意,不要仅仅使用 'b' 这样的名字。注意我从不使用单个字符的变量名。如果你命名为 "int i",然后搜索 i,你会得到很多根本不是 i 的结果。这是一个非常微不足道的事情,不会影响你代码的质量。

  2. 在所有情况下,你总是返回自己,因此返回语句可以放在 if-else 结构之后,这样更容易看出是相同的。

  3. 这完全消除了顶部的 if 块,所以我颠倒了逻辑。

  4. 并且我更改了递归方法的方法签名,我将在下面描述原因。

最终的结果简洁明了,容易理解。


现在,让我们看看你的第二个方法:

private void recurseAppendBuild(CNode lastNode, MyStringBuilder2 BPoint) {
    // 测试是否所有节点都已添加
    if (lastNode.next == null && BPoint.firstC == null) {
        System.out.println("finished");
    }
    // 测试是否所有原始链表中的节点都已经经过
    else if (lastNode.next == null) {
        lastNode.next = new CNode(BPoint.firstC.data);
        BPoint.firstC = BPoint.firstC.next;
        recurseAppendBuild(lastNode.next, BPoint);
    }
    // 递归,直到满足条件
    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 = OriginalList + firstItem + Append Tail of List.

private void recurseAppendBuild(CNode headToAppend) {
   if (headToAppend == null) {
       // 全部完成。
       return;
   }

   CNode nodeToAppend = new CNode(headToAppend.data);
   if (lastC == null) {
       // 原始列表为空。
       firstC = lastC = nodeToAppend;
   } else {
       lastC.next = nodeToAppend;
       lastC = nodeToAppend;  // 将尾部指向新的尾部
   }

   // 然后你总是递归。
   recurseAppendBuild(headToAppend.next);
}

让我们来看看这个。

  1. 我假设你在构建器中保留了 firstC 和 lastC。否则会非常低效。因此,你只需要传入节点的链条,而不是周围的封装器。

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

  3. 立即创建新的副本。这部分很容易,对吧?

  4. 如果 lastC 为空,说明你有一个空列表,所以你只需将列表的前后都指向新节点。

  5. 否则,将旧尾部的 next 指针指向新节点,并将尾指针更新为指向新的尾部。

  6. 无论哪种方式,你都可以安全地递归到原始列表的下一个对象。

除了能够正常工作之外,这种方法的优势是你不会破坏原始列表,而且代码很清晰易读。

英文:

Okay, your code needs some work. Let's look at your first method. I'm going to rewrite it.

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

    return this;
}

I changed a number of things.

  1. I used a more meaningful name on the argument. It's a good idea to give your variables meaningful names, not just 'b'. Note that I never use one-character names. If nothing else, it can be really hard to search on that. If you do "int i" and then search for i, you'll get a LOT of hits that aren't i at all.

This is a very trivial thing and doesn't affect the quality of your code.

  1. In all cases, you always return yourself, so the return statement can be after the if-else structure, which is easier to see that it's the same.

  2. That eliminates the top if-block entirely, so I reversed the logic.

  3. And I changed the method signature of your recursive method, for reasons I'll describe below.

The end result is short and sweet and easily understood.

<hr />
Now, let's look at your second method:

private void recurseAppendBuild(CNode lastNode, MyStringBuilder2 BPoint) {
    //Test if all nodes have been added
    if(lastNode.next==null&amp;&amp;BPoint.firstC==null) {
        System.out.println(&quot;finished&quot;);
    }
    //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. Your variable named BPoint breaks JAVA naming standards. It should start with a lower case letter.

  2. If you pass in a MyStringBuilder2 as the second argument, then as you move things from BPoint to the end of your list and recurse, you have to remove them from BPoint, which is a pain in the ass. So instead, I didn't point to the wrapper. In my code above, I passed in the head of the list (fromBuilder.firstC).

  3. You are finished when your list-to-append-from (BPoint) is empty, not when lastNode is null. Your first if is flawed.

  4. You aren't recursively adding items. You're recursively looking for the end of the list. I don't think that's what you really want.

  5. You're messing up the integrity of BPoint. You're making a copy of the nodes as you add them, but you're then dropping the old ones from BPoint but NOT maintaining lastC at all.

  6. And you have a significant problem if your list starts as empty, as firstC and lastNode will both be empty.

<hr />

So let's think about it this way. First, doing this recursively is silly, but that's the assignment, so we'll work with it.

A recursive definition is:

AppendedList = OriginalList + firstItem + Append Tail of List.

private void recurseAppendBuild(CNode headToAppend) {
if (headToAppend == NULL) {
// All done.
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);

}

Let's look at this.

  1. I'm assuming you keep both a firstC and lastC in your builder. It would be deeply inefficient otherwise. So you only need to pass in the chain of nodes, not the surrounding wrapper.

  2. By putting a null-check at the top of this method, you eliminate other null checks. Note -- this means we can eliminate the null check in the first method.

  3. Create the new copy right away. That part's easy, right?

  4. If lastC is null, you have an empty list, so you just point both front and back of the list to your new node.

  5. Otherwise you point the old tail's next pointer to your new node and update the tail pointer to remain pointed at the tail.

  6. Either way, you can safely recurse with the next object in the original list.

Advantages of this method, aside from working, is that you don't destroy the original list, and it's pretty clear to read.

huangapple
  • 本文由 发表于 2020年10月28日 02:19:01
  • 转载请务必保留本文链接:https://go.coder-hub.com/64560619.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定