I have a singly linked list. Apart from the normal "Next" pointer, there is one more pointer(random ptr) in each node which points to some random node of the list. How to create a clone of such a list? (In less than O(n^2)).

Any suggestion or solution using Java?