给定一个由Node节点类型组成的无环单链表的头 节点 head， 请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。

class Node {
  int val;
  Node next;
  Node random;

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

题目描述：rand 指针是单链表节点结构中新增的指针。rand 可能指向链表中的任意一个节点，也可能指向 null。给定一个由 Node 节点类型组成的无环单链表的头 节点 head， 请实现一个西数完成这个链表的复制，并返回复制的新链表的头节点。

要求：时问复杂度 O(N)，额外空问复杂度 O(1)

解法一：哈希表 #

public Node copyRandomList1(Node head) {
  HashMap<Node, Node> map = new HashMap<>();// key 老节点；value 新节点
  Node cur = head;
  while (cur != null) {
    map.put(cur, new Node(cur.val));
    cur = cur.next;
  }
  cur = head;
  while (cur != null) {
    /**
     * cur 老
     * map.get(cur) 新
     * 新.next -> cur.next克隆节点找到
     */
    map.get(cur).next = map.get(cur.next);
    map.get(cur).random = map.get(cur.random);
    cur = cur.next;
  }
  return map.get(head);
}

解法二：Copy 子节点 #

public Node copyRandomList2(Node head) {
  if (head == null) {
    return null;
  }
  Node cur = head;
  Node next = null;
  while (cur != null) {
    next = cur.next;
    cur.next = new Node(cur.val);
    cur.next.next = next;
    cur = next;
  }
  cur = head;
  Node copy = null;
  // 依次设置 1' 2' 3' random指针
  while (cur != null) {
    next = cur.next.next;
    copy = cur.next;
    copy.random = cur.random != null ? cur.random.next : null;
    cur = next;
  }
  Node res = head.next;
  cur = head;

  // 分离新老链表
  while (cur != null) {
    next = cur.next.next;
    copy = cur.next;
    cur.next = next;
    copy.next = next != null ? next.next : null;
    cur = next;
  }
  return res;
}