-
Notifications
You must be signed in to change notification settings - Fork 277
/
Copy pathCopyListwithRandomPointer.java
68 lines (55 loc) · 1.29 KB
/
CopyListwithRandomPointer.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
65
66
67
68
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
// TC : O(n)
// SC : O(n)
public Node copyRandomList(Node head) {
if(head == null){
return null;
}
// duplicate nodes
Node it = head;
while(it!=null){
Node nextIt = it.next;
Node newNode = new Node(it.val);
newNode.next = it.next;
it.next = newNode;
it = nextIt;
}
// set random pointer
Node newIt = head.next;
Node newHead = head.next;
it = head;
while(it!=null){
if(it.random!=null) {
newIt.random = it.random.next;
}
it = newIt.next;
if(it!=null)
newIt = it.next;
}
// Reseting the next nodes so as to separte old and duplicate lists
it = head;
newIt = head.next;
while(it!=null){
it.next = newIt.next;
it = it.next;
if(it!=null){
newIt.next = it.next;
newIt = it.next;
}
}
return newHead;
}
}