> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/linked-list/12.copy-list-with-random-pointer.md).

# 15.Copy List with Random Pointer

Return a **deep copy** of the list.

![Example ](/files/-MHqDAUkX3t6mFWxkdtk)

```
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
```

## Solution I :(Using Extra Space)

**Algorithm:**\
1\. Create all nodes in **copy linked list** using next pointers.\
2\. **Store** the **next pointer mappings of original linked list**.\
4\. Make the **random pointer of copy linked list point to original Linked List.**\
5\. Make the **Next pointer of the original Linked List point to copy linked list.**\
6\. **Set the random pointer of copy linked list to original values using** \
                 **node->random = node->random->random->next**\
7.Change **next pointer of all nodes in original linked list** to point to the corresponding node in linked list.

![](/files/-MHqGrDJStfmBFODEQRw)

```cpp
class Solution
{
public:
    Node *copyRandomList(Node *head)
    {
        
        if(head == NULL){return NULL;}

        vector<Node *> v;

        Node *head1 = NULL;
        Node *p = head;
        Node *q = NULL;
        Node *t = NULL;

        // Creating a copy of original ll
        while (p != NULL)
        {
            Node *temp = new Node(p->val);
            if (head1 == NULL)
            {
                head1 = temp;
                t = head1;
            }
            else
            {
                t->next = temp;
                t = t->next;
            }
            p = p->next;
            // Store the original address
            v.push_back(p);
        }

        //changing random pointer
        p = head;
        t = head1;
        while (p != NULL)
        {
            t->random = p;
            p = p->next;
            t = t->next;
        }

        //changing next pointer
        p = head;
        q = head;
        t = head1;
        while (p != NULL)
        {
            p = p->next;
            q->next = t;
            q = p;
            t = t->next;
        }

        //assigning random pointer its correct value
        t = head1;
        while (t != NULL)
        {
            if (t->random->random != NULL)
            {
                t->random = t->random->random->next;
            }
            else
            {
                t->random = NULL;
            }

            t = t->next;
        }

         // Restore the original next pointer
        p = head;
        for (int i = 0; i < v.size(); i++)
        {
            p->next = v[i];
            p = p->next;
        }

        return head1;
    }
};
```

**Time Complexity: O(n) , Space Complexity: O(n)**

## Solution II: (Using Constant Space)

**Algorithm :**

* Create the copy of node 1 and insert it between node 1 & node 2 in original Linked List, create a copy of 2 and insert it between 2 & 3. Continue in this fashion, add the copy of N after the Nth nod&#x65;**.**

![](/files/-MHyNUZGu9-nT8j5-bLz)

* Now copy the random link:

```
 original->next->random= original->random->next
```

![](/files/-MHyNosVXBJlunUfYsjH)

* Now restore the original and copy linked lists in this fashion in a single loop.

```
original->next = original->next->next; 
copy->next = copy->next->next;
```

![](/files/-MHyOIcXlBbSmhnKnAnk)

```cpp
class Solution
{
public:
    Node *copyRandomList(Node *head)
    {

        if (head == NULL)
        {
            return head;
        }

        Node *p = head;
        Node *q = head;

        //Inserting a copy in between original values
        while (p != NULL)
        {
            q = p->next;
            Node *temp = new Node(p->val);
            p->next = temp;
            temp->next = q;
            p = q;
        }

        //Copying the random pointers
        p = head;
        while (p)
        {
            if (p->random)
            {
                p->next->random = p->random->next;
            }
            else
            {
                p->next->random = NULL;
            }

            if (p->next)
            {
                p = p->next->next;
            }
            else
            {
                p = p->next;
            }
        }

        //Separting original and random pointers
        Node *orgi = head;
        Node *copy = head->next;
        Node *temp = copy;

        while (orgi && copy)
        {
            if (orgi->next)
            {
                orgi->next = orgi->next->next;
            }
            else
            {
                orgi->next = NULL;
            }

            if (copy->next)
            {
                copy->next = copy->next->next;
            }
            else
            {
                copy->next = NULL;
            }

            orgi = orgi->next;
            copy = copy->next;
        }

        return temp;
    }
};
```

**Time Complexity: O(n)**