138. 隨機鏈表的複製

給你一個長度為 n 的鏈表，每個節點包含一個額外增加的隨機指針 random ，該指針可以指向鏈表中的任何節點或空節點。

構造這個鏈表的 深拷貝。 深拷貝應該正好由 n 個 全新 節點組成，其中每個新節點的值都設為其對應的原節點的值。新節點的 next 指針和 random 指針也都應指向複製鏈表中的新節點，並使原鏈表和複製鏈表中的這些指針能夠表示相同的鏈表狀態。複製鏈表中的指針都不應指向原鏈表中的節點 。

例如，如果原鏈表中有 X 和 Y 兩個節點，其中 X.random --> Y 。那麼在複製鏈表中對應的兩個節點 x 和 y ，同樣有 x.random --> y 。

返回複製鏈表的頭節點。

用一個由 n 個節點組成的鏈表來表示輸入/輸出中的鏈表。每個節點用一個 [val, random_index] 表示：

  • val：一個表示 Node.val 的整數。
  • random_index：隨機指針指向的節點索引（範圍從 0 到 n-1）；如果不指向任何節點，則為  null 。

你的代碼 只 接受原鏈表的頭節點 head 作為傳入參數。

 

示例 1：

138. 隨機鏈表的複製_深拷貝

輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

138. 隨機鏈表的複製_深拷貝_02

輸入：head = [[1,1],[2,1]]
輸出：[[1,1],[2,1]]

示例 3：

138. 隨機鏈表的複製_深拷貝_03

輸入：head = [[3,null],[3,0],[3,null]]
輸出：[[3,null],[3,0],[3,null]]

 

提示：

  • 0 <= n <= 1000
  • -104 <= Node.val <= 104
  • Node.random 為 null 或指向鏈表中的節點。

 

class Solution {
    Map<Node, Node> cachedNode = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        if (!cachedNode.containsKey(head)) {
            Node headNew = new Node(head.val);
            cachedNode.put(head, headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
        return cachedNode.get(head);
    }
}