[特殊字符] LeetCode 138. 随机链表的复制（C语言详解｜图解思路｜O(1)空间）

题目描述给你一个链表每个节点除了next指针外还有一个random指针可以指向任意节点或NULL。要求深拷贝整个链表返回新链表头节点。 一、解题思路面试最优解这题的关键是如何在不使用额外空间的情况下建立 random 关系核心技巧“节点穿插 拆分链表”✨ Step1复制节点并插入原链表原链表A → B → C复制后A → A → B → B → C → C 每个新节点插在原节点后面✨ Step2复制 random 指针关键观察A.random → B 那么 A.random → B而B B.next所以A.random A.random-next✨ Step3拆分链表把混合链表拆成两个原链表A → B → C 新链表A → B → C 二、C语言实现最优解struct Node* copyRandomList(struct Node* head) { if (head NULL) return NULL; struct Node* cur head; // 1. 复制节点并插入 while (cur) { struct Node* newNode (struct Node*)malloc(sizeof(struct Node)); newNode-val cur-val; newNode-next cur-next; cur-next newNode; cur newNode-next; } // 2. 复制 random 指针 cur head; while (cur) { if (cur-random) { cur-next-random cur-random-next; } else { cur-next-random NULL; } cur cur-next-next; } // 3. 拆分链表 cur head; struct Node* newHead head-next; while (cur) { struct Node* newNode cur-next; cur-next newNode-next; if (newNode-next) { newNode-next newNode-next-next; } cur cur-next; } return newHead; }⏱️ 三、复杂度分析类型复杂度时间复杂度O(n)空间复杂度O(1) 不使用哈希表是本题最优解 四、另一种解法哈希表思路用哈希表记录映射关系原节点 - 新节点两遍遍历创建所有节点连接 next 和 random缺点空间复杂度O(n)面试不够优雅⚠️ 五、易错点总结❗1. random 为空一定要判断if (cur-random)❗2. 拆链表顺序不能乱cur-next newNode-next; newNode-next newNode-next-next;❗3. 注意循环跳步cur cur-next-next; 六、总结一句话 本题本质利用“原节点和新节点的相对位置关系”巧妙完成 random 指针复制 面试加分点如果面试官问 为什么可以 O(1) 空间你可以答因为新节点直接插入原链表通过next关系隐式建立映射关系避免使用额外哈希表。