时间戳

首页 > 解决方案 > 克隆随机指针链表时出现未知错误

data-structures - 克隆随机指针链表时出现未知错误

问题描述

C++ 代码
有 C++ 代码用于克隆链表 请参考https://www.geeksforgeeks.org/a-linked-list-with-next-and-arbit-pointer/了解详情

Node* getNewNode(int data)
{
    Node *newNode = new Node();
    newNode->next = NULL;
    newNode->data = data;
    newNode->arb = NULL;
    return newNode;
}
Node * copyList(Node *head)
{
    Node *cur = head, *copy=NULL, *copy_cur, *next;
    while(cur)
    {
        if(!copy)
        {
            copy = getNewNode(cur->data);
            copy_cur = copy;
        }
        else
        {
            copy_cur->next = getNewNode(cur->data);
            copy_cur = copy_cur->next;
        }
        cur = cur->next;
    }
    copy_cur = copy;
    cur = head;
    while(cur)
    {
        next = cur->next;
        cur->next = copy_cur;
        copy_cur->arb = cur;
        copy_cur = copy_cur->next;
        cur = next;
    }
    copy_cur = copy;
    while(copy_cur)
    {
        copy_cur->arb = copy_cur->arb->arb->next;
        copy_cur = copy_cur->next;
    }
    return copy;
}

谁能帮我理解这个实现中的错误。

标签： data-structureslinked-listc++14

解决方案

您的代码中有几件事需要更正。您的第一个 while 循环只是创建一个新的单链接列表，其中设置了下一个指针，但没有设置“arb”指针。而不是创建一个完整的新列表，只需将新节点嵌入到原始列表中。之后设置随机指针会更容易。

Node newlyClonedNode = createNewNode(node->data);
newlyClonedNode->next = node->next;
node->next = newlyClonedNode;

然后再次遍历列表并设置新克隆节点的随机指针。

node->next->arb = node->arb->next;

完成此操作后，将新列表与原始列表分开，这样您就可以恢复原始列表以及设置了随机指针的新克隆列表。

Node clonedNode = node->next;
node->next = node->next->next;

clonedNode->next = clonedNode->next->next;

推荐阅读