138. 复制带随机指针的链表

题目链接：138. 复制带随机指针的链表

题目描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。

核心思考：节点拆分与交错拼接

如果使用哈希表存储 原节点 -> 新节点 的映射，可以非常直观地解决问题，但需要 $O(N)$ 的额外空间。本代码采用了一种**无额外空间（除结果集外）**的巧妙算法：节点交错链接法。

1. 第一步：复制并交错插入
   在原链表的每个节点 A 后面直接插入一个复制节点 A'。链表结构变为 A -> A' -> B -> B' -> ...。这一步使得我们可以直接通过 A.next 找到副本，解决定位问题。
2. 第二步：设置随机指针
   遍历交错链表。对于每一个副本节点 A'，它的 random 指针应当指向原节点 A.random 的副本，即 A.next.random = A.random.next（注意空指针判断）。
3. 第三步：拆分链表并还原
   将这个长链表拆分为原链表和新链表。这需要改变 next 指针，将 A -> A' -> B -> B' 恢复为 A -> B 和 A' -> B'。

这种方法的核心价值在于，它利用了链表本身的物理结构作为索引，从而规避了哈希表的开销。

解题思路 (Python)

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        # 1. 构造交错链表: A -> A' -> B -> B'
        cur = head
        while cur:
            copy = Node(cur.val)
            copy.next = cur.next
            cur.next = copy
            cur = copy.next
        
        # 2. 处理 random 指针
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next

        # 3. 将交错链表拆分，并还原原链表
        cur_ori = head
        dummy = Node(0)
        cur_new = dummy
        
        while cur_ori:
            node = cur_ori.next
            # 提取新链表节点
            cur_new.next = node
            cur_new = cur_new.next
            
            # 还原原链表结构
            cur_ori.next = node.next
            cur_ori = cur_ori.next
        
        return dummy.next

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是链表的长度。我们共对链表进行了三次线性扫描。
• 空间复杂度：$O(1)$，如果不考虑存储深拷贝结果所需的节点空间，我们仅使用了常数个指针变量。