力扣138 随机链表的复制

题目描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

思路分析

有很多小伙连题目都读不懂，更别说思路。下面我将进行解释：

其实就是一个关于链表的拷贝，像一般的单链表只需要遍历一遍复制即可，但这个链表多了一个随机指针random，它可以指向链表中的任意一个结点，包括它自己，同时也可以指向空。这时你可能会想到，将链表复制一遍放到新节点，再将random指向对应的源节点的位置不就行了？但题目要求复制链表中的指针都不应指向原链表中的节点 ，这就成了一个大问题。也就是说，如果碰到后面结点的random在它之前，且不知道是是什么位置，单纯的用什么所谓的双指针还是快慢指针都会很麻烦。

基于单链表，这题的最优解是：

将要复制的结点插入到每一个源节点的后面，记为copy，题目要求copy的random不能指回源节点，只能值向复制的结点，会发现，如果要取到对应的复制结点，例如原节点13的random指向7，那复制结点13也要指向复制的7，怎么取到呢，就是原结点13的random的next，是不是很巧妙？基于这个思路，即复制结点的random就是原结点的random的next值。

方法步骤：

1.将需要复制的结点插入到原结点的后面。

2.将复制结点的random指向原结点的random的next值。

3.将链表取下，恢复原链表。

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur=head;//保存头结点，用cur遍历
    while(cur)
    {
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));//复制结点用malloc创建
        copy->val=cur->val;//
        copy->next=cur->next;//进行插入
        cur->next=copy;
        cur=copy->next;//往下走
    }
    cur=head;//再从头走一遍
    while(cur)//处理random指针
    {
        struct Node* copy=cur->next;
        struct Node* next=copy->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;
        }
        cur=next;
    }
    cur=head;
    struct Node* newhead=NULL,*tail=NULL;
    while(cur)//将复制完后的链表取下
    {
        struct Node* copy=cur->next;
        struct Node* next=copy->next;//保存原链表的next值
        if(newhead==NULL)//尾插
        {
            newhead=tail=copy;
        }
        else
        {
            tail->next=copy;
            tail=tail->next;
        }
        cur->next=next;//恢复原链表
        cur=next;//往下走
    }
    return newhead;//返回新节点
}