Java 中链表的深度复制构造函数-解网

问：

我有一个硬件分配，其中只有一小部分是制作一个复制构造函数，该构造函数会对您在其参数中输入的链表进行深度复制。

我理解这意味着，您输入的链表保持不变，并且新链表与“旧”链表隔离。我的代码给了我一个新列表，它与旧列表（您作为参数输入的列表）完全相同，这就是我想要的，但旧列表已更改。List

下面是构造函数：

public SortedLinkedSet(SortedLinkedSet<T> copy) {
    if (copy == null) {
        this.firstNode = null;
    } else{
        SortedLinkedSetNode firstNode1 = new SortedLinkedSetNode(copy.getFirstNode().value);
        this.firstNode = firstNode1;
       // so basically I am chaining elements from "copy" to firstNode1 and then making "this" = to firstNode1. 
        while (copy.firstNode.next !=null) {  
            firstNode1.add(copy.getFirstNode().next.value);
            this.firstNode = firstNode1;
            copy.firstNode = copy.firstNode.next;
       // at the end of this loop I have a successful new linkedList with the same value, but "copy" has been changed
        }
    }      
}

例如，如果我输入一个具有值的链表 - 使用这个构造函数，我得到一个带有值的新链表，但旧的链表只有 1。如果有人能帮助我解释为什么会出错，那就太好了。谢谢(1,2,3)1,2,3

更新：正如 Ireeder 所指出的，通过我所做的测试，我几乎可以肯定问题出在陈述中： copy.firstNode = 复制.firstNode.next; 我删除了当前代码，并进行了以下测试：

SortedLinkedSetNode firstNode = new SortedLinkedSetNode(copy.getFirstNode().value);
this.firstNode=firstNode;

firstNode.add(copy.getFirstNode().next.value);
this.firstNode = firstNode;

firstNode.add(copy.getFirstNode().next.next.value);
this.firstNode = firstNode;

这工作得很好（但我事先知道我只用 3 个元素列表进行测试）。我将如何在不使用诸如以下语句的情况下使用 while 循环来做到这一点： copy.firstNode = 复制.firstNode.next; 我必须以某种方式沿着“复制”列表移动？

Java Linked-List Copy-Constructor 深拷贝复制

this.firstNode = firstNode1;
// so basically I am chaining elements from "copy" to firstNode1 and then making "this" = to firstNode1. 

SortedLinkedSetNode currentNode = copy.firstNode;

while (currentNode.next !=null) {  
    firstNode1.add(currentNode.next.value);
    this.firstNode = firstNode1;
    currentNode = currentNode.next;
 }

你是对的，我刚刚做了一个测试，删除了这个语句和 while 循环，然后又添加了 3 个“添加”语句，其中我首先调用 copy.getfirstNode.value，然后在下一个 copy.getFirstNode.next.value 中调用，最后是 copy.getFirstNode.next.next.value 并且它有效（但我知道我只用 3 个元素列表进行测试）。当我尝试在循环中执行此操作时（“while”，因为我不知道长度），我看不出如何不使用这样的语句。感谢您指出！

0赞 lreeder 3/4/2014

使用 temp 变量存储对列表中当前节点的引用，并更新该变量而不是原始变量。查看我更新的答案。

0赞 Joop Eggen 2/8/2022 #2

首先要复制的原件，叫做，就像在复制这个吗？copy

您确实与正确的节点混淆了，并且代码不够简单。

简化事情的递归解决方案似乎是合适的：

public SortedLinkedSet(SortedLinkedSet<T> original) {
    Objects.requireNotNull(original);
    this.firstNode = copyNodes(orignal.firstNode);
}

private SortedLinkedSetNode copy(SortedLinkedSetNode originalNode) {
    if (originalNode == null) {
        return null;
    }
    SortedLinkedSetNode node = new SortedLinkedSetNode(originalNode.value);
    node.next = copy(originalNode.next);
    return node;
}

如果节点的值也需要深度复制，则可以在一个地方完成。

循环仍然很简单。一种方式：

private SortedLinkedSetNode copy(SortedLinkedSetNode originalNode) {
    SortedLinkedSetNode firstNode = null;
    SortedLinkedSetNode previousNode = null;
    while (originalNode != null) {
        SortedLinkedSetNode node = new SortedLinkedSetNode(originalNode.value);
        if (firstNode == null) {
            firstNode = node;
        } else {
            previousNode.next = node;
        }
        previousNode = node;
        originalNode = originalNode.next;
    }
    return firstNode;
}

上一个：Java 中链表的深度复制构造函数

下一个：如何使用委托构造函数和条件初始化程序列表编写复制/移动构造函数

Java 中链表的深度复制构造函数

Deep Copy Constructor for Linked List in Java

评论

评论