/**
1. 这个题的难点是怎么确定random指针指向的位置?
    1.1 可以先将非随机指针部分深拷贝出来, 然后同时遍历2个链表, 找到对应的随机指针, 时间复杂度O(n^2), 空间复杂度的O(1)
    1.2 可以每次缓存生成的节点, 然后再次访问到的话使用缓存的节点, 需要用Map 记录,  时间复杂度O(n), 空间复杂度的O(n)
    1.3 可以先使用next节点生成新节点, 并将oldNode.next = newNode, newNode.next =  oldNextNode, 即插入到原链表中, 这样每次就能确定random指向的位置必定为 oldNode.next,  时间复杂度O(n), 空间复杂度的O(1)
*/

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        // return scan(head);
        // return cache(head, new HashMap<Node, Node>());
        return locate(head);
    }

    public Node locate(Node head){
        if (head == null) return head;
        Node p = head;
        while(p != null){
            Node copy = new Node(p.val);
            copy.random = p.random;
            copy.next = p.next;
            p.next = copy;
            p = copy.next;
        }

        p = head.next;
        while (p != null){
            if (p.random != null) p.random = p.random.next;
            if (p.next != null) p = p.next.next;
            else break;
        }

        Node p1 = head, p2 = head.next, r = head.next;
        while (p1 != null && p2 != null){
            if (p1.next != null) p1.next = p1.next.next;
            if (p2.next != null) p2.next = p2.next.next;
            else break;

            p1 = p1.next;
            p2 = p2.next;
        }
        return r;
    }

    public Node cache(Node head, Map<Node, Node> map){
        if (head == null) return null;
        Node root = map.get(head);
        if (root != null) return root;

        root = new Node(head.val);
        map.put(head, root);
        root.next = cache(head.next, map);
        root.random = cache(head.random, map);

        return root;
    }

    public Node scan(Node head){
        Node dummy = new Node(0);
        Node p = head, p2 = dummy;
        while (p != null){
            p2.next = new Node(p.val);
            p = p.next;
            p2 = p2.next;
        }

        p = head;
        p2 = dummy.next;
        while (p != null){
            p2.random = getIndex(p.random, head, dummy.next);
            p = p.next;
            p2 = p2.next;
        }
        return dummy.next;
    }

    public Node getIndex(Node target, Node head1, Node head2){
        if (target == null) return null;
        Node p = head1, p2 = head2;
        while (p != null){
            if (p == target) return p2;
            p = p.next;
            p2 = p2.next;
        }
        return null;
    }
}