/**

 * 题目：复杂链表的复制

 * 描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。

 *   （注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

 * 方案：方法一：  ① 遍历原链表，每次创建新节点，放入到HashMap里面；

 *     ② 遍历，进行节点连接； 

 *     ③ HashMap中，Value对应的值就是复制的链表

 *           方法二：  将原链表和复制的链表先放到一起，然后在进行拆分

 * */

public class Five {        public static RandomListNode one(RandomListNode phead) {        HashMap
     
       hashMap  =  new HashMap<>();        RandomListNode cur;        cur = phead;        while(cur != null) {            hashMap.put(cur, new RandomListNode(cur.label));            cur = cur.next;        }        cur = phead;        while(cur != null) {            hashMap.get(cur).next = hashMap.get(cur.next);            hashMap.get(cur).random = hashMap.get(cur.random);            cur = cur.next;        }        return hashMap.get(phead);    }    public static RandomListNode two(RandomListNode phead) {        if(phead == null) {            return null;        }        RandomListNode current = phead;        //1.复制节点到A与B之间   A  A*  B  , 连接任意节点和next节点        while(current !=null) {            RandomListNode cloneNode = new RandomListNode(current.label);             RandomListNode nextNode = current.next;            RandomListNode randomNode = current.random == null? null:current.random ;            cloneNode.next = nextNode;            current.next = cloneNode;            cloneNode.random = randomNode;            current = nextNode;        }                //拆分        current = phead;        RandomListNode pCloneHead = phead.next;        while(current !=null ) {            RandomListNode cloneNode = current.next;            current.next = cloneNode.next;            cloneNode.next = phead.next.next == null?null:phead.next.next;            current = current.next;        }            return null;    }        static class RandomListNode{            int label;        RandomListNode next;        RandomListNode random;        public RandomListNode(int label) {            super();            this.label = label;        }    }}