-
Notifications
You must be signed in to change notification settings - Fork 0
/
Question16.java
64 lines (54 loc) · 1.38 KB
/
Question16.java
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
54
55
56
57
58
59
60
61
62
63
64
//Clone a linked list with the random points
public class Question16 {
class Node {
int data;
Node next;
Node random;
Node() {
this.data = 0;
this.next = null;
this.random = null;
}
Node(int data) {
this.data = data;
this.next = null;
this.random = null;
}
Node(int data, Node nextNode, Node randomNode) {
this.data = data;
this.next = nextNode;
this.random = randomNode;
}
}
public Node copyRandomList(Node head) {
Node temp = head;
// step 1
while (temp != null) {
Node newNode = new Node(temp.data);
newNode.next = temp.next;
temp.next = newNode;
temp = temp.next.next;
}
// step 2
Node itr = head;
while (itr != null) {
if (itr.random != null) {
itr.next.random = itr.random.next;
}
itr = itr.next.next;
}
// step 3
Node dummy = new Node(0);
itr = head;
temp = dummy;
Node fast;
while (itr != null) {
fast = itr.next.next;
temp.next = itr.next;
itr.next = fast;
temp = temp.next;
itr = fast;
}
return dummy.next;
}
}