LeetCode Copy List with Random Pointer：哈希表 / 原地拆分雙法深拷貝

問題描述

鏈表節點含 next 和 random 指針。深拷貝返回新鏈表頭。

方法一：哈希表映射舊→新節點

1. 第一遍：遍歷舊鏈表，創建新節點，map[old] = new
2. 第二遍：遍歷舊鏈表，設置 new.next = map[old.next]，new.random = map[old.random]

Node copyRandomList(Node head) {
    if (!head) return null;
    Map map = new HashMap<>();
    for (Node p=head; p!=null; p=p.next) map.put(p, new Node(p.val));
    for (Node p=head; p!=null; p=p.next) {
        Node q = map.get(p);
        q.next = map.get(p.next);
        q.random = map.get(p.random);
    }
    return map.get(head);
}

方法二：原地拆分 O(1) 空間（不算輸出）

1. 在每個舊節點後插入其拷貝：A → A' → B → B' → ...
2. 設置拷貝節點 random：A'.random = A.random ? A.random.next : null
3. 拆分鏈表：恢復舊鏈表，提取新鏈表

Node copyRandomList(Node head) {
    if (!head) return null;
    // 1. 複製節點插入原鏈表
    for (Node p=head; p!=null; p=p.next.next) {
        Node copy = new Node(p.val);
        copy.next = p.next;
        p.next = copy;
    }
    // 2. 設置 random
    for (Node p=head; p!=null; p=p.next.next)
        if (p.random != null) p.next.random = p.random.next;
    // 3. 拆分
    Node newHead = head.next;
    for (Node p=head; p!=null; p=p.next) {
        Node copy = p.next;
        p.next = copy.next;
        copy.next = (copy.next != null) ? copy.next.next : null;
    }
    return newHead;
}

複雜度