[数据结构与算法]力扣138 -------复制带随机链表的指针

题目描述

题目链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

简单的说就是复制一个链表，链表中的指针指向关系完全相同

解题思路：

大致思路就是3步（图里面还会详细说的，如果看不懂解题思路的话）：
1先拷贝相同个数的节点，并连接在对应节点的后面（处理了val和next的指针）

2处理random指针，在图中我们不难发现拷贝的节点指针的random是前一个random的next指针

3断开所有的节点就可以了

看图理解

第一步：

第二步：

第三步：
断开连接就好了

代码分享：

struct Node* copyRandomList(struct Node* head) 
{
    if(head==NULL)
    return NULL;
    //第一步，拷贝节点并连接在后面
    struct Node* cur=head;
    while(cur)
    {
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node)); //拷贝一个头节点
        struct Node* save=cur->next; //保存下一个节点，防止找不到
        copy->val=cur->val;
        //链接
        cur->next=copy;
        copy->next=save;

        cur=save;
    }

    cur=head;
    //第二步，处理random指针
    while(cur)
    {
        struct Node* copy=cur->next; //copy就是拷贝的节点，要处理的对象
        if(cur->random==NULL)
        {
            copy->random=NULL;  //cur->random为空，然后找next会报错
        }
        else
        {
            copy->random=cur->random->next;
        }

        cur=cur->next->next;
    }

    // 断开拷贝的节点
    cur=head;
    struct Node* newhead,*newtail;
    newhead=newtail=(struct Node*)malloc(sizeof(struct Node));
    while(cur)
    {
        struct Node* save=cur->next;
        newtail->next=save;
        newtail=newtail->next;
        
        cur->next=save->next;  //将原链表连接回来
        cur=save->next;
    }
    struct Node* list=newhead->next;
    free(newhead);
    return list;	
}