# Copy List with Random Pointer

{% embed url="<https://www.lintcode.com/problem/105/>" %}

## Solution 1 (Java)

```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 {
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;

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

        while (head != null) {
            // deal with the core nodes
            if (!map.containsKey(head)) {
                newNode = new RandomListNode(head.label);
                map.put(head, newNode);
            } else {
                newNode = map.get(head);
            }
            prev.next = newNode;

            // deal with random pointers of the core nodes
            if (head.random != null) {
                if (!map.containsKey(head.random)) {
                    newNode.random = new RandomListNode(head.random.label);
                    map.put(head.random, newNode.random);
                } else {
                    newNode.random = map.get(head.random);
                }
            }
            prev = newNode;
            head = head.next;
        }

        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.&#x20;
* Time complexity is `O(n)` and space complexity is also `O(n)`.

### **Scratches**

![](/files/-Mbo69KVjmeNBsmIAhjG)

## Solution 2 (Java)

```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 {
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        copyNext(head);
        copyRandom(head);
        return splitLists(head);
    }

    private void copyNext(RandomListNode head) {
        RandomListNode newNode = null;
        while (head != null) {
            newNode = new RandomListNode(head.label);
            newNode.next = head.next;
            // newNode.random = head.random;
            head.next = newNode;
            head = head.next.next;
        }
    }

    private void copyRandom(RandomListNode head) {
        while (head != null) {
            if (head.random != null) {
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
    }

    private RandomListNode splitLists(RandomListNode head) {
        RandomListNode newHead = head.next;
        while (head != null) {
            RandomListNode duplicate = head.next;
            head.next = head.next.next;
            if (duplicate.next != null) {
                duplicate.next = duplicate.next.next;
            }
            head = head.next;
        }
        return newHead;
    }
}
```

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

### **Scratches**

![](/files/-Mbo6G_E35w0lMdNyn8c)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.yushunchen.com/algo/linked-list/copy-list-with-random-pointer.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.