复制带随机指针的链表

题目描述：给你一个长度为 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：

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

示例 2：

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

示例 3：

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

示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

方法一：哈希迭代

使用map存放所有的节点
遍历map给每个节点指向 next和random节点

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
  public Node copyRandomList(Node head) {
    if(head == null) return null;
    Map<Node, Node> map = new HashMap<>();
    Node cur = head;
    while(cur != null) {
      map.put(cur, new Node(cur.val));
      cur = cur.next;
    }

    cur = head;
    while(cur != null) {
      map.get(cur).next = map.get(cur.next);
      map.get(cur).random = map.get(cur.random);
      cur = cur.next;
    }
    return map.getOrDefault(head, null);
  }
}

复杂度分析

时间复杂度：O(N)。因为我们需要将原链表逐一遍历。
空间复杂度：O(N) 。我们需要维护一个字典，保存旧的节点和新的节点的对应。因此总共需要 N 个节点，需要 O(N) 的空间复杂度。

执行结果：通过

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.4 MB, 在所有 Java 提交中击败了27.03%的用户

方法二：哈希递归

哈希表Mydic映射原有节点->新的节点
原节点为空，则返回空
原节点在哈希表中可以找到，则说明新的节点已生成，直接返回
根据原有节点的值，创建新的节点root = Node(node.val)
将原有节点和新节点的对应关系添加到哈希表中Mydic[node] = root
最后参照原节点的next和random关系，创建新的next和random节点给新节点root
递归整个过程

class Solution {
    private HashMap<Node, Node> MyMap = new HashMap<>();
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        if (MyMap.containsKey(head)) return MyMap.get(head);
        Node root = new Node(head.val);
        MyMap.put(head, root);
        root.next = copyRandomList(head.next);
        root.random = copyRandomList(head.random);
        return root;
    }
}

复杂度分析

时间复杂度：O(N)，其中 NN 是链表中节点的数目。
空间复杂度：O(N)。如果我们仔细分析，我们需要维护一个回溯的栈，同时也需要记录已经被深拷贝过的节点，也就是维护一个已访问字典。渐进时间复杂度为 O(N) 。

执行结果：通过

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.5 MB, 在所有 Java 提交中击败了7.86%的用户

方法三：O(1) 空间的迭代

class Solution {
  public Node copyRandomList(Node head) {
    if(head==null) {
      return null;
    }
    //第一步，在每个原节点后面创建一个新节点
    //1->1'->2->2'->3->3'
    Node p = head;
    while(p!=null) {
      Node newNode = new Node(p.val);
      newNode.next = p.next;
      p.next = newNode;
      p = newNode.next;
    }
    
    //第二步，设置新节点的随机节点
    p = head;
    while(p!=null) {
      if(p.random!=null) {
        p.next.random = p.random.next;
      }
      p = p.next.next;
    }
    
    //第三步，将两个链表分离
    Node dummy = new Node(-1);
    Node cur = dummy;
    p = head;
    while(p!=null) {
      cur.next = p.next;
      cur = cur.next;
      p.next = cur.next;
      p = p.next;
    }
    return dummy.next;
  }
}

复杂度分析

时间复杂度：O(N)
空间复杂度：O(1)

执行结果：通过

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：37.8 MB, 在所有 Java 提交中击败了85.29%的用户

方法一：哈希 迭代

方法二：哈希 递归

方法三：O(1) 空间的迭代

方法一：哈希迭代

方法二：哈希递归