剑指 Offer 35. 复杂链表的复制
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1：
示例 2：
示例 3：
示例 4：
输入：head = [] 输出：[] 解释：给定的链表为空（空指针），因此返回 null。提示：
-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。
首先说明解题思路的时候，先简单说一下这个题主要是让返回的值是你自行复制的链表，也就是说可以采用暴力解法、哈希表或者开辟一个空间来创建一个链表让它进行返回，当然直接return head肯定不行。
一、暴力解法这个暴力解法在LeetCode里面提交题解的时候，提示超出了时间限制，然后看了K神的代码以后，发现还可以再精简完善一些。
class Solution { public Node copyRandomList(Node head) { if(head==null) return null; ArrayList<Node> list = new ArrayList<>(); while(head!=null){ list.add(head); head = head.next; } //创建结果集合并初始化 ArrayList<Node> res = new ArrayList<>(); for(int i = 0;i<list.size();++i){ res.add(new Node(list.get(i).val)); } //设置结果结合的 random和next for (int i = 0; i < list.size(); ++i) { res.get(i).random = list.get(i).random == null?null:res.get(list.indexOf(list.get(i).random)); if(i!=list.size()-1) res.get(i).next = res.get(i+1); } return res.get(0); } } 二、哈希表这里主要的难点在看懂构建新链表的引用指向：
构建新节点的next和random引用指向
cur遍历原链表到下一个节点
class Solution { public Node copyRandomList(Node head) { if (head == null) return null; Node cur = head; Map<Node,Node> res = new HashMap<>(); while(cur != null) {//遍历链表,并存储每个节点的新节点 res.put(cur, new Node(cur.val)); cur = cur.next; } cur = head;//重置cur while (cur != null) { res.get(cur).next = res.get(cur.next);//用cur.next指向res.get(cur).next res.get(cur).random = res.get(cur.random);//用cur.random指向res.get(cur).random cur = cur.next; } return res.get(head);//返回头结点是因为新链表的头结点也存着在res中 } } 三、递归这个做题思路类似于dfs，创建一个节点之后，接着通过递归的方式创建他的next节点……（参考链接见下面）
class Solution { public Node copyRandomList(Node head) { //map存储已经创建的节点 HashMap<Node, Node> map = new HashMap<>(); return copyListHelper(head, map); } public Node copyListHelper(Node head, HashMap<Node, Node> map) { if (head == null) return null; //如果节点创建了，直接从map中取 if (map.containsKey(head)) return map.get(head); //如果节点没有创建，就创建一个，然后使用递归的方式在创建他的 //next节点和random节点 Node res = new Node(head.val); map.put(head, res); res.next = copyListHelper(head.next, map); res.random = copyListHelper(head.random, map); return res; } }参考链接：
https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/9plk45/
https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/shu-ju-jie-gou-he-suan-fa-di-gui-he-fei-wby85/