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
Given list
1 -> 2 -> 3
with random pointers going from
1 -> 3
2 -> 1
3 -> 1
You should return a deep copy of the list. The returned answer should not contain the same node as the original list, but a copy of them. The pointers in the returned list should not link to any node in the original input list.
Solution:
Time: O(n) Space: O(n)
/** * Definition for singly-linked list with a random pointer. * class RandomListNode { * int label; * RandomListNode next, random; * RandomListNode(int x) { this.label = x; } * }; */ public class Solution { public RandomListNode copyRandomList(RandomListNode head) { Map<RandomListNode, RandomListNode> map = new HashMap<>(); RandomListNode p = head; RandomListNode dummy = new RandomListNode(0); RandomListNode n = dummy; while (p != null) { RandomListNode r = map.getOrDefault(p, new RandomListNode(p.label)); map.put(p, r); if (p.random != null) { r.random = map.getOrDefault(p.random, new RandomListNode(p.random.label)); map.put(p.random, r.random); } n.next = r; n = n.next; p = p.next; } return dummy.next; } }