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.

 

思路：

做过，先复制一遍指针，再复制random位置，再拆分两个链表。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;// 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 NULL;        RandomListNode * p = head;        //在每个结点后面复制一个自己 不管random指针        while(p != NULL)        {            RandomListNode * cpy = new RandomListNode(p->label);            cpy->next = p->next;            p->next = cpy;            p = cpy->next;        }        //复制random指针        p = head;        while(p != NULL)        {            RandomListNode * cpy = p->next;            if(p->random != NULL)            {                cpy->random = p->random->next;            }            p = cpy->next;        }        //把原链表与复制链表拆开        RandomListNode * cpyhead = head->next;        p = head;        RandomListNode * cpy = cpyhead;        while(p != NULL)        {            p->next = cpy->next;            cpy->next = (cpy->next == NULL) ? cpy->next : cpy->next->next;            p = p->next;            cpy = cpy->next;        }        return cpyhead;    }};int main(){    RandomListNode * r = new RandomListNode(-1);    Solution s;    RandomListNode * ans = s.copyRandomList(r);    return 0;}