算法1

(hashmap)

第一种方法：
用hashmap将每个节点先进行copy，然后用原节点做key，复制节点做value存进hashmap
然后遍历链表，把复制节点取出连好即可，因为hashmap的增删改查是O（n）。所以时间复杂度很低。

Java 代码

class Solution {
    public ListNode copyRandomList(ListNode head) {
        if(head==null)
            return null;

        Map<ListNode,ListNode> copy = new HashMap<>();

        ListNode node = head;
        while(node!=null){
            ListNode CloneNode = new ListNode(node.val);
            copy.put(node,CloneNode);
            node = node.next;
        }

        node = head;
        ListNode CloneHead = copy.get(node);
        ListNode CloneNode = CloneHead;

        while(node!=null){
            CloneNode.next = copy.get(node.next);
            if(node.random!=null){
                CloneNode.random = copy.get(node.random);
            }
            CloneNode = CloneNode.next;
            node = node.next;
        }

        return CloneHead;

    }
}

算法2

(时间换空间)

第二种方法：
复制每个节点，每复制一个就把复制节点接在被复制的节点后面，然后从头遍历一遍，将复制节点的随机节点纸箱被复制节点的后面的节点。
然后将两个链表分开即可。

Java 代码

class Solution {
    public ListNode copyRandomList(ListNode head) {
        if(head==null)
            return null;

        ListNode node1 = head;

        while(node1!=null){
            ListNode node2 = new ListNode(node1.val);
            node2.next = node1.next;
            node1.next = node2;
            node1 = node1.next.next;
        }

        ListNode ran1 = head;
        while(ran1!=null){
           ListNode ran2 = ran1.next;
           if(ran1.random!=null){
            ran2.random = ran1.random.next;
           }
           ran1 = ran2.next;
        }

        ListNode node = head;
        ListNode cloneNode = null;
        ListNode cloneHead = null; 

        if(node!=null){
            cloneHead = node.next;
            cloneNode = cloneHead;
            node.next = cloneNode.next;
            node = cloneNode.next;
        }

        while(node!=null){
            cloneNode.next = node.next;
            cloneNode = cloneNode.next;
            node.next = cloneNode.next;
            node= cloneNode.next;
        }

        return cloneHead;

    }
}