Copy List with Random Pointer leetcode

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Subscribe to see which companies asked this question

1、在链表中依次插入新的结点

2、构建新节点random指针：newNode->random = oldNode->random->next

3、恢复原始链表以及构建新链表：例如old->next = old->next->next,  new->next = new->next->next

 

RandomListNode *copyRandomList(RandomListNode *head) {
    if (head == nullptr)
        return nullptr;
    RandomListNode *iter = head;
    while (iter != nullptr)
    {
        RandomListNode *newNode = new RandomListNode(iter->label);
        newNode->next = iter->next;
        iter->next = newNode;
        iter = newNode->next;
    }
    iter = head;
    RandomListNode *iter1;
    while (iter != nullptr)
    {
        iter1 = iter->next;
        if(iter->random != nullptr)
            iter1->random = iter->random->next;
        iter = iter1->next;
    }
    RandomListNode *ret;
    ret = head->next;
    iter1 = ret;
    head->next = ret->next;
    iter = head->next;
    while (iter != nullptr)
    {
        iter1->next = iter->next;
        iter1 = iter1->next;
        iter->next = iter1->next;
        iter = iter->next;
    }
    return ret;
}