
### Problem Statement

###### A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

###### Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

###### For example, if there are two nodes X and Y in the original list, where X.random &rarr; Y, then for the corresponding two nodes x and y in the copied list, x.random &rarr; y.

###### Return the head of the copied linked list.

###### The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

- ###### val: an integer representing Node.val

- ###### random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

###### Your code will only be given the head of the original linked list.

![Copy Linked List](https://assets.leetcode.com/uploads/2019/12/18/e1.png)

**INPUT**

- **[[7,null],[13,0],[11,4],[10,2],[1,0]]**

**OUTPUT**

- **[[7,null],[13,0],[11,4],[10,2],[1,0]]**

**Steps To Solve**

- According to problem statement we have a linked list with a random pointer which points to any element in the list.
- Now we have to construct deep copy of the linked list.
  ![Deep vs Shalow](https://res.cloudinary.com/practicaldev/image/fetch/s--CjdqwIq1--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://dev-to-uploads.s3.amazonaws.com/i/llosmmb3rzbq5ravmfcp.jpg)
- We are going to solve this problem without any extra space.
- So lets first copy the elements into another linked list and keep aside the thought of handling random pointers for now.
- As we dont have any extra space to play with,so we create the new node and attach them one by one after the original node ,in this linked list itself.
- For this we will take a current pointer and forward pointer. Lets say current pointer is at 1st node (7,null) and forward pointer is at (13,0).
- Now we will create a new node with value of current pointer and attach in between the 1st and 2nd node.
- Then we will repeat the process with the other node as well by moving both current and forward pointers to next nodes.
- Our new constructtion will look something like this : 7&rarr;7&rarr;13&rarr;13&rarr;11&rarr;11&rarr;10&rarr;10&rarr;1&rarr;1&rarr;null
- Here every next alternative node is the newly constructed node and remember that these node does not have random pointers yet.
- Next we will worry about how to populate random pointers to these alternative nodes.
- We can see that the node with value 11 points to node at position 4 with value 1.
- So now can we say that the newly constructed node 11 which is next to the original node 11 , will point to the newly constructed node at position 4 with value 1, which we know is placed next to the original node at position 4 with value 1.
- Algorithm wise :

```js
const random = curr.random; // curr and random are original node
curr.next.random = random.next; // curr.next and random.next is newly constructed node
```

- Now we will run our extraction process to seperate the constructed node.
- For that we create a dummy node.
- Then create a pointer prev and point it to dummy and its next as head.
- After that we will create a pointer curr and point it to head.
- We will then attach dummy to newly constructed node by doing **prev.next = curr.next** as curr.next is not the original node but its newly constructed node.
- Then we will break the link of the original node with the newly constructed node by doing **curr.next = curr.next.next**.
- The first original node element will now point to 2nd original node element as it was before and the constructed node which was created by us can be referenced by the dummy pointer.
- Repeat the process by moving our prev and curr pointer forward till we reach the end.
- Return the dummy node's next pointer as head of the newly constructed node chain.
- Lets Jump to solution !!!

```js
/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function (head) {
  copyList(head);
  copyRandomPointer(head);

  return extract(head);
};

function extract(head) {
  const dummy = new Node(-1, head, null);
  let prev = dummy,
    curr = head;

  while (curr !== null) {
    prev.next = curr.next;
    curr.next = curr.next.next;
    prev = prev.next;
    curr = curr.next;
  }

  return dummy.next;
}

function copyList(head) {
  let curr = head;
  while (curr !== null) {
    const fwd = curr.next;

    const node = new Node(curr.val, fwd, null);
    curr.next = node;

    curr = fwd;
  }
}

function copyRandomPointer(head) {
  let curr = head;
  while (curr !== null) {
    let random = curr.random;
    if (random !== null) {
      curr.next.random = random.next;
    }
    curr = curr.next.next;
  }
}
```

###### Time and Space Complexity

Time Complexity is **O(N)**.
Space complexity is **O(1)**.
