复制含有随机指针节点的链表

// 使用额外空间：使用hash表，key是老节点，value是新节点。
// 遍历老节点，并取出对应value新节点，然后获得老节点next，
// 再从hash表中找出老节点next的value，新节点next就是这个value。rand也是这样。
    public static Node copyRandomList1(Node head) {
        // key 老节点
        // value 新节点
        HashMap<Node, Node> map = new HashMap<Node, Node>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            // cur 老
            // map.get(cur) 新
            // 新.next ->  cur.next克隆节点找到
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
// 老节点挂在新节点的next，然后新节点next指向老节点next。然后循环一对一对的设置rand。
// 新节点的rand就是老节点的rand的next，最后新老链表分离。利用新节点的位置关系实现了一一对应。1→1'→2→2’
    public static Node copyRandomList2(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Node next = null;
        // 1 -> 2 -> 3 -> null
        // 1 -> 1' -> 2 -> 2' -> 3 -> 3'
        while (cur != null) {
            next = cur.next; // 保留当前节点后驱
            cur.next = new Node(cur.val); // 当前节点后驱指向当前复制节点
            cur.next.next = next; 
            cur = next;
        }
        cur = head;
        Node copy = null;
        // 1 1' 2 2' 3 3'
        // 依次设置 1' 2' 3' random指针
        while (cur != null) {
            next = cur.next.next;
            copy = cur.next;                    
            // 当前节点的随机节点下一个就是复制节点的随机节点
            copy.random = cur.random != null ? cur.random.next : null;
            cur = next;
        }
        Node res = head.next;
        cur = head;
        // 老 新 混在一起，next方向上，random正确
        // next方向上，把新老链表分离
        while (cur != null) {
            next = cur.next.next;
            copy = cur.next;
            cur.next = next;
            copy.next = next != null ? next.next : null;
            cur = next;
        }
        return res;
    }