/*

 // Definition for a Node.

 class Node {

 public:

     int val;

     Node* next;

     Node* random;

     Node() {}

     Node(int _val, Node* _next, Node* _random) {

         val = _val;

         next = _next;

         random = _random;

     }

 };

 */

 class Solution {

 public:

     Node* copyRandomList(Node* head) {

         if(head == NULL) return NULL;

         Node *p1 = head, *p2, *newhead;

         // 在原链表中交替嵌入新节点

         while(p1 != NULL) {

             Node *t = new Node();

             t->next = p1->next;

             t->val = p1->val;

             p1->next = t;

             p1 = t->next;

         }

         newhead = head->next;

         p1 = head;

         p2 = newhead;

         // 拷贝random

         while() {

             if(p1->random == NULL) p2->random = NULL;

             else p2->random = p1->random->next;

             p1 = p2->next;

             if(p1 == NULL) break;

             p2 = p1->next;

         }

         p1 = head;

         p2 = newhead;

         // 分离

         while() {

             p1 = p1->next = p2->next;

             if(p1 == NULL) break;

             p2 = p2->next = p1->next;

         }

         return newhead;

     }

 };