题目

链接：138.复制带随机指针的链表

思路

这道题的步骤总共分为三步：

步骤1

1、在题目所给的每一个链表节点的后面malloc一个节点，将原有链表节点中存储的数据值拷贝到新开辟的这个节点中，并连接在原有链表中。

如图所示：

具体步骤：

struct Node* cur = head;
    //1、在每一个节点的后面复制一个节点
    while(cur)
    {
        struct Node*copy = (struct Node*)malloc(sizeof(struct Node));
        copy->next = cur->next;//(1)
        copy->val = cur->val;//(2)
        cur->next = copy;//(3)
        cur = cur->next->next;//(4)
    }

步骤2

2、处理random。根据当前的cur节点找到random，然random的下一个节点的地址，就是cur节点的random存储的地址。

图示：

//2、连接random
    cur = head;
    while(cur)
    {
        struct Node*copy = cur->next;
        if(cur->random==NULL)//防止random为空时再对空指针进行解引用出错，因为前面没有malloc一个空间存储尾节点后的NULL
            copy->random = NULL;
        else
            copy->random = cur->random->next;//(1)
        
        cur = cur->next->next;//(2)
    }

步骤3

3、将我们malloc的节点剪取下来并进行连接同时将原来的链表重新重新连接起来。

//3、将复制的链表节点剪下并连接
    cur = head;
    struct Node*newList = (struct Node*)malloc(sizeof(struct Node));//哨兵位的节点
    newList->next = NULL;//将哨兵位的next置为空
    struct Node*newtail = newList;
    while(cur)
    {
        struct Node*copy = cur->next;
        newtail->next = copy;//(1)
        newtail = newtail->next;//(2)
        cur->next = copy->next;//(3)
        cur = copy->next;//(4)
        copy->next = NULL;//将要返回的新链表的最后一个节点的next置为NULL
    }
    struct Node*ret = newList->next;//临时变量存放哨兵位的下一个节点，就是我们要返回的节点
    free(newList);//释放开辟的哨兵位的空间
    return ret;

代码总览

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;
    //1、在每一个节点的后面复制一个节点
    while(cur)
    {
        struct Node*copy = (struct Node*)malloc(sizeof(struct Node));
        copy->next = cur->next;//(1)
        copy->val = cur->val;//(2)
        cur->next = copy;//(3)
        cur = cur->next->next;//(4)
    }
    //2、连接random
    cur = head;
    while(cur)
    {
        struct Node*copy = cur->next;
        if(cur->random==NULL)
            copy->random = NULL;
        else
            copy->random = cur->random->next;//(1)
        
        cur = cur->next->next;//(2)
    }
    //3、将复制的链表节点剪下并连接
    cur = head;
    struct Node*newList = (struct Node*)malloc(sizeof(struct Node));//哨兵位的节点
    newList->next = NULL;//将哨兵位的next置为空
    struct Node*newtail = newList;
    while(cur)
    {
        struct Node*copy = cur->next;
        newtail->next = copy;//(1)
        newtail = newtail->next;//(2)
        cur->next = copy->next;//(3)
        cur = copy->next;//(4)
        copy->next = NULL;//将要返回的新链表的最后一个节点的next置为NULL
    }
    struct Node*ret = newList->next;//临时变量存放哨兵位的下一个节点，就是我们要返回的节点
    free(newList);//释放开辟的哨兵位的空间
    return ret;
}

总结

总的来说，这道题有点类似于DNA的双螺旋复制与解螺旋，一开始的拷贝链表类似于DNA的双螺旋复制，后来的剪切链表有点类似与DNA的解螺旋，最后形成了是两条结构一模一样的链表。