138. 复制带随机指针的链表

题目：

知识提要：

①浅拷贝:创建一个新对象，这个对象有着原始对象属性值的一份精确拷贝。如果属性是基本类型，拷贝的就是基本类型的值，如果属性是引用类型，拷贝的就是内存地址 ，所以如果其中一个对象改变了这个地址，就会影响到另一个对象。即修改拷贝的新对象会影响原始对象。
②深拷贝：将一个对象从内存中完整的拷贝一份出来，在堆内存中开辟一个新的区域存放新的对象。即修改拷贝的新对象不会影响原始对象。

思路：

①在原始链表的每个节点之后添加该节点的副本
②循环原始链表的每个节点的random,若其有值则添加给复制的节点
③提取出新链表，并还原旧链表

代码：

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        Node pre = head;
        if(head == null)
            return null;
        while(pre != null){//在每个节点后面复制一个该节点
            Node copynode  =new Node(pre.val);
            copynode.next = pre.next;
            pre.next = copynode;
            pre = pre.next.next; 
        }
        pre = head;
        while(pre != null){
            pre.next.random = (pre.random != null) ? pre.random.next : null; 
            pre = pre.next.next;
        }
        Node new_list = head.next;
        Node new_pre = head.next;
        Node old_pre = head;
        while(old_pre != null){
            old_pre.next = new_pre.next;
            new_pre.next = (new_pre.next == null) ? null : new_pre.next.next;
            new_pre = new_pre.next;
            old_pre = old_pre.next;
            
        }
        return new_list;

    }
}

复杂度分析：

时间复杂度：O（n）
空间复杂度：O（1）