-
Notifications
You must be signed in to change notification settings - Fork 2
/
CopyListWithRandomPointer.java
56 lines (48 loc) · 1.2 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
package com.algorithm.playground.leetcode.problems.lc100.lc130.lc138;
import com.algorithm.playground.leetcode.problems.utils.linkedlist.Node;
import java.util.HashMap;
import java.util.Map;
/**
* https://leetcode.com/problems/copy-list-with-random-pointer/
* <p>
* 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.
* <p>
* Return a deep copy of the list.
*/
public class CopyListWithRandomPointer {
/**
* // Definition for a Node.
* class Node {
* public int val;
* public Node next;
* public Node random;
* <p>
* public Node() {}
* <p>
* public Node(int _val,Node _next,Node _random) {
* val = _val;
* next = _next;
* random = _random;
* }
* };
*/
class Solution {
public Node copyRandomList(Node head) {
return copy(head, new HashMap<>());
}
private Node copy(Node node, Map<Node, Node> copies) {
if (node == null) {
return null;
} else if (copies.containsKey(node)) {
return copies.get(node);
}
Node n = new Node();
n.val = node.val;
copies.put(node, n);
n.next = copy(node.next, copies);
n.random = copy(node.random, copies);
return n;
}
}
}