本文概览本文以LeetCode经典题目随机链表的复制为例从随机指针带来的复制难点入手先讲解哈希表记录新旧节点映射关系的解法再优化到拼接拆分的 O(1) 空间解法一、题目二、题目分析给定一个链表每个节点除了next指针之外还有一个random指针random可以指向链表中的任意节点也可以指向null目标对这个链表进行深拷贝返回复制链表的头节点核心难点普通链表复制并不难难的是random指针。因为新节点的random必须指向新链表中的对应节点不能继续指向旧链表中的节点思路概览最终优化版 Java 实现代码如下public Node copyRandomList(Node head) { if (head null) return null; Node cur head; // 拼接新节点到原节点后面 while (cur ! null) { Node newNode new Node(cur.val); newNode.next cur.next; cur.next newNode; cur newNode.next; } // 处理随机指针 cur head; while (cur ! null) { if (cur.random ! null) { // 新节点的随机指针指向旧节点的随机指针的下一个节点 cur.next.random cur.random.next; } // 移动到下一个旧节点 cur cur.next.next; } // 分离新旧节点 cur head.next; Node pre head, res head.next; while (cur.next ! null) { // 分离新旧节点 pre.next pre.next.next; cur.next cur.next.next; // 移动到下一个节点 pre pre.next; cur cur.next; } pre.next null; // 单独处理原链表尾节点 // 返回新节点的头节点 return res; }思路简要说明复制节点并拼接把每个新节点都插入到对应旧节点的后面形成旧1 → 新1 → 旧2 → 新2的结构设置 random 指针旧节点的复制节点是cur.next旧节点 random 指向节点的复制节点是cur.random.next拆分新旧链表把拼接在一起的新旧节点拆开恢复旧链表同时得到新链表三、思路详解普通链表复制为什么不难如果链表只有next指针复制其实很简单遍历旧链表每遇到一个旧节点就创建一个值相同的新节点然后把新节点接到新链表后面即可比如旧链表A → B → C 新链表A → B → C只要按顺序复制next关系即可但是这道题多了一个random指针问题就复杂了random 指针带来的问题random指针可以指向链表中的任意节点比如旧链表 next A → B → C random关系 A.random → C B.random → A C.random → B复制后应该是新链表 next A → B → C random关系 A.random → C B.random → A C.random → B注意新链表的 random 必须指向新节点不能指向旧节点这就带来一个问题当我们复制 A’ 的时候如果 A.random 指向 C那么 A’.random 应该指向 C’。可是这时候 C’ 可能还没创建所以无法直接找到。问题就演变成了如何快速找到旧节点 C 对应的新节点 C’如果没有记录新旧节点的对应关系就只能每次从头遍历链表去找这样会非常低效暴力思路每次都遍历查找最直接的做法是先复制一条只有next的新链表设置 random 指针时对于旧链表中的每个 random 指向都从旧链表头开始找它是第几个节点再到新链表中走同样的步数找到对应的新节点并赋值这个方法虽然能做但问题很明显每个节点设置 random 时都可能要遍历一整条链表时间复杂度O(n²)空间复杂度O(1) 或 O(n)取决于是否额外存储链表核心瓶颈没有记录旧节点和新节点之间的对应关系所以每次都要重新查找关键思考能不能提前记录好旧节点 → 新节点的关系这样设置 random 时就能直接拿到对应的新节点方法一哈希表记录新旧节点关系最自然的优化就是使用哈希表哈希表中记录旧节点 A → 新节点 A 旧节点 B → 新节点 B 旧节点 C → 新节点 C这样设置 random 时如果旧节点cur.random指向 C那么新节点的 random 就应该指向map.get(C)也就是 C’实现步骤第一遍遍历旧链表创建所有新节点并用哈希表记录新旧节点关系第二遍遍历旧链表根据哈希表补全新节点的next和randomJava 实现代码如下public Node copyRandomList(Node head) { if (head null) return null; MapNode, Node map new HashMap(); Node cur head; // 第一遍复制所有节点并记录旧节点和新节点的映射关系 while (cur ! null) { map.put(cur, new Node(cur.val)); cur cur.next; } // 第二遍补全新节点的next和random指针 cur head; while (cur ! null) { Node newNode map.get(cur); newNode.next map.get(cur.next); newNode.random map.get(cur.random); cur cur.next; } return map.get(head); }为什么map.get(null)没问题在 Java 的HashMap中map.get(null)会返回 null。所以当cur.next null或cur.random null时直接赋值为 null逻辑刚好正确这个方法非常清晰但需要额外的哈希表时间复杂度O(n)空间复杂度O(n)如果想继续优化空间就需要想办法不用哈希表也能维护新旧节点的对应关系方法二拼接 拆分哈希表的作用是记录旧节点和新节点之间的对应关系那有没有办法不用哈希表也能快速找到某个旧节点对应的新节点答案是把新节点直接插到旧节点后面比如原链表是A → B → C复制并拼接后变成A → A → B → B → C → C这样就天然建立了对应关系旧节点 A 的复制节点就是 A.next 旧节点 B 的复制节点就是 B.next 旧节点 C 的复制节点就是 C.next这就相当于把哈希表的信息直接塞进链表结构里了第一步拼接新节点遍历旧链表每遇到一个旧节点cur就创建一个新节点newNode然后把它插到cur后面Node newNode new Node(cur.val); newNode.next cur.next; cur.next newNode; cur newNode.next;图示原链表 A → B → C 处理 A 后 A → A → B → C 处理 B 后 A → A → B → B → C 处理 C 后 A → A → B → B → C → C这一步完成后每个旧节点的下一个节点就是它对应的新节点第二步处理 random 指针拼接完成后random 指针就很好处理了如果当前旧节点是curcur.next是当前旧节点对应的新节点cur.random是旧节点 random 指向的旧节点cur.random.next就是这个 random 目标节点对应的新节点所以cur.next.random cur.random.next;图示理解旧链表关系 A.random → C 拼接后 A → A → B → B → C → C |___________________↑ A.random 指向 C 因为 C 的复制节点就在 C 后面所以 A.random A.random.next C也就是cur.next.random cur.random.next ↑ ↑ A C如果cur.random null说明当前节点没有 random 指向直接跳过即可第三步拆分新旧链表拼接后的链表是A → A → B → B → C → C我们需要拆成两条链表旧链表A → B → C 新链表A → B → C代码中cur head.next; Node pre head, res head.next; while (cur.next ! null) { pre.next pre.next.next; cur.next cur.next.next; pre pre.next; cur cur.next; } pre.next null; return res;这里的指针含义是pre旧链表当前节点cur新链表当前节点res新链表头节点也就是head.next为什么res head.next因为拼接完成后原头节点head后面紧跟的就是复制出来的新头节点所以新链表的头节点就是head.next拆分过程图示初始pre ↓ A → A → B → B → C → C ↑ cur res A第一轮pre.next pre.next.next; // A.next B恢复旧链表连接 cur.next cur.next.next; // A.next B连接新链表变成旧链表A → B → B → C → C 新链表A → B → C → C然后移动pre pre.next; // pre B cur cur.next; // cur B第二轮继续拆分直到新链表最后一个节点最后需要pre.next null;这是为了恢复旧链表尾节点的next。否则旧链表尾节点可能还指向最后一个复制节点最终得到旧链表A → B → C 新链表A → B → C时间复杂度O(n)三次遍历链表空间复杂度O(1)没有使用哈希表只使用几个指针变量四、总结这道题的核心不是普通的链表复制而是如何处理random指针关键点是必须建立旧节点和新节点之间的对应关系哈希表方法显式维护旧节点 → 新节点的映射思路清晰但空间复杂度 O(n)拼接拆分方法把新节点插到旧节点后面利用链表结构隐式维护映射空间复杂度 O(1)拼接法最巧妙的地方就在于旧节点的复制节点就是旧节点的 next旧节点 random 指向节点的复制节点就是 random.next