struct Node
{
    int val;
    struct Node* next;
    struct Node* random;
};
struct Node* copyRandomList(struct Node* head)
{
    struct Node* cur = head;
    //copy结点并插入原链表结点后面
    while (cur)
    {
        //创建新结点
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        //复制结点的值
        copy->val = cur->val;
        //新节点插入源链表
        copy->next = cur->next;
        cur->next = copy;
        //cur迭代往后遍历
        cur = copy->next;
    }
    //根据原结点的random处理copy的random
    cur = head;
    while (cur)
    {
        //copy指向复制链表的起点
        struct Node* copy = cur->next;
        if (cur->random == NULL)
        {
            copy->random = NULL;
        }
        //copy->random指向cur->random指向的结点的下一个结点,即next，
        // 通过桥接，使复制链表的random指向的位置于原链表相同
        else
        {
            copy->random = cur->random->next;
        }
        //cur迭代往后
        cur = copy->next;
    }
    //解开原链表和复制链表，还原原链表，链接复制的链表
    cur = head;//原链表的当前结点位置
    struct Node* copyHead = NULL, * copyTail = NULL;//复制链表的头尾
    while (cur)
    {
        struct Node* copy = cur->next;//复制链表的当前位置随着cur往后迭代
        struct Node* next = copy->next;//原链表的下一个结点位置随着cur也往后迭代
        if (copyHead == NULL)//第一个结点
        {
            copyHead = copyTail = copy;
        }
        else//尾插
        {
            copyTail->next = copy;//复制链表的链接
            copyTail = copy;//tial往后移到copy的位置
        }
        cur->next = next;//原链表还原
        cur = next;//cur往后移到next的位置
    }
    return copyHead;
}