【Leetcode】138. Copy List with Random Pointer（链表拷贝）（剑指offer原题）

谁借莪１个温暖的怀抱￠ 2022-02-09 08:53 124阅读 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**][deep copy] of the list.

**Example 1:**

**![1470150906153-2yxeznm.png][]**

Input:
    {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
    
    Explanation:
    Node 1's value is 1, both of its next and random pointer points to Node 2.
    Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

**Note:**

1.  You must return the **copy of the given head** as a reference to the cloned list.

题目大意：

链表节点当中会附带random指针，这个指针会指向链表当中任意节点或者为空。我们需要复制这个链表，若按照传统遍历的方式创建无法完成random随机指针的创建。

解题思路：

对于当前节点，复制一个新的将其插入到当前位置之后。第一次遍历不考虑random指针的初始化，第二遍遍历插入之后的链表，构建random，第三次遍历，创建新节点将复制的链表从中取出。

class Solution {
    public:
        Node* copyRandomList(Node* head) {
            if(head==NULL) return NULL;
            
            Node *p = head;
    
            while(p){
                Node* new_cor = new Node(p->val, p->next, nullptr);
                p->next = new_cor;
                p = new_cor->next;
            }
            
            Node *q = head;
            while(q){
                if(q->random){
                    q->next->random = q->random->next;
                }
                q = q->next->next; 
            }
            
            Node ans(0); //创建一个头为空的新链表
            p=head;
            Node* t=&ans; 
            while(p){
                t->next=p->next;
                p->next = p->next->next;
                t=t->next;
                p=p->next;
            }
            t->next=NULL;
            return ans.next;
        }
    };

[deep copy]: https://en.wikipedia.org/wiki/Object_copying#Deep_copy
[1470150906153-2yxeznm.png]: https://discuss.leetcode.com/uploads/files/1470150906153-2yxeznm.png