LeetCode138—Copy List with Random Pointer

小灰灰 2022-07-18 09:07 127阅读 0赞

## 原题 ##

[原题链接][Link 1]

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

--------------------

## 分析 ##

拷贝链表，但是这个链表多了一个指针域，该指针可以指向链表中任意节点。

考虑对一般链表的拷贝，肯定是要不停的new节点，然后尾插法插入链表，但是现在问题来了，在一个循环中，如果只干这一件事情，那么对于random指针域就需要重新进行循环，并且由于链表不支持随机访问，传统的方法复杂度会大大增加。

可以考虑把新new出来的节点插入到原链表中，如图：

![这里写图片描述][20160908110336773]

这样，对于原链表中的节点来说：  
p->next 就是新链表中自己的拷贝。

所以当构造完整个链表后，就可以方便处理节点的random指针域，即

if(p->random!=NULL)
        p->next->random=p->random->next;

拷贝完random域，就要把拷贝的节点从原链表中剥离出来，也就是从原链表中删除节点操作。

最后，一个细节就是（其实提交的时候也会提示），也就是原链表各个节点的指针域是不能改变的，考虑特殊情况，稍微处理一蛤即可。

--------------------

## 代码 ##

class Solution {
    
        public:
        RandomListNode *copyRandomList(RandomListNode *head) 
        {
            if(head==NULL)
                return NULL;
            RandomListNode * head_=new RandomListNode(0);//头节点
            //创建带头节点的链表，方便链表操作
            RandomListNode * p = head;
            RandomListNode * k = head_;
    
            while(p)//构建新链表
            {
                RandomListNode* r = new RandomListNode(p->label);
                r->next = p ->next;
                p->next = r;
                p=r->next;
            }
            p=head;
    
            while(p)//拷贝random指针域
            {
                if(p->random)
                    p->next->random=p->random->next;
                p=p->next->next;
            }
    
            p=head->next;
            RandomListNode * o = head;//指针o表示origin原链表
    
            while(p)//“删除”节点
            {
                o->next=o->next->next;
                k->next=p;
                k=p;
                if(p->next)
                    p=p->next->next;
                else//特殊情况处理一下
                    break;
                o=o->next;
            }
    
            return head_->next;
    
        }
    
    };

[Link 1]: https://leetcode.com/problems/copy-list-with-random-pointer/
[20160908110336773]: /images/20220717/7afcb684a14541be9489636cfc490171.png