思路一

1. 链表节点的定义包含三个属性，一个val一个next指针，一个random指针
2. 复制的时候每个节点需要重新new一个实例
3. val和next指针比较简单，主要是random指针的处理，这里需要保存节点在整个链表中的相对位置。核心思路就是在处理复制原节点的时候，从map中获取random节点的相对位置（可能为null），然后新节点从数组中获取该位置的node（或者获取null）

/*
// 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) {
        // 列表保存每个节点的顺序，random可以获取是指向的index
        
        if (head == null) return null;
        // 保存节点和在数组中的索引地址
        Map<Node, Integer> indexMap = new HashMap<>();
        // 保存新旧节点
        ArrayList<Node> listNode = new ArrayList<>();
        ArrayList<Node> newNodeList = new ArrayList<>();
        int index = 0;
        while (head != null) {
            listNode.add(head);
            newNodeList.add(new Node(head.val));
	    // 保存节点在整个数组中的位置
            indexMap.put(head,index);
            head = head.next;
            index ++;
        }

        for(int i = 0; i < newNodeList.size(); i++) {
            if (i == (newNodeList.size() -1))
                newNodeList.get(i).next = null;
            else
                newNodeList.get(i).next = newNodeList.get(i+1);

            if (listNode.get(i).random == null) {
                newNodeList.get(i).random = null;
            } else {
                newNodeList.get(i).random = newNodeList.get(indexMap.get(listNode.get(i).random));
            }
        }

        return newNodeList.get(0);
    }
}

思路二（更佳，精简不易出错）

1. 链表自身保存了每个节点的先后顺序，但是random节点为随机指向，但是可以通过map在O(1)时间内查找到对应的节点位置
2. 因此可以通过map保存老节点和新节点的方式形成一一对应的两条链

public Node copyRandomList(Node head) {
        if (head == null) return null;
        HashMap<Node, Node> nodeMap = new HashMap<>();
        Node tmp = head;
        while (tmp != null) {
	    // 保存两个节点的一一对应关系
            nodeMap.put(tmp,new Node(tmp.val));
            tmp = tmp.next;
        }
        tmp = head;
        while(tmp != null) {
            Node node = nodeMap.get(tmp);
            node.next = nodeMap.get(tmp.next);
            node.random = nodeMap.get(tmp.random);
            tmp = tmp.next;
        }
        return nodeMap.get(head);
    }

Q.E.D.