[C题目]力扣138. 复制带随机指针的链表

138. 复制带随机指针的链表 - 力扣（LeetCode）

题目要求： 给你一个链表A，其中结点的next用于连接前后结点，random指向当前链表A任意结点位置或者是NULL，此时需要你再创建一个相同结构的链表B，链表B与链表A长度一样、对应位置结点的val值一样、每个结点的random指向当前链表的第几个结点也一样。

思路：在链表A的每一个结点cur后面插入一个新的结点copy，cur的random指向为cur->random，而copy的random指向为cur->random->next时就能拷贝出相同的结构。当cur->next指向NULL时为特殊情况，copy->random直接指向NULL即可。

struct Node* copyRandomList(struct Node* head)
{
    //在旧链表中的每一个结点后插入新结点
    struct Node* cur=head;
    while(cur)
    {
        //创建新结点copy
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        
        //将新结点插入cur结点的后面
        copy->next=cur->next;
        cur->next=copy;

        //换下一个cur，直到为NULL后不再插入新结点。
        cur=copy->next;
    }


    //新结点复制前一个结点对应的random指向结构
    //与cur相对应的结点为cur->next
    cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;

        //random为NULL不满足复制的规律
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;
        }
        
        //换下一个cur，直到为NULL不再对cur->next进行复制random结构。
        cur=copy->next;
    }


    //拆解链表
    cur=head;
    //创建哨兵位头结点copyhead，并且初始时copyhead->next必须为NULL。
    struct Node* copyhead=(struct Node*)malloc(sizeof(struct Node));
    copyhead->next=NULL;

    //尾结点初始时为copyhead。
    struct Node* copytail=copyhead;

    //将每一个cur->next拆解下来尾插到copytail后面，直到cur为止。
    while(cur)
    {
        //用copy标记cur->next。
        struct Node* copy=cur->next;
        
        //将copy尾插到copytail后面。
        copytail->next=copy;
        //尾结点copytail更新。
        copytail=copytail->next;
        
        //下一个cur连接上前一个cur
        cur->next=copy->next;

        //对下一个cur进行判断
        cur=cur->next;
    }
    return copyhead->next;
}