138. 复制带随机指针的链表（深拷贝）题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了138. 复制带随机指针的链表（深拷贝）题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述：138. 复制带随机指针的链表 - 力扣（LeetCode）

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

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

138. 复制带随机指针的链表（深拷贝）题解,数据结构Oj,链表,数据结构

题解思路：

第一遍循环：复制节点并插入原节点之后

在这一步中，我们会遍历原链表，并为每个节点创建一个新的节点，然后将新节点插入到原节点之后-->插入时可以采用先用新节点的next指向current的next，在用current的next指向新节点，最后再将current移动到新节点的next；如果先将current的next指向新节点，这样就还需要保存原节点的下一个。

第二遍循环：设置新节点的随机指针

我们可以根据原节点的随机指针来设置新节点的随机指针。如果原节点的随机指针不为空，那么新节点的随机指针应该指向原节点随机指针指向的新节点（原节点的下一个节点）；如果原节点的随机指针为空，新节点的随机指针指向NULL。

第三遍循环：拆分链表

在这一步，我们需要将链表分成原链表和新链表。我们遍历链表，将每个新节点连接到一起，同时恢复原链表的 next 指针-->利用尾插的思想，将新节点作为尾插节点进行尾插；

最后返回新链表的头指针。

代码：

struct Node* creatNode(int val)
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->val = val;
    newNode->next = NULL;
    newNode->random = NULL;
    return newNode;
}
struct Node* copyRandomList(struct Node* head) 
{
	// 复制节点并插入原节点之后
    struct Node* current = head;
    while(current)
    {
        struct Node* next = current->next;
        struct Node* newNode = creatNode(current->val);
        newNode->next = current->next;
        current->next = newNode;
        current = next;
    }
    // 设置新节点的随机指针
    current = head;
    while(current)
    {
        struct Node* newNode = current->next;
        if(current->random != NULL)
        {
            newNode->random = current->random->next;
        }
        else
        {
            newNode->random = NULL;
        }
        current = newNode->next;
    }
    // 拆分链表
    struct Node* newHead = NULL, *newTail = NULL; 
    current = head;
    while(current)
    {
        struct Node* newNode = current->next;
        struct Node* next = newNode->next;
        // 尾插
        if(newTail == NULL)
        {
            newHead = newTail = newNode;
        }
        else
        {
            newTail->next = newNode;
            newTail = newNode;
        }
        current->next = next; // 恢复原链表的 next 指针
        current = next;
    }
    return newHead;
}

注：（第一步图解）

138. 复制带随机指针的链表（深拷贝）题解,数据结构Oj,链表,数据结构