# 138.Copy-List-with-Random-Pointer

## ้ข็ฎๅฐๅ

https://www.lintcode.com/problem/copy-list-with-random-pointer/

https://leetcode.com/problems/copy-list-with-random-pointer/

## ้ข็ฎๆ่ฟฐ

``````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.``````

## ไปฃ็ 

### Approach #1 Recursive

Complexity Analysis

• Time Complexity: O(N)

• Space Complexity: O(N)

``````class Node {
public int val;
public Node next;
public Node random;

public Node() {}
public Node(int _val, Node _next, Node _random) {
val = _val;
next = _next;
random = _random;
}
}

class Solution {
HashMap<Node, Node> visitedHash = new HashMap<Node, Node>();

if (head == null) return null;

}

Node node = new Node(head.val, null, null);

return node;
}
}``````

### Approach #2 Iterative with O(N) Space

``````class Solution {
HashMap<Node, Node> visited = new HashMap<Node, Node>();
public Node getClonedNode(Node node) {
if (node != null) {
if (this.visited.containsKey(node)) {
return this.visited.get(node);
} else {
this.visited.put(node, new Node(node.val, null, null));
return this.visited.get(node);
}
}
return null;
}

if (head == null) return null;

Node newNode = new Node(oldNode.val);
this.visited.put(oldNode, newNode);

while (oldNode != null) {
newNode.random = this.getCloneNode(oldNode.random);
newNode.next = this.getClonedNode(oldNode.next);

oldNode = oldNode.next;
newNode = newNode.next;
}

}
}``````
``````class RandomListNode {
int val;
}

public class Solution {
if (head == null) return null;

RandomListNode dummy = new RandomListNode(0);
RandomListNode curNode = dummy;
HashMap<RandomListNode, RandomListNode> randomMap =
new HashMap<RandomListNode, RandomListNode>();
curNode.next = newNode;

curNode = curNode.next;
}

curNode = dummy.next;
while (curNode != null) {
if (curNode.random != null) {
curNode.random = randomMap.get(curNode.random);
}
curNode = curNode.next;
}

return dummy.next;
}
}``````

// Solution 2:

``````public class Solution {
RandomListNode dummy = new RandomListNode(0);
RandomListNode curNode = dummy;
HashMap<RandomListNode, RandomListNode> hash_map =
new HashMap<RandomListNode, RandomListNode>();
RandomListNode newNode = null;
} else {
}
curNode.next = newNode;

} else {