【leetcode每日一题】138.Copy List with Random Pointer

超、凢脫俗 2022-08-04 14:40 9阅读 0赞

题目：

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.

解析：如果是正常的链表，则直接新建结点，然后把结点连接起来即可。但是本题中是有随机结点的，可能在新建结点时，随机节点还没被创建。因此，这种方法是不可行的。我们可以先把所有的结点都复制一遍，再把它们连接起来。步骤如下：

1）在旧链表每个结点后面插入一个copyNode，让copyNode的random和next指向的结点与被拷贝的结点的random和next指向的结点相同。

2）在所有结点被创建后，调整copyNode的random指针，让它指向真正的结点。

3）将整个链表拆分，恢复旧链表，生成新链表。

代码如下：

/**
     * Definition for singly-linked list with a random pointer.
     * struct RandomListNode {
     *     int label;
     *     RandomListNode *next, *random;
     *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
     * };
     */
    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            if(head==NULL)
            {
                return head;
            }
            RandomListNode *curNode=head;
             /*第一步:在OldList的每个节点后面都插入一个copyNode(拷贝链表的结点)*/
            while(curNode!=NULL)
            {
                RandomListNode *copyNode=new RandomListNode(curNode->label);
                copyNode->random=curNode->random;
                copyNode->next=curNode->next;
                curNode->next=copyNode;
                curNode=curNode->next->next;
            }
            /*第二步:确定NewList的每个节点*/
            curNode=head;
            while(curNode!=NULL)
            {
                if(curNode->random!=NULL)
                {
                    curNode->next->random=curNode->random->next;
                }
                curNode=curNode->next->next;
            }
            /*第三步：还原OldList*/
            RandomListNode *result=new RandomListNode(0);
            result->next=head;
            RandomListNode *temp=result;
            curNode=head;
            while(curNode!=NULL)
            {
                temp->next=curNode->next;
                curNode->next=curNode->next->next;
                temp=temp->next;
                curNode=curNode->next;
            }
            return result->next;
        }
    };