[138] Copy List with Random Pointer

微妙的題目......

以為跟deep copy linked list 差不多，但多了巧妙的地方XD

而重點就是那個，我應該自己想不到的，巧妙的地方XD

總共三步：

1. 先新增/複製每個node在原本的node之後，就變成

1-> 1' -> 2-> 2' -> 3-> 3' ......

2. 這兒我原以為可以一次處理掉random node 和 拆成新list & 舊list ，但原來！！！

因為你不知道random 會是往前還是往後指，所以還是從頭跑一遍先把 新的list 的random，都根據舊的random指好，比方說原本random指到2 ，那麼現在就要指到 2' ，簡單說就是原本的random 的下一個

3. 接下來才能把這條list 拆成新舊兩組list，並傳回新的list。

/**

* Definition for a Node.

* struct Node {

* int val;

* struct Node *next;

* struct Node *random;

* };

*/

struct Node* copyRandomList(struct Node* head) {

if (head == NULL)

return head;

struct Node* ptr = head;

while (ptr != NULL)

{

struct Node *dup = calloc(1, sizeof (struct Node));

dup->next = ptr->next;

dup->val = ptr->val;

ptr->next = dup;

ptr=dup->next;

}

ptr=head;

struct Node *new_head = head->next;

while(ptr!=NULL)

{

struct Node* p2 = ptr->next;

if (ptr->random != NULL)

p2->random = ptr->random->next;

else

p2->random = NULL;

ptr = ptr->next->next;

}

ptr=head;

while (ptr != NULL)

{

struct Node* p2 = ptr->next;

if (p2->next == NULL)

break;

ptr->next = p2->next;

ptr = p2->next;

p2->next = ptr->next;

}

return new_head;

}