3

这是一个家庭作业。将以下递归深度复制方法更改为迭代等效方法。我走近了，需要你的帮助才能做到这一点。递归实现：

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'.

有什么建议么？

4

1 回答 1

4

您还需要在循环中向前移动，否则您会在每次迭代str中不断添加。第一次调用方法时，第一个元素不同。然后在整个循环中都是相同的。same strliststr.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 循环，因为您不知道循环应该迭代多少次。

于 2012-11-06T06:58:22.763 回答