Copy List with Random Pointer LeetCode solution in Java

1
class Solution {
2
  public Node copyRandomList(Node head) {
3

4
    if (head == null) return null;
5

6
    HashMap<Node, Node> map = new HashMap<>();
7

8
    // node to be returned
9
    Node ans = new Node(head.val);
10

11
    // temproary pointer to the ans node
12
    Node tempAns = ans;
13

14
    Node temp = head;
15

16
    map.put(head, ans);
17
    temp = temp.next;
18

19
    // loop to store the lookalike new nodes of the original ones
20
    // create the new list side by side
21
    while (temp != null) {
22
      Node x = new Node(temp.val);
23
      map.put(temp, x);
24
      tempAns.next = x;
25
      tempAns = x;
26
      temp = temp.next;
27
    }
28

29
    // repointing them to the start
30
    temp = head;
31
    tempAns = ans;
32

33
    // will have lookup of O(1) for the random nodes;
34
    while (temp != null) {
35
      tempAns.random = map.get(temp.random);
36
      tempAns = tempAns.next;
37
      temp = temp.next;
38
    }
39

40
    return ans;
41
  }
42
}