复杂链表的复制

题目链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/

image.png

思路解题
本题实需要现一个复杂链表的深拷贝，因为涉及到随机性，next和random节点可能会没有被创建，所以本题的难点是怎么在创建之后在设置next和random节点。

思路一：
采用HashMap进行缓存Node，如果HashMap对应没有找到这个Node，就进行创建和缓存，缓存之后在赋值next和random节点。
代码如下

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    HashMap<Node,Node> nodeNodeCache = new HashMap<>();
    public Node copyRandomList(Node head) {
        if (head==null){
            return null;
        }
        if (!nodeNodeCache.containsKey(head)){
            Node node = new Node(head.val);
            nodeNodeCache.put(head,node);
            node.next = copyRandomList(head.next);
            node.random = copyRandomList(head.random);
        }
        return nodeNodeCache.get(head);
    }

复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)。

思路二：
在思路一的基础上主要是针对空间复杂度的优化，采用A→B→C ---> A→A'→B→B'→C→C' 在进行random和next的赋值。如下图所示:

原始node.png
复制node.png
random指向.png
next指向.png

代码如下

public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        // 复制node
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = new Node(node.val);
            nodeNew.next = node.next;
            node.next = nodeNew;
        }
       // random指向
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = node.next;
            nodeNew.random = (node.random != null) ? node.random.next : null;
        }
        Node headNew = head.next;
       //next指向
        for (Node node = head; node != null; node = node.next) {
            Node nodeNew = node.next;
            node.next = node.next.next;
            nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
        }
        return headNew;
    }

复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。