Saturday, August 30, 2014

Clone linked list with arbit pointer

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


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


Complexity Analysis

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