138. 随机链表的复制

题目链接：https://leetcode.cn/problems/copy-list-with-random-pointer/

代码

/**
 * Definition for _Node.
 * class _Node {
 *     val: number
 *     next: _Node | null
 *     random: _Node | null
 *
 *     constructor(val?: number, next?: _Node, random?: _Node) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *         this.random = (random===undefined ? null : random)
 *     }
 * }
 */

class _Node {
    val: number
    next: _Node | null
    random: _Node | null

    constructor(val?: number, next?: _Node, random?: _Node) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
        this.random = (random === undefined ? null : random)
    }
}


function copyRandomList(head: _Node | null): _Node | null {
    let now = head;
    const map = new Map<_Node, _Node>();
    while(now){
        let node = new _Node(now.val);
        map.set(now, node);
        now = now.next;
    }
    now = head;
    while(now){
        map.get(now).next = map.get(now.next) ?? null;
        map.get(now).random = map.get(now.random) ?? null;
        now = now.next;
    }
    return map.get(head);
};

思路

使用哈希表建立原节点和新节点的映射关系：

第一次遍历：创建所有新节点

1. 遍历原链表，为每个节点创建对应的新节点
2. 将原节点和新节点的映射关系存入 Map
3. 此时新节点只有 val，next 和 random 都未设置

第二次遍历：建立指针关系

1. 再次遍历原链表
2. 通过 Map 找到当前节点对应的新节点
3. 设置新节点的 next 和 random 指针：
   • map.get(now).next = map.get(now.next) ?? null
   • map.get(now).random = map.get(now.random) ?? null
4. 使用 ?? 运算符处理 null 的情况

关键点

• 使用哈希表存储原节点到新节点的映射

• 分两次遍历：第一次创建节点，第二次建立关系

• 避免了复杂的指针操作，思路清晰

• 时间复杂度 $O(n)$，其中 $n$ 是链表的长度

• 空间复杂度 $O(n)$，哈希表存储所有节点