随机链表深拷贝：三步法详解与代码实现

题目描述

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

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

解题思路

这道题的关键在于如何处理随机指针。由于随机指针可能指向链表中的任意节点，简单的遍历复制无法处理随机指针的指向问题。

核心思想：三步法

1. 插入复制节点：在原链表的每个节点后面插入一个复制节点
2. 设置随机指针：根据原节点的随机指针设置复制节点的随机指针
3. 分离链表：将原链表和复制链表分离

这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)（不包括结果链表）。

代码实现

/**
 * Definition for a Node.
 * struct Node {
 *   int val;
 *   struct Node *next;
 *   struct Node *random;
 * };
 */
// 创建新节点函数
struct Node* BuyNode(int x) {
    struct Node* NewNode = (struct Node*)malloc(( Node));
    NewNode->val = x;
    NewNode->next = ;
    NewNode->random = ;
     NewNode;
}

 Node*  {
     (head == )  ;
     head;
    
    (cur) {
         cur->next;
         BuyNode(cur->val);
        newnode->next = next;
        cur->next = newnode;
        cur = next;
    }
    
    cur = head;
    (cur) {
        (cur->random == ) {
            cur->next->random = ;
        }  {
            cur->next->random = cur->random->next;
        }
        cur = cur->next->next;
    }
    
    cur = head;
     ;
     ;
    (cur) {
        
         cur->next;
        
        cur->next = temp->next;
        (newhead == ) {
            newhead = temp;
            newtail = temp;
        }  {
            newtail->next = temp;
            newtail = newtail->next;
        }
        cur = temp->next;
    }
     newhead;
}