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.
剑指offer里面的一道题，具体思路看不懂请查阅剑指offer
/**
* 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:
void copyFirst(RandomListNode *head){ RandomListNode *pcur, *pnext, *q;
pcur = head;
while(pcur != NULL){
pnext = pcur->next;
q = new RandomListNode(pcur->label);
q->next = pnext;
pcur->next = q;
pcur = pnext;
}
}
void fixRandom(RandomListNode * head){ RandomListNode *ph = head;
while(ph!=NULL){
if(ph->random != NULL)
ph->next->random = ph->random->next;
ph = ph->next->next;
}
}
RandomListNode * getCopy(RandomListNode *head){ RandomListNode *p,*rcur,*q, *res;
res = NULL; p = head;rcur = NULL;
while(p != NULL){
q = p->next;
p->next = q->next;
p = p->next;
if(res == NULL){
res = q;
rcur = q;
}else{
rcur->next = q;
rcur = q;
}
}
// rcur->next = NULL;
return res; }
RandomListNode *copyRandomList(RandomListNode *head) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if(head == NULL) return NULL;
copyFirst(head);
fixRandom(head);
return getCopy(head); }
};