3.7 Copy List with Random Pointer

Description

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.

Method

since we need to copy the linkedlist with random pointer, we can split the function into two components, one is copy each node, and another is copy the random pointer, we can stroe the original node with copy node in map(original node, copy one)

Time and Space Complexity

o(n) o(n)

Code

/**

• 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) { 
       if (head == null){
           return null;
       }

       RandomListNode newhead = new RandomListNode(head.label);
       HashMap<RandomListNode,RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
       map.put(head, newhead);
       RandomListNode node = head;
       while (node != null){
              copySingle(node,newhead,map);
              node = node.next;
              newhead = newhead.next;
       }
       return map.get(head);
}

private void copySingle(RandomListNode head, RandomListNode newhead,HashMap<RandomListNode,RandomListNode> map){
         if (head.next != null && map.containsKey(head.next)){
                  newhead.next = map.get(head.next);
              } else {
                  if (head.next != null){
                      RandomListNode copy = new RandomListNode(head.next.label);
                      map.put(head.next, copy);
                      newhead.next =  copy;
                  }
        }

        if (head.random != null && map.containsKey(head.random)){
            newhead.random = map.get(head.random);
        } else {
            if (head.random != null){
                RandomListNode copy = new RandomListNode(head.random.label);
                map.put(head.random, copy);
                newhead.random =  copy;
            }
        }
}

}