第二十四题：复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路：

        Hash表解法：时间复杂度O(N)，空间复杂度O(N)

            ①遍历原链表，并且每次创建新节点

            ②将oldNode与copyNode存储到Hash表中。例如HashMap<ListNode,ListNode>

            ③遍历原链表，并进行copyList的生成操作。(连接新节点)

        三步走策略(只操作原链表)：时间复杂度O(N)，空间复杂度O(1)

            ①遍历原链表，且每走到一个oldNode时，创建copyNode，并连接在oldNode后

            ②根据原链表中的random指针，连接copyNode的random指针

            ③从原链表中拆分出copyList和oldList

具体实现如下图所示：

时间复杂度为O(N)，空间复杂度为O(N)的解：

时间复杂度为O(N)的解：

具体实现代码如下：

    //Hash表解法，时间和空间复杂度都为O(N)
    public RandomListNode Clone(RandomListNode pHead){
        //创建hash表
        HashMap<RandomListNode,RandomListNode> map = new HashMap<>();
        //遍历原链表，并存储到hash表中作为key，value为新节点
        RandomListNode cur = pHead;
        while (cur != null){
            map.put(cur,new RandomListNode(cur.label));
            cur = cur.next;
        }
        //遍历原链表，生成新链表，连接新节点
        cur = pHead;
        while (cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        //返回新链表头
        return map.get(pHead);
    }


    //原链表操作三步走策略，时间复杂度都为O(N)  空间复杂度为O(1)
    public RandomListNode Clone(RandomListNode pHead) {
        //代码的鲁棒性
        if(pHead == null) {
            return null;
        }

        //1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
        //创建引用结点（用于遍历）
        RandomListNode currentNode = pHead;
        while(currentNode != null){
            //复制节点
            RandomListNode cloneNode = new RandomListNode(currentNode.label);
            //记录当前节点的next结点
            RandomListNode nextNode = currentNode.next;
            //将当前结点的指针指向复制节点
            currentNode.next = cloneNode;
            //复制节点的next指针指向缓存节点
            cloneNode.next = nextNode;
            //开始下一个结点
            currentNode = nextNode;
        }

        //2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
        //创建引用结点（用于遍历）
        currentNode = pHead;
        while(currentNode != null) {
            //利用第一步操作的特性，A1.random = A.random.next;
            currentNode.next.random = currentNode.random==null?                    
            null:currentNode.random.next;
            //继续连接下一个结点，跳过cloneNode结点
            currentNode = currentNode.next.next;
        }

        //3、拆分链表，将链表拆分为原链表和复制后的链表
        //创建引用结点（用于遍历）
        currentNode = pHead;
        //copyList的头结点
        RandomListNode pCloneHead = pHead.next;
        while(currentNode != null) {
            //clone结点
            RandomListNode cloneNode = currentNode.next;
            //oldNode的指针指向下一个oldNode
            currentNode.next = cloneNode.next;
            //copyNode指向下一个copyNode
            cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
            //继续操作oldNode的下一个结点
            currentNode = currentNode.next;
        }

        //返回新链表
        return pCloneHead;
    }