## Problem statement

Given a linked list with next and arbitrary pointer, clone the given linked list.

Given linked list will be something like below figure.Linked list with arbitrary pointer |

## Analysis

This problem can be solved using extra N spaces where we store the next and arbitrary pointer mapping of the given linked list. However, challenge is to do it in O(1) space complexity.

Idea here is to add a node between each two nodes of original list which will eventually become node in clone linked list. For example, in above list, a new node will be added between 1 and 2 with value 1, between 2 and 3 with value as 2 and so on.

After this step linked list looks like

After adding nodes in between |

**Code for above step**

Now we can access the clone node with

and arbitrary pointer of clone node can be set as

**Code for above step**

Last step will be to segregate two linked list.

**Code for above step**

## Code

## Complexity Analysis

Time complexity of above code is O(N) and space complexity is O(1).