力扣面试经典——138题

💡 参考代码：

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

struct Node* copyRandomList(struct Node* head) {
    // 如果输入为空，直接返回空
    if (head == NULL) {
        return NULL;
    }

    // 第一步：复制每个节点并插入到原节点后面
    // 原链表: 1 -> 2 -> 3
    // 复制后: 1 -> 1' -> 2 -> 2' -> 3 -> 3'
    struct Node* curr = head;
    while (curr != NULL) {
        // 创建新节点
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->val = curr->val;
        // 将新节点插入到当前节点和下一个节点之间
        newNode->next = curr->next;
        curr->next = newNode;
        // 移动到原始链表的下一个节点（跳过刚插入的复制节点）
        curr = newNode->next;
    }

    // 第二步：设置复制节点的 random 指针
    curr = head;
    while (curr != NULL) {
        // 复制节点是当前节点的下一个节点
        struct Node* copyNode = curr->next;
        // 如果原节点的 random 指针为空，则复制节点的 random 也为空
        // 否则，复制节点的 random 应该指向原节点 random 指针指向节点的复制节点
        // 原节点 random 指向的节点的复制节点就是原节点 random->next
        if (curr->random != NULL) {
            copyNode->random = curr->random->next;
        } else {
            copyNode->random = NULL;
        }
        // 移动到下一个原始节点（跳过复制节点）
        curr = copyNode->next;
    }

    // 第三步：分离原始链表和复制链表
    curr = head;
    // 复制链表的头节点
    struct Node* copyHead = head->next;
    struct Node* copyCurr = copyHead;

    while (curr != NULL) {
        // 恢复原始链表的 next 指针
        curr->next = curr->next->next;
        
        // 设置复制链表的 next 指针
        if (copyCurr->next != NULL) {
            copyCurr->next = copyCurr->next->next;
        }
        
        // 移动到下一个节点
        curr = curr->next;
        copyCurr = copyCurr->next;
    }

    // 返回复制链表的头节点
    return copyHead;
}

📖 总结：

点击展开题目总结

🤔 随机链表的复制

---

1️⃣ 题目核心信息

🎯 功能描述：实现带有随机指针的链表的深拷贝，创建一个与原链表结构完全相同但节点全新的链表

📥 输入输出：

• 输入：head - 原始链表的头节点指针
• 输出：新的链表头节点指针，其结构与原链表完全相同但所有节点都是新创建的

---

2️⃣ 实现原理

💡 核心思路：通过三次遍历原链表，在原链表中直接构建映射关系，避免使用额外的哈希表存储空间

📋 实现步骤：

1. 复制每个节点并插入到原节点之后，构建交替链表结构
2. 根据原节点的random指针设置复制节点的random指针
3. 分离原始链表和复制链表，恢复原链表并构建新链表

---

3️⃣ 关键点解析

该解法通过巧妙地将复制节点插入到原节点之后，利用位置关系建立原节点与复制节点的映射，避免了使用哈希表。

🎯 代码技巧

• 节点交织技术：将复制节点插入原节点之后，利用位置关系建立映射
• 三步分离法：先复制节点，再设置random指针，最后分离链表
• 边界处理：正确处理NULL指针和链表尾部节点

4️⃣ 使用场景

✅ 适用情况：

• 需要实现复杂链表的深拷贝
• 内存使用要求严格，不能使用额外的哈希表空间
• 链表操作中需要保持节点间复杂引用关系的场景

⚠️ 前提条件：

• 链表节点结构已知且固定
• 节点的random指针可能指向任意节点或NULL
• 允许修改原链表结构（临时）

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(n) - 需要遍历链表三次，每次遍历都是线性时间
• 💾 空间复杂度：O(1) - 只使用了常数级别的额外空间（不计算结果链表本身）

6️⃣ 注意事项

🚩 边界情况：

• 输入链表为空的情况
• 节点的random指针指向NULL的情况
• 链表只有一个节点的情况

💥 易错点：

• 在分离链表时忘记恢复原链表的结构
• random指针为NULL时的特殊处理
• 遍历过程中指针移动的步长控制错误

7️⃣ 补充说明

这个 copyRandomList 函数实现了对带有随机指针的链表进行深拷贝。它采用了"原地复制"的技巧，分三步完成：

1. 交织复制节点：在每个原节点后插入其副本
2. 设置随机指针：利用交织结构设置副本节点的 random 指针
3. 分离链表：将原链表和副本链表分离

示例演示

我们以示例 [[1,1],[2,1]] 为例，即链表有两个节点：

• 节点1 (值为1)，random指向节点2
• 节点2 (值为2)，random指向节点2自身

初始状态

原链表: 1(random->2) -> 2(random->2) -> NULL

第一步：交织复制节点

// 创建每个节点的副本并插入其后
struct Node* curr = head;
while (curr != NULL) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->val = curr->val;
    newNode->next = curr->next;
    curr->next = newNode;
    curr = newNode->next;
}

执行后状态：

交织链表: 1(random->2) -> 1'(random->?) -> 2(random->2) -> 2'(random->?) -> NULL

第二步：设置副本节点的 random 指针

// 设置复制节点的 random 指针
curr = head;
while (curr != NULL) {
    struct Node* copyNode = curr->next;
    if (curr->random != NULL) {
        copyNode->random = curr->random->next;  // 关键：利用交织结构
    } else {
        copyNode->random = NULL;
    }
    curr = copyNode->next;
}

执行过程：

1. 处理节点1：1->random 指向节点2，所以 1'->random 应该指向节点2的副本，即 2->next (也就是2')

2. 处理节点2：2->random 指向节点2自身，所以 2'->random 应该指向节点2的副本，即 2->next (也就是2')

执行后状态：

交织链表: 1(random->2) -> 1'(random->2') -> 2(random->2) -> 2'(random->2') -> NULL

第三步：分离两个链表

// 分离原始链表和复制链表
curr = head;
struct Node* copyHead = head->next;  // 新链表的头节点
struct Node* copyCurr = copyHead;

while (curr != NULL) {
    curr->next = curr->next->next;       // 恢复原链表
    if (copyCurr->next != NULL) {
        copyCurr->next = copyCurr->next->next;  // 构建新链表
    }
    curr = curr->next;
    copyCurr = copyCurr->next;
}

执行过程：

1. 恢复原链表1的next指针：1->next = 1->next->next 即 1->next = 2
2. 设置新链表1'的next指针：1'->next = 1'->next->next 即 1'->next = 2'
3. 继续处理节点2，同理恢复和设置指针

最终结果：

原链表:   1(random->2)  -> 2(random->2)  -> NULL
新链表:   1'(random->2') -> 2'(random->2') -> NULL

函数返回新链表的头节点 1'。

这个算法的巧妙之处在于利用节点交织的方式，在不使用额外存储空间的情况下建立了原节点与新节点之间的映射关系，从而能够正确设置random指针。

加载评论中...