单链表OJ题：LeetCode–138.复制带随即指针的链表

朋友们、伙计们，我们又见面了，本期来给大家解读一下LeetCode中第138道单链表OJ题，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

数据结构与算法专栏：数据结构与算法

个  人  主  页 ：stackY、

C 语 言 专 栏：C语言：从入门到精通

 LeetCode–138.复制带随即指针的链表：https://leetcode.cn/problems/copy-list-with-random-pointer/description/

目录

1.题目介绍

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

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

小编现在这里向大家袒露心扉一下：其实我刚刚看到这个单链表OJ题，看了半天连题目都没咋搞明白，好不容易看懂了题目介绍，可是又不知道该从何下手，然后求助各种大佬，才慢慢理解，然后整理思路，在这篇文章中将这道题分享给大家。

2.实例演示

3.解题思路

这道题应该算是单链表OJ题中比较复杂的一道题了，主要是比较难理解。题目的主要意思就是要拷贝出与原链表一模一样的一个链表。那么这道题拷贝链表都不是很复杂，比较难处理的就是这个随即指针random的指向，如果原链表的random指向空那这好说，拷贝链表的也指向空，但是如果原链表的random指向非空，那该如何去找这个random呢？在这里呢，很多老铁喜欢用random指向的值来比较，这种想法可以，但是架不住链表中有相同的值，那么就有许多老铁用它的random指向的地址来比较，这种方法是完全可行的，但是呢，这种暴力求解的方法往往都不是最优解，使用地址来进行比较的话它的时间复杂度是O(N^2)，效率也是不太行。所以我们需要寻求更优解。

这道题的解题思路我分为了三个步骤：

1. 链接拷贝结点：

 将拷贝结点插入到原结点的后面。

2. 找拷贝节点的random：

通过原链表来控制拷贝结点的随机指针random。

3. 拆解拷贝链表：

将拷贝结点拆下来，依次尾插组成新的链表，然后恢复原链表。

接下来我们一步一步来进行解题：

：：链接拷贝结点 ：： 

我们可以将拷贝结点链接在原结点的后面，这种方法比较巧妙，有助于我们找随即指针random。

先创建拷贝节点，然后遍历原链表，然后保存头节点的下一个结点，改变指向，将拷贝节点插入到原结点的后面。

图示：

 

代码演示：

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;

    //1.链接拷贝节点
    while(cur)
    {
        //创建拷贝结点
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;

        //保存头指针的下一个结点
        struct Node* curNext = cur->next;

        //链接
        cur->next = copy;
        copy->next = curNext;
        cur = curNext;
    }
    //......
}

 ：：找拷贝节点的random ：：

当我们将拷贝结点链接在原结点的后面时，我们需要找拷贝结点的随机指针random，这里可以分为两种情况：

1. 如果原结点的random是空，那么直接将拷贝结点的random置为空即可。

2. 若不为空，那么就需要观察一下这个链表，拷贝结点的random指针指向的就是原结点的random指向的结点的next结点：

                               copy -> random = cur -> random -> next;

因为我们将拷贝结点链接在了原结点的后面，那么原结点的random指向的结点的next结点就是拷贝结点要找的random。我们依旧遍历整个链表，然后将拷贝节点的随机指针链接。

图示：

 

代码演示：

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;

    //1.链接拷贝节点
    while(cur)
    {
        //创建拷贝结点
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;

        //保存头指针的下一个结点
        struct Node* curNext = cur->next;

        //链接
        cur->next = copy;
        copy->next = curNext;
        cur = curNext;
    }

    //2.找拷贝节点的random 
    //重新返回头
    cur = head;
    while(cur)
    {
        //找拷贝结点
        struct Node* copy = cur->next;
        //找下一个结点
        struct Node* next = copy->next;

        //链接拷贝节点的随机指针random
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }

        //遍历
        cur = next;
    }
    //......
}

：： 拆解拷贝链表 ：：

我们找到了拷贝链表之后呢，需要将这些拷贝的结点组成一个新的链表，这就需要将这些拷贝结点依次进行尾插，然后再将原链表恢复。这就比较简单了：

图示：

 完整代码演示：

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;

    //1.链接拷贝节点
    while(cur)
    {
        //创建拷贝结点
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;

        //保存头指针的下一个结点
        struct Node* curNext = cur->next;

        //链接
        cur->next = copy;
        copy->next = curNext;
        cur = curNext;
    }

    //2.找拷贝节点的random 
    //重新返回头
    cur = head;
    while(cur)
    {
        //找拷贝结点
        struct Node* copy = cur->next;
        //找下一个结点
        struct Node* next = copy->next;

        //链接拷贝节点的随机指针random
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }

        //遍历
        cur = next;
    }

    //3.拆解拷贝结点，恢复原链表
    //重新返回头
    cur = head;

    //创建新的链表
    struct Node* copyHead = NULL;
    struct Node* copyTail = NULL;

    while(cur)
    {
        //找拷贝结点
        struct Node* copy = cur->next;
        //找下一个结点
        struct Node* next = copy->next;

        //尾插拷贝节点构成新的链表
        if(copyTail == NULL)
        {
            copyHead = copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }

        //恢复原链表
        cur->next = next;
        cur = next;
    }
    
    return copyHead;

}

朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！