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.

 

1 /** 2  * Definition for singly-linked list with a random pointer. 3  * public class RandomListNode { 4  *     public int label; 5  *     public RandomListNode next, random; 6  *     public RandomListNode(int x) { this.label = x; } 7  * }; 8  */ 9 public class Solution {10     public RandomListNode CopyRandomList(RandomListNode head) {11         if (head == null) return null;12         13         RandomListNode newHead = new RandomListNode(head.label), cur = head, newCur = newHead;14         15         var dict = new Dictionary
     
      ();16         dict[head] = newHead;17         18         while (cur.next != null)19         {20             var n = new RandomListNode(cur.next.label);21             dict[cur.next] = n;22             newCur.next = n;23             cur = cur.next;24             newCur = newCur.next;25         }26         27         cur = head;28         newCur = newHead;29         30         while (cur != null)31         {32             if (cur.random != null && dict.ContainsKey(cur.random))33             {34                 newCur.random = dict[cur.random];35             }36             37             cur = cur.next;38             newCur = newCur.next;39         }40         41         return newHead;42     }43 }