复制带随机指针的链表

问题陈述

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

要求返回这个链表的 深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

示例：

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

思路分析

浅拷贝与深拷贝

浅拷贝只复制指针的指向，即a和b共用同一个内存空间。深拷贝则开辟了一个新的内存空间用以存储该内容。

代码实现

回溯法

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

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
public solution{
    //HashMap中旧结点存储为键，新结点存储为值。
    HashMap<Node,Node> visitedHash=new HashMap<Node,Node>();
    
    public Node copeRandomList(Node head){
        if(head==null) return null;
        //如果存在当前结点，直接返回它的复制。
        if(this.visitedHash.containsKey(head))  return this.visitedHash.get(head);
        //若不存在，则创建一个新结点。
        Node node=new Node(head.val,null,null);
        //将其放入HashMap
        this.visitedHash.put(head,node);
        //循环下一结点
        node.next=this.copeRandomList(head.next);
        node.random=this.copeRandomList(head.random);
        return node;
    }
}

O(n)空间迭代法

public class solution{
      // Visited dictionary to hold old node reference as "key" and new node reference as the "value"
  HashMap<Node, Node> visited = new HashMap<Node, Node>();
//获取复制结点
  public Node getClonedNode(Node node) {
    // If the node exists then
    if (node != null) {
      // Check if the node is in the visited dictionary
      if (this.visited.containsKey(node)) {
        // If its in the visited dictionary then return the new node reference from the dictionary
        return this.visited.get(node);
      } else {
        // Otherwise create a new node, add to the dictionary and return it
        this.visited.put(node, new Node(node.val, null, null));
        return this.visited.get(node);
      }
    }
    return null;
  }
//复制带有random指针的链表。
  public Node copyRandomList(Node head) {

    if (head == null) {
      return null;
    }

    Node oldNode = head;

    // Creating the new head node.
    Node newNode = new Node(oldNode.val);
    this.visited.put(oldNode, newNode);

    // Iterate on the linked list until all nodes are cloned.
    while (oldNode != null) {
      // Get the clones of the nodes referenced by random and next pointers.
      newNode.random = this.getClonedNode(oldNode.random);
      newNode.next = this.getClonedNode(oldNode.next);

      // Move one step ahead in the linked list.
      oldNode = oldNode.next;
      newNode = newNode.next;
    }
    return this.visited.get(head);
  }
}