【数据结构与算法】随机链表的复制（图文详解）

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) 
{
    Node* pcur=head;
    while(pcur)//链表数据拷贝
    {
        Node*copy=(Node*)malloc(sizeof(Node));//创建拷贝节点
        copy->val=pcur->val;//拷贝数据

        copy->next=pcur->next;//插入到pcur后面
        pcur->next=copy;

        pcur=copy->next;//移动pcur指针
    }


    pcur=head;//指针重置
    while(pcur)//链表随机指针拷贝
    {
        Node*copy=pcur->next;
        if(pcur->random==NULL)
            copy->random=NULL;//对指向NULL的情况额外处理
        else
        {
            copy->random=pcur->random->next;//随机指针拷贝的关键
        }
        pcur=copy->next;
    }

    pcur=head;
    Node*newhead=NULL,*newtail=NULL;
    while(pcur)
    {
        Node*copy=pcur->next;//指向要拷贝的节点
        Node*next=copy->next;//指向原链表原本的下一个节点

        if(newhead==NULL)//将拷贝节点尾插到新链表上
        {
            newhead=newtail=copy;
        }
        else
        {
            newtail->next=copy;
            newtail=copy;
        }

        pcur->next=next;//恢复原链表
        pcur=next;
    }
    return newhead;
}