The problem belongs to LeetCode, here is the link to the problem

Following code segment contains the description in the class comments, followed by fully working solution (faster than 100% of the java submissions), then a brief detail about the solution afterwards

/**
 * Construct a deep copy of a given linked list and return its head.
 * What's more is - there is a random pointer in every node which may point to any node or can be null as well.
 * The new linked list created should not point to any nodes from original linked list.
 *
 */
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class CopyListRandomPointer {

 // my solution faster than 100% :)
    public Node copyRandomList(Node head) {
        Node h1 = head;
        Node h2 = null;
        Node head2 = null;
        Node prev = null;
        Map map=new HashMap<>();
        while (h1 != null) {
            h2 = new Node(h1.val);
            if (head2 == null) {
                head2 = h2;
            }
            if (prev != null) {
                prev.next = h2;
            }
            map.put(h1, h2);
            h1 = h1.next;
            prev = h2;
        }
        Node p1 = head;
        Node p2 = head2;
        while (p1 != null) {
            Node r1 = p1.random;
            p2.random=map.get(r1);
            p1 = p1.next;
            p2 = p2.next;
        }

        return head2;
    }

}

The complexity here is O(N). The solution is faster than 100% of the java submissions as per leetcode evaluation.

The idea is to first iterate over the given linked list and create a new linked list with only the next pointers but at the same time making a map of current node to the random node. In the next iteration we iterate over the linked list and get the random node from the map and connect it in the new linked list.