> For the complete documentation index, see [llms.txt](https://bhabs.gitbook.io/prepbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://bhabs.gitbook.io/prepbook/coding/deep-copy-list-with-random-node.md).

# Deep copy list with random node

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.

Note: Strategy is to do in O(n) time and use a hash to keep a node reference - O(n) space. The hash/dict has key as the original node and the value as the copy node. Later traverse the copied list and re-associate the random pointers by doing a hash lookup

```
# Definition for singly-linked list with a random pointer.
'''
class RandomListNode(object):
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None
'''

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        #if not head:
            #return None

        nodeRefDict = {}

        ptr = head
        copyNodePrev = None
        copyNodeHead = None

        while ptr:
            #print 'ptr.label = ', ptr.label, ' ptr.random: ', ptr.random
            # create a copy of the node
            copyNode = RandomListNode(ptr.label)
            copyNode.random = ptr.random # keep an account of the original random node. Will replace this later

            # keep chaining the copyNode link list, when the previous node exists
            # so that we get a linked list for the copied nodes in the end
            if copyNodePrev:
                copyNodePrev.next = copyNode

            # nodeRefDict keeps an account between current node and the copy node
            # This will be used to re-associate the random node ptr in a separate iteration
            nodeRefDict[ptr] = copyNode 

            # do the following only 1 time, so that we can return the head of the copyNode list
            # this is just preserving the reference to the head of the copyNode list
            if copyNodeHead is None:
                copyNodeHead = copyNode

            copyNodePrev = copyNode
            ptr = ptr.next

        #////////////////////////////////////////////////////////////////////    
        # Traverse the copyNode list and re-associate the random pointers
        # to the correct copyNode items
        #////////////////////////////////////////////////////////////////////
        ptr = copyNodeHead
        while ptr:
            #print('copy ptr: ', ptr.label, ' copy ptr random: ', ptr.random)
            if ptr.random:
                ptr.random = nodeRefDict[ptr.random]
                #print('  new random: ', ptr.random.label)
            ptr = ptr.next

        return copyNodeHead
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://bhabs.gitbook.io/prepbook/coding/deep-copy-list-with-random-node.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.