/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        //在每个点的后面接上复制点
        for (auto p = head; p; ) {
            auto np = new ListNode(p->val);//把复制点new出来
            auto next = p->next;//备份p->next
            p->next = np;//接在当前点的后面
            np->next = next;//新复制的点指向之前节点的next
            p = next;//往后移
        }
        //循环一遍将每个random接好
        for (auto p = head; p; p = p->next->next) {
            if (p->random)//当前节点有random指针
                p->next->random = p->random->next;
        }
        //将新的链表拆出来
        auto dummy = new ListNode(-1);
        auto cur = dummy;
        for (auto p = head; p; p = p->next) {
            cur->next = p->next;//将cur-next指向新复制的点
            cur = cur->next;//将cur移到复制的点上
            p->next = p->next->next;//将p也往后移一位
        }
        return dummy->next;
    }
};