手撕力扣138题：优雅复制带随机指针的链表，三步搞定经典算法题
手撕力扣138题✨：优雅复制带随机指针的链表，三步搞定经典算法题
在链表的算法考察中，带随机指针的链表复制绝对是高频考点，力扣138题虽被标注为中等难度，但实则是锻炼链表操作思维的经典简单题。普通链表的复制仅需遍历处理next指针即可，而带random随机指针的链表，因random可指向链表任意节点（或空），复刻其指向关系成为解题核心难点。本文将分享三步法解题思路，从原理剖析到C++代码实现，手把手教你优雅解决这个问题，让复杂的随机指针复制变得so easy！
一、题目核心剖析🔍
题目要求
给定一个单链表，每个节点除了包含一个next指针指向下一个节点，还包含一个random指针，该指针可以随机指向链表中的任意一个节点，也可以指向NULL。要求完整复制出这个链表的深拷贝，新链表的每个节点都是全新的节点，且next和random指针的指向关系与原链表完全一致。
解题难点
普通链表复制的核心是按序遍历处理next指针，而本题的关键痛点在于：原节点的random指针指向的位置是随机的，复制节点无法直接确定自己的random指针该指向哪个新节点。如果先单独复制所有节点再处理random指针，需要额外的哈希表存储原节点与复制节点的映射关系，而本文的三步法无需额外空间（空间复杂度O(1)），是更优的解法。
节点结构定义（C++）
首先定义题目中的链表节点结构，这是代码实现的基础：
// 定义带随机指针的链表节点 struct Node { int val; Node* next; Node* random; Node(int x) : val(x), next(NULL), random(NULL) {} }; 二、核心解题思路💡：三步法原地复制
本次解题的核心思路是原地插入复制节点→修正复制节点的random指针→拆分原链表与复制链表，全程在原链表上操作，无需额外的哈希表存储映射，时间复杂度O(n)，空间复杂度O(1)（仅使用常数个指针变量）。
为了更直观理解算法步骤，我们以原链表1 → 2 → 3 → NULL为例，其中原节点1的random指向3，原节点2的random指向1，原节点3的random指向NULL，通过图形一步步拆解算法执行过程。
步骤1：原地插入复制节点，打造“原节点-复制节点”成对链表
核心操作：遍历原链表，在每个原节点的后面插入一个值相同、random指针暂时与原节点一致的复制节点，使原链表变为原节点→复制节点→原节点→复制节点的成对结构。
操作目的：让复制节点与原节点形成一一对应的紧邻关系，为后续修正random指针提供便利，通过“原节点的random指向→原节点random的下一个节点”，即可找到复制节点的正确random指向。
图形演示
原链表：
1 → 2 → 3 → NULL | | | v v v 3 1 NULL 插入复制节点后（复制节点标为1’、2’、3’）：
1 → 1' → 2 → 2' → 3 → 3' → NULL | | | | | | v v v v v v 3 3 1 1 NULL NULL 可以看到，复制节点的random指针暂时和原节点指向相同，后续需要修正。
核心代码片段
// 步骤1：在每个原节点后插入复制节点 Node* p = head; while (p != NULL) { Node* copy = new Node(p->val); // 复制原节点的值 copy->random = p->random; // 暂时让复制节点的random与原节点一致 copy->next = p->next; // 复制节点的next指向原节点的下一个节点 p->next = copy; // 原节点的next指向复制节点 p = copy->next; // p跳转到下一个原节点，继续遍历 } 步骤2：修正复制节点的random指针，指向正确的复制节点
核心操作：遍历插入后的链表，仅处理复制节点的random指针：若原节点的random指向节点A，那么复制节点的random应指向A的复制节点A’，而A’正是A的下一个节点，因此只需将复制节点的random指向原random指向的节点的next即可。
注意点：需要判断原节点的random是否为NULL，若为NULL，复制节点的random也保持NULL，无需处理。
图形演示
待修正的链表（复制节点random未修正）：
1 → 1' → 2 → 2' → 3 → 3' → NULL | | | | | | v v v v v v 3 3 1 1 NULL NULL 修正后（复制节点random指向对应复制节点）：
1 → 1' → 2 → 2' → 3 → 3' → NULL | | | | | | v v v v v v 3 3' 1 1' NULL NULL 此时，所有复制节点的next和random指针均已指向正确位置，仅剩最后一步拆分。
核心代码片段
// 步骤2：修正复制节点的random指针 p = head->next; // p指向第一个复制节点 while (p != NULL) { if (p->random != NULL) { // 若原random不为空，才需要修正 p->random = p->random->next; } // p跳转到下一个复制节点（隔一个节点） p = (p->next != NULL) ? p->next->next : NULL; } 步骤3：拆分原链表与复制链表，得到最终的深拷贝链表
核心操作：遍历成对的链表，将原节点→复制节点→原节点→复制节点的结构拆分为原链表（原节点依次连接）和复制链表（复制节点依次连接），恢复原链表的同时，得到独立的复制链表。
操作技巧：设置两个指针分别指向原节点和复制节点，依次遍历并调整next指针，最终复制链表的头节点为原链表头节点的下一个节点（head->next）。
图形演示
待拆分的链表（已修正random）：
1 → 1' → 2 → 2' → 3 → 3' → NULL | | | | | | v v v v v v 3 3' 1 1' NULL NULL 拆分后：
原链表：1 → 2 → 3 → NULL（恢复原状）
复制链表：1' → 2' → 3' → NULL（最终结果）
核心代码片段
// 步骤3：拆分原链表和复制链表 Node* newHead = head->next; // 复制链表的头节点 Node* p1 = head; // p1指向原节点 Node* p2 = newHead; // p2指向复制节点 while (p1 != NULL) { p1->next = p2->next; // 原节点的next指向下一个原节点 p1 = p1->next; // p1后移 if (p1 != NULL) { // 若原节点未到末尾，复制节点继续后移 p2->next = p1->next; p2 = p2->next; } } return newHead; // 返回复制链表的头节点 三、完整C++代码实现📝
结合上述三步法，补充空链表判断等边界条件处理，给出完整的C++代码实现，代码逻辑清晰，注释详尽，可直接在力扣提交通过：
#include <iostream> using namespace std; // 定义带随机指针的链表节点 struct Node { int val; Node* next; Node* random; Node(int x) : val(x), next(NULL), random(NULL) {} }; class Solution { public: Node* copyRandomList(Node* head) { // 边界条件：空链表直接返回NULL if (head == NULL) { return NULL; } // 步骤1：在每个原节点后插入复制节点 Node* p = head; while (p != NULL) { Node* copy = new Node(p->val); copy->random = p->random; copy->next = p->next; p->next = copy; p = copy->next; } // 步骤2：修正复制节点的random指针 p = head->next; while (p != NULL) { if (p->random != NULL) { p->random = p->random->next; } p = (p->next != NULL) ? p->next->next : NULL; } // 步骤3：拆分原链表和复制链表 Node* newHead = head->next; Node* p1 = head; Node* p2 = newHead; while (p1 != NULL) { p1->next = p2->next; p1 = p1->next; if (p1 != NULL) { p2->next = p1->next; p2 = p2->next; } } return newHead; } }; // 测试代码（可选） void printList(Node* head) { Node* p = head; while (p != NULL) { cout << "节点值：" << p->val; if (p->random != NULL) { cout << "，random指向：" << p->random->val << endl; } else { cout << "，random指向：NULL" << endl; } p = p->next; } } int main() { // 构建测试链表 Node* n1 = new Node(1); Node* n2 = new Node(2); Node* n3 = new Node(3); n1->next = n2; n2->next = n3; n1->random = n3; n2->random = n1; n3->random = NULL; Solution s; Node* copyHead = s.copyRandomList(n1); cout << "复制链表的节点信息：" << endl; printList(copyHead); return 0; } 四、算法性能分析📊
时间复杂度
算法全程对链表进行三次遍历：插入复制节点一次、修正random指针一次、拆分链表一次。每次遍历的时间复杂度为O(n)，总时间复杂度为O(n)（时间复杂度不考虑常数项，3n最终简化为n）。
空间复杂度
算法仅使用了常数个指针变量（p、p1、p2、newHead等），未使用额外的数组、哈希表等数据结构，所有操作均在原链表上完成，因此空间复杂度为O(1)。
对比哈希表法
除了本次的三步法，解决该问题还有哈希表映射法：先复制所有节点，用哈希表存储原节点→复制节点的映射，再遍历处理next和random指针。该方法的时间复杂度也是O(n)，但空间复杂度为O(n)（需要存储n个节点的映射），相比之下，三步法是更优的原地解法。
五、解题总结与拓展📚
解题核心要点
- 原地插入复制节点是关键：让复制节点与原节点紧邻，将“随机的指向关系”转化为“固定的紧邻关系”，无需额外存储映射；
- 分步骤处理更清晰：将复杂的复制问题拆分为“插入→修正→拆分”三个简单步骤，逐个突破，降低思维难度；
- 边界条件不可忽视：必须判断原链表是否为空，同时处理
random指针为NULL的情况，避免空指针异常。
算法拓展
本题的三步法是链表原地操作的经典应用，这类思路还可迁移到其他链表问题中，例如：
- 链表的原地反转（多指针法）；
- 寻找链表的中间节点（快慢指针法）；
- 合并两个有序链表（原地合并）。
掌握链表的指针操作技巧，理解“分步骤处理”和“原地操作”的思想，能让我们更轻松地应对各类链表算法题。力扣138题作为基础经典题，是锻炼链表思维的绝佳素材，吃透这道题，后续的复杂链表问题也能迎刃而解！
写在最后：算法的学习并非死记硬背，而是理解思路、多做练习、学会迁移。希望本文的三步法能让你对带随机指针的链表复制有清晰的认识，也希望大家在刷题过程中，多思考、多总结，让算法思维不断提升✨。
