138.随机链表的复制（附带源码）

目录

一、思路分析

二、如何操作

三、源码

---

深拷贝：原封不动的拷贝一份

一、思路分析：

这一题，偏向于技巧性。如果是按照工科思维硬推，那会非常头大，脑袋瓜疼。

这一题目的核心难点在于：处理random指针

思路的核心是：创建每一个节点的拷贝，链接在该节点的后面。

那么，每一个节点的random指针就是它前一个节点的random

例如：

7的random就是前一个节点7的random

13的random就是前一个节点13的random

...

看图：

二、如何操作

1、复制节点在原链表的后面

2、从复制节点的前一个节点找到其random

3、处理完后对复制的节点进行链接，直接取下来尾插

(注意画图，带上变量进行推演)

三、源码

struct Node* copyRandomList(struct Node* head) {
	struct Node *cur = head;
    //拷贝
    while(cur)
    {
         struct Node* copy = (struct Node*) malloc(sizeof( struct Node));
         copy->val = cur->val;
         copy->next = cur->next;
         cur->next = copy;
         cur = copy->next;
    }
    //处理random
    cur = head; 
    while(cur)
    {
        struct Node *copy = cur->next;
        if(cur->random == NULL)
         {
            copy->random = NULL;
         }
        else
         {
            copy->random = cur->random->next;
         }
        cur = copy->next;
    }
    //处理新链表
    cur = head;
    struct Node *newhead = NULL;
    struct Node *tail = NULL;
    while(cur)
    {
        struct Node *copy = cur->next;
        struct Node *next = copy->next;
        if(tail == NULL)
        {
            newhead = tail = copy;
        }
        else
        {
            tail->next= copy;
            tail = tail->next;
        }
        cur->next = next;
        cur = next;
    }
    return newhead;
}