leetcode 138 Copy List with Random Pointer
z
 2019-04-09 10:36:27  

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Example 1:

img

1
2
3
4
5
6
Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

  1. You must return the copy of the given head as a reference to the cloned list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

import utils.Node;

import java.util.HashSet;
import java.util.Hashtable;

public class CopyListwithRandomPointer {
  /**
   * Copy List with Random Pointer
   */
  public static Node copyRandomList(Node head) {
    if (head == null) return null;
    Hashtable<Node, Node> m = new Hashtable<>();

    Node p = head;

    // copy all the node, put it to the map
    while (p != null) {
      Node t = new Node();
      t.val = p.val;
      m.put(p, t);
      p = p.next;
    }

    p = head;
    while(p != null) {
      m.get(p).next = m.get(p.next);
      m.get(p).random = m.get(p.random);
      p = p.next;
    }

    return m.get(head);
  }

  public  static  void  main(String[] args) {
//    Node head = new Node();
//    Node t1 = new Node();
//    Node t2 = new Node();
//    head.val=1;
//    t1.val = 2;
//    t2.val = 3;
//    head.next = t1;
//    t1.next = t2;
//    t2.next = null;
//
//    Node r = copyRandomList(head);
//    while(r != null) {
//      System.out.println(r.val);
//      r = r.next;
      System.out.println(((double)94911150/(double)94911151) + " " + ( (double)94911151/(double)94911152));
//    }
  }
}