LC138 Copy list with Random Pointer

说到random就应该想到HashMap

因为每个节点都有一个random pointer,这个pointer可以指向null或者链表中任意一个节点; 如果新链表中每个节点的random pointer赋值时，都要去遍历整个链表那么肯定TLE; 所以应该考虑用HashMap缩短查找时间为O(1); 第一遍遍历生成所有节点的过程中建立一个原来所有节点和新节点的HashMap, 第二遍给node赋值next指针好说，赋值random pointer的时候，根据原来的节点的random pointer赋值查找时间也是O(1).

public RandomListNode copyRandomList(RandomListNode head) {
  if (head == null) return null;
  
  Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
  
  // loop 1. copy all the nodes
  RandomListNode node = head;
  while (node != null) {
    map.put(node, new RandomListNode(node.val));
    node = node.next;
  }
  
  // loop 2. assign next and random pointers
  node = head;
  while (node != null) {
    map.get(node).next = map.get(node.next);
    map.get(node).random = map.get(node.random);
    node = node.next;
  }
  
  return map.get(head);
}

Achtung hier:

map.get(node).next: 得到当前key的节点的next指针指向的节点, map中V对应的新创建的节点的next指针就应该指向这个节点

map.get(node).random同理，指向的是当前key的节点的random指针指向的节点