作者：一个喜欢猫咪的的程序员

专栏：《Leetcode》

喜欢的话：世间因为少年的挺身而出，而更加瑰丽。                                  ——《人民日报》

目录

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

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

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

https://leetcode.cn/problems/copy-list-with-random-pointer/

题目描述：

示例：

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]

输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]

输出：[[3,null],[3,0],[3,null]]

思路：

题目的要求：

使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

本题我们分为三步完成：

• 我们先将要复制的链表copy，先不管random我们先将val和next复制好。将cur和next来复制整个链表并将其链接在对应的数的后面。

• 链接完成后，我们开始处理random，我们链接后的链表是这样的。

当cur->random的下一个刚好是copy要链接的位置。因此当cur->random不为空时，copy->random=cur->random->next；cur->random为空时，置空就好了

当random处理完后，我们要将这两个链表拆开，并且保证两个链表要跟一开始一样、cur->next-next将链表变为原来的连接形式。我们用newhead来记录新链表的起始位置，copyTail来遍历链表将一个链表拆成两个链表。

时间复杂度：O（N）            空间复杂度：O（1）              

代码实现：

struct Node* copyRandomList(struct Node* head) {
  struct Node*cur=head;
    while(cur)
    {
        struct Node*next=cur->next;
        struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        cur->next=copy;
        copy->next=next;
        cur=next;
    }
    cur=head;
    while(cur)
    {
        struct Node*copy=cur->next;
        if(cur->random)
        {
            copy->random=cur->random->next;
        }
        else
        {
            copy->random=NULL;
        }
        cur=copy->next;
    }
    cur=head;
    struct Node*copyTail=NULL;
    struct Node*newhead=NULL;
    while(cur)
    {
        struct Node*copy=cur->next;
        struct Node*next=copy->next;
        cur->next=next;
        if(copyTail==NULL)
        {
            newhead=copyTail=copy;
        }
        else
        {
            copyTail->next=copy;
            copyTail=copyTail->next;
        }
        cur=next;
    }
    return newhead;
}