LeetCode 复制带随机指针的链表(C语言)

Definition for a Node.
struct Node {
    int val;
    struct Node *next;
    struct Node *random;
    };


struct Node* copyRandomList(struct Node* head) {
	//交叉链表
    struct Node* cur,*next,*p1;//next是新节点的指针，p1是原链表中下一个结点的指针
    cur=head;//cur是遍历原链表用的
    while(cur)//遍历原结点
    {
        p1=cur->next;
        next=(struct Node*)malloc(sizeof(struct Node));//开辟新节点的空间
        cur->next=next;//下面三步是插入新结点
        next->next=p1;
        cur=p1;
    }
    //复制链表
    struct Node*p2=NULL;//储存cur指向的结点中random指向的位置
    cur=head;
    while(cur)
    {
        p1=cur->next;
        p1->val=cur->val;//变成相同的内容
        p2=cur->random;
        if(p2)//判断p2是不是指向了空指针
        {
            p1->random=p2->next;
        }
        else
        {
            p1->random=NULL;
        }
        cur=cur->next->next;//cur在原链表中进行移动
    }
    //分开两个链表
    struct Node* p3=NULL;//指向新链表的指针
    cur=head;
    while(cur)
    {
        p1=cur->next;//指向新结点
        p2=p1->next;//指向原结点，在cur结点之后
        if(p3==NULL)//第一次进行尾插
        {
            head=p3=p1;//head等于新链表的头结点，整个代码以返回head结束
            p1->next=NULL;
        }
        else//不是第一次进行尾插
        {
            p3->next=p1;//尾插
            p3=p1;//因为cur比p3先到尾部，所以不用担心p3指向空
        }
        cur->next=p2;//恢复原链表
        cur=cur->next;//cur继续遍历原链表
    }
    return head;//返回的就是新链表的头结点
}