38_复杂链表的复制

要求：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
思路：
浅拷贝只复制指向某个对象的指针，而不复制对象本身，新旧对象还是共享同一块内存。但深拷贝会另外创造一个一模一样的对象，新对象跟原对象不共享内存，修改新对象不会改到原对象。

方法一：使用哈希表。第一步仍然是将原始链表上的每个节点 N复制为N',然后把这些创建出来的节点N’连接起来。同时我们把<N,N'>的配对信息放到一个HashMap<Node,Node> map中;第二步设置每个节点的random指针:如果在原始链表中节点 N的random指针指向节点 S,那么在复制链表中,对应的 N'节点应该指向 S'。由于有了哈希表，我们可以用O(1)的时间根据S找到S'。使用空间换时间，以O(n)的空间消耗把时间复杂度由 $O(n^2)$ 降到 $O(n)$ 。

public class L36_Clone {
    // 使用哈希表的方法

    public RandomListNode Clone(RandomListNode head) {
        // 判断边界
        if(head==null)return null;
        // 创建一个哈希表
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        // 定位一个临时结点p，指向头结点
        RandomListNode p = head;
        // 从头到尾将复制结点
        while(p!=null){
            // 将<N，N'>的配对信息放到一个哈希表中。
            map.put(p, new RandomListNode(p.label));
            p = p.next;
        }
        p = head;
        // 从头到尾连接结点的next和random
        while(p!=null){
            map.get(p).next = map.get(p.next);
            map.get(p).random = map.get(p.random);
            p = p.next;
        }
        return map.get(head);
    }
}

方法二:不使用辅助空间的情况下实现O(n)的时间效率。
1、第一步：依然是根据原始链表的每个节点N创建对应的N'。不过是把N'链接在N的后面。
2、第二步：重新遍历链表，复制老结点的随机指针给新结点
3、第三步：拆分链表，将链表拆分为原链表和复制后的链表

    // 方法二：不使用辅助空间的情况下实现O(n)的时间效率。
    // 第一步：依然是根据原始链表的每个节点N创建对应的N'。不过是把N'链接在N的后面。
    public void copy(RandomListNode head){
        RandomListNode p = head;
        while(p!=null){
            // 复制一个新的节点
            RandomListNode cloneNode = new RandomListNode(p.label);
            RandomListNode nextNode = p.next;
            // 将复制的新节点连接到原来节点后面
            p.next = cloneNode;
            cloneNode.next = nextNode;
            p=nextNode;
        }
    }

    // 第二步：重新遍历链表，复制老结点的随机指针给新结点
    public void randomDirect(RandomListNode head){
        RandomListNode p = head;
        // 从头到尾遍历
        while(p!=null){
            // 找到原来节点的随机指针，复制的结点同时操作
            p.next.random = p.random==null? null:p.random.next;
            p = p.next.next;
        }

    }
    // 第三步：拆分链表，将链表拆分为原链表和复制后的链表
    public RandomListNode reList(RandomListNode head){
        RandomListNode p = head;
        RandomListNode cloneHead = p.next;
        while(p!=null){
            RandomListNode cloneNode = p.next;
            p.next = cloneNode.next;
            cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
            p = p.next;
        }
        return cloneHead;
    }