package com.jiucaiyuan.net.algrithm.linked;



import java.util.HashMap;



/**

 * 【问题】复制带有随机指针节点的链表

 * 【要求】时间复杂度O(N)，空间复杂度O(1)

 * 【思路】如果不是空间复杂度O(1)的限制，可以使用Map，暂存新老节点之间的关系，

 * 然后再补齐rand字段，但是有O(1)限制，所以在克隆出新节点时，放到该节点之后，

 * 变成注入这个结构：1——>1`——>2——>2`——>3——>3`——>4——>4`——>5——>5`

 * 然后再遍历next、next.next，补齐rand，然后再拆出来新老链表，返回新链表的头结点

 *

 * @Author jiucaiyuan  2022/4/5 21:46

 * @mail services@jiucaiyuan.net

 */



public class CopyListWithRand {

    /** 使用额外空间

     * @param head

     * @return

     */

    public static Node copyListWithRand1(Node head, int value) {

        if (head == null){

            return null;

        }

        //把所有原节点放到map的key中，并克隆节点作为map的value

        HashMap<Node,Node> map = new HashMap<>();

        Node curr = head;

        while (curr != null){

            map.put(curr, new Node(curr.value));

            curr = curr.next;

        }



        //循环设置新节点的next和rand

        curr = head;

        while (curr != null){

            //curr 老的

            //map.get(curr) 新的

            map.get(curr).next = map.get(curr.next);

            map.get(curr).rand = map.get(curr.rand);

            curr = curr.next;

        }

        return map.get(head);

    }



    /** 不使用额外空间

     * @param head

     * @return

     */

    public static Node copyListWithRand2(Node head, int value) {

        if (head == null){

            return null;

        }

        //copy node : 1——>2——>3——>null  to  1——>1`——>2——>2`——>3——>3`——>null

        Node curr = head;

        Node next = null;

        while (curr != null){

            next = curr.next;

            curr.next = new Node(curr.value);

            curr.next.next = next;

        }



        curr = head;

        Node currCopy = null;

        //set copy node rand

        //1——>1`——>2——>2`——>3——>3`——>null

        while (curr != null){

            next = curr.next.next;

            currCopy = curr.next;

            currCopy.rand = next.rand != null ? next.rand.next:null;

            curr = next;

        }



        Node res = head.next;

        curr = head;

        //split 1——>1`——>2——>2`——>3——>3`——>null to 1——>2——>3——>null and 1`——>2`——>3`——>null

        while (curr != null){

            next = curr.next.next;

            currCopy = curr.next;

            curr.next = next;

            currCopy.next = next != null ? next.next:null;

            curr = next;

        }

        return res;

    }



    static class Node{

        int value;

        Node next;

        Node rand;

        public Node(int value){

            this.value = value;

        }

    }

}