复制带随机指针的链表

来源Leetcode第138题复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

示例：

输入：
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

解释：
节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。

提示：

你必须返回给定头的拷贝作为对克隆列表的引用。

哈希Map

利用一个哈希Map存储原链表结点和对应的拷贝结点，在原链表里遍历，但是要注意当原结点的随机结点为空时，不能将空结点及其拷贝放入哈希Map里。

public Node copyRandomList(Node head) {
    if(head == null)
        return null;
    Map<Node,Node> map = new HashMap<>();
    Node newHead = new Node();
    map.put(head,newHead);
    Node p1 = newHead;
    while (head != null) {
        p1.val = head.val;
        //p1.next = head.next;
        if(!map.containsKey(head.random) && head.random != null){
            Node tmp = new Node();
            map.put(head.random,tmp);
            p1.random = tmp;
        }else if(head.random != null)
            p1.random = map.get(head.random);
        else
            p1.random = null;
        //map.put(head,p1);
        head = head.next;
        if(head == null)
            break;
        if(!map.containsKey(head)){
            p1.next = new Node();
            map.put(head,p1.next);
            p1 = p1.next;
        }
        else
        {
            p1.next = map.get(head);
            p1 = p1.next;
        }
    }
    return newHead;
}

原结点后追加新结点

HashMap 额外需要 O(n) 的空间复杂度，现在考虑不需要额外空间的方法。

主要参考了这里-and-linear-time-complexity-O(N))。主要解决的问题就是我们生成节点以后，当更新它的 random 的时候，怎么找到之前生成的节点，前两种解法用了 HashMap 全部存起来，这里的话可以利用原来的链表的指针域。

主要需要三步。

生成所有的节点，并且分别插入到原有节点的后边
更新插入节点的 random
将新旧节点分离开来

一图胜千言，大家看一下下边的图吧。

代码对应如下。

public Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    Node l1 = head;
    Node l2 = null;
    //生成所有的节点，并且分别插入到原有节点的后边
    while (l1 != null) {
        l2 = new Node();
        l2.val = l1.val;
        l2.next = l1.next;
        l1.next = l2;
        l1 = l1.next.next;
    }
    //更新插入节点的 random
    l1 = head;
    while (l1 != null) {
        if (l1.random != null) {
            l1.next.random = l1.random.next;
        }
        l1 = l1.next.next;
    }

    l1 = head;
    Node l2_head = l1.next;
    //将新旧节点分离开来
    while (l1 != null) {
        l2 = l1.next;
        l1.next = l2.next;
        if (l2.next != null) {
            l2.next = l2.next.next;
        }
        l1 = l1.next;
    }
    return l2_head;
}

利用random保存新结点

不利用额外的空间复杂度还有一种思路，参考这里。

上一个解法利用原链表的 next 域把新生成的节点保存了起来。类似的，我们还可以利用原链表的 random 域把新生成的节点保存起来。

主要还是三个步骤。

生成所有的节点，将它们保存到原链表的 random 域，同时利用新生成的节点的 next 域保存原链表的 random。
更新新生成节点的 random 指针。
恢复原链表的 random 指针，同时更新新生成节点的 next 指针。

一图胜千言。

public Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    Node l1 = head;
    Node l2 = null;
    //生成所有的节点，讲它们保存到原链表的 random 域，
    //同时利用新生成的节点的 next 域保存原链表的 random。
    while (l1 != null) {
        l2 = new Node();
        l2.val = l1.val;
        l2.next = l1.random;
        l1.random = l2;
        l1 = l1.next;
    }
    l1 = head;
    //更新新生成节点的 random 指针。
    while (l1 != null) {
        l2 = l1.random;
        l2.random = l2.next != null ? l2.next.random : null;
        l1 = l1.next;
    }

    l1 = head;
    Node l2_head = l1.random;
    //恢复原链表的 random 指针，同时更新新生成节点的 next 指针。
    while (l1 != null) {
        l2 = l1.random;
        l1.random = l2.next;
        l2.next = l1.next != null ? l1.next.random : null;
        l1 = l1.next;
    }
    return l2_head;
}