【数据结构和算法】面试必刷之随机链表复制：这三步让你彻底吃透 random 指针
🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人等方向学习者
❄️个人专栏：《C语言》《【初阶】数据结构与算法》
✨ 永远相信美好的事情即将发生
文章目录
前言
随机链表的复制是数据结构中的经典难题，核心难点在于复制节点的random指针——其指向的节点可能尚未创建，也可能指向链表中的任意节点。本文采用“原地拷贝+拆分”的最优思路，分三步拆解解题逻辑，结合代码实现与原理分析，清晰讲解如何高效解决该问题，帮助读者吃透random指针的处理技巧，掌握链表操作的核心思维。
一、随即链表的复制
1.1 题目
链接：随机链表的复制
1.2 算法原理
第一步：依次拷贝每个节点放在原节点后面
第二步：处理random指针指向 — 新链表 == (旧链表)random->next
第三步：把拷贝节点依次取下来尾插成新链表
1.3 代码
*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;*};*/ typedef struct Node* Node; struct Node*copyRandomList(struct Node* head){//拷贝每个节点放在原节点后面 Node cur = head;while(cur){ Node copy =(Node)malloc(sizeof(struct Node)); copy->val = cur->val; copy->next = cur->next; cur->next = copy; cur = copy->next;}//处理拷贝链表的random cur = head;while(cur){ Node copy = cur->next;if(cur->random ==NULL) copy->random =NULL;else copy->random = cur->random->next; cur = copy->next;}//把拷贝链表从原链表摘下来成为新链表 cur = head; Node copyhead =NULL; Node copytail =NULL;while(cur){ Node copy = cur->next; Node next = copy->next;//没有节点 + 有一个节点 if(copytail ==NULL) copyhead = copytail = copy;else{ copytail->next = copy; copytail = copytail->next;} cur = next;}return copyhead;}总结与每日励志
✨本文详细讲解了随机链表复制的完整解法，核心是通过“原地拷贝节点、关联random指针、拆分链表”三步，在O(n)时间复杂度和O(1)空间复杂度内完成复制，避开了random指针带来的难点。每一道算法题都是思维的锤炼，每一次代码调试都是能力的提升。愿你在技术学习的道路上，保持严谨与耐心，不畏惧难题，不敷衍细节，永远相信美好的事情即将发生，用坚持与积累，解锁更多算法奥秘，奔赴属于自己的成长之路。
