# Copy List with Random Pointer

ID: 105; medium; 复制带随机指针的链表

## Solution 1 (Java)

``````/**
* 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 {
/**
* @return: A new head of a deep copy of the list.
*/
if (head == null) return null;

RandomListNode dummy = new RandomListNode(0);
RandomListNode prev = dummy, newNode;
HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();

// deal with the core nodes
} else {
}
prev.next = newNode;

// deal with random pointers of the core nodes
} else {
}
}
prev = newNode;
}

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

### Notes

• This solution uses a HashMap to keep track of the original nodes and their duplicates.

• For each iteration, we first deal with the node itself. If it is not in the HashMap, we add it to the `map` where the key is itself and the value is its duplicate. If it is in the `map`, the next node for the deep copy is its value, i.e., the duplicate in the map. Next, we deal with the random pointers of the node. Using a similar approach, we point the random pointer of the node in the deep copy to a duplicate.

• Do not forget to update `prev` and `head`. Here, `prev` is for constructing the new deep copy and `head` is just for traversing the original linked list.

• Time complexity is `O(n)` and space complexity is also `O(n)`.

## Solution 2 (Java)

``````/**
* 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 {
/**
* @return: A new head of a deep copy of the list.
*/
if (head == null) return null;
}

RandomListNode newNode = null;
}
}

}
}
}

if (duplicate.next != null) {
duplicate.next = duplicate.next.next;
}
}
}
}``````

### Notes

• This solution uses three pass to copy the original list. Thus, there are three steps:

1. copyNext: This step creates new duplicated nodes and point their next pointers to their originals'.

2. copyRandom: This step simply point the duplicates' random pointers to the corresponding duplicates of their original nodes' random pointers. The key operation here is `head.next.random = head.random.next`. The left is the random pointer of the duplicate and the right is the duplicate of the original random node.

3. splitLists: We cut the connections between the original list and the new deep copy. Be careful with null checking in the loop to prevent `NullPointerException`.

• The time complexity is still `O(n)`, but the space complexity now is `O(1)`.

Last updated