迭代深度复制链接列表

Question

这是一项家庭作业。将以下递归深复制方法更改为迭代等效方法。我已经很接近了，需要你的帮助来纠正它。递归实现：

public static StringNode copy(StringNode str) {
        if (str == null)
            return null;

        StringNode copyFirst = new StringNode(str.ch, null);
        copyFirst.next = copy(str.next);
        return copyFirst;
    }

这是我想出的，迭代的等价物。该static length()方法已经实现，用于返回给定链接列表中有多少个节点。

public static StringNode copy(StringNode str) {
    if (str == null)
        return null;

    StringNode firstNode = new StringNode(str.ch ,null);
    StringNode prevNode = firstNode;
    StringNode nextNode;

    for (int i = 1; i < length(str); i++) {
        nextNode = new StringNode(str.next.ch, null);
        prevNode.next = nextNode;
        prevNode = nextNode;
    }

    return firstNode;
}

str1问题：为了测试我的实现，我创建了一个包含字符值 的链表，'n', 'b', 'a'然后调用

StringNode copy = StringNode.copy(str1);

然后我删除 str1 的最后一个节点，保留它'n','b', ，但是，当我尝试打印出副本中存储的内容时，我得到的 'n', 'b', 'b'不是'n', 'b', 'a'.

有什么建议么？

Answer 1

您还需要str在循环中向前移动，否则您将在每次迭代中不断same str添加list。第一次调用方法时，第一个元素不同。然后str.next在整个循环中都是相同的。

因此，您需要在 for 循环中添加以下代码：-

str = str.next;

另外，你的循环有一些问题。您不应该迭代直到length(str). 但直到str == null。

所以，最后你的循环应该是这样的：-

while (str.next != null) {  // Iterate till str.next != null, as we are creating 
                            // the next node in the loop for current node str

    nextNode = new StringNode(str.next.ch, null);
    prevNode.next = nextNode;
    prevNode = nextNode;

    str = str.next;  // Move to next node.
}

在这种情况下必须使用 while 循环，因为您不知道循环应该迭代多少次。