随机链表的复制
题目链接：https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-100-liked
我的解答：
public Node copyRandomList(Node head) { Node dummy = new Node(-1); Node cur=head, newCur, newPre=dummy; Map<Node, Integer> map = new HashMap<>(); Map<Integer, Node> newMap = new HashMap<>(); int count=0; while(cur!=null){ map.put(cur,count); newCur = new Node(cur.val); newMap.put(count,newCur); newPre.next = newCur; cur = cur.next; newPre = newCur; count++; } cur = head; newCur = dummy.next; while(cur != null){ if(cur.random != null){ newCur.random = newMap.get(map.get(cur.random)); } cur = cur.next; newCur = newCur.next; } return dummy.next; }分析：代码的时间复杂度为O(n)，空间复杂度为O(n)。解题思路：采用哈希表，map的key存储原始链表的节点，value存储序号，newMap的key存储序号，value存储拷贝链表的节点。先通过遍历原始链表建出新链表，将新、旧节点及其序号分别存入newMap和map，方便后续通过旧节点获取序号，然后新节点直接通过序号获取random。
看了官方题解后的解答：
//方法一：递归（回溯）+哈希表 //时间复杂度：O(n) //空间复杂度：O(n) //key:原始节点 value:拷贝节点 Map<Node,Node> map = new HashMap<>(); public Node copyRandomList(Node head) { if(head==null){ return null; } if(!map.containsKey(head)){ Node newHead = new Node(head.val); map.put(head,newHead); newHead.next = copyRandomList(head.next); newHead.random = copyRandomList(head.random); } return map.get(head); } //方法二：迭代+节点拆分 //时间复杂度：O(n) //空间复杂度：O(1) public Node copyRandomList(Node head) { if(head==null){ return null; } //第一遍遍历：拷贝原始节点，并将拷贝节点连接在原始节点之后 for(Node cur=head; cur!=null; cur=cur.next.next){ Node newCur = new Node(cur.val); newCur.next = cur.next; cur.next = newCur; } //第二遍遍历：拷贝原始节点的random for(Node cur=head; cur!=null; cur=cur.next.next){ Node newCur = cur.next; newCur.random = cur.random==null ? null : cur.random.next; } //第三遍遍历：拆分原始链表和拷贝链表 Node newHead = head.next; for(Node cur=head; cur!=null; cur=cur.next){ Node newCur = cur.next; cur.next = newCur.next; newCur.next = newCur.next==null ? null : newCur.next.next; } return newHead; }分析：
1、方法一采用递归。我们用map保存原始节点到拷贝节点的映射，若map中不存在当前原始节点的映射关系，我们就拷贝原始节点，并将原始节点和拷贝节点的映射关系放入map，然后继续递归拷贝原始节点的next和random；若map中存在当前原始节点的映射关系，我们直接通过原始节点获取对应的拷贝节点返回即可。
2、方法二采用迭代+节点拆分。第一次遍历先将原始链表的每一个节点拷贝一份，并连接在其原始节点之后；第二次遍历根据原始节点的random连接拷贝节点对应的random，第三次遍历将原始链表和拷贝链表拆分，最后返回拷贝链表的头节点即可。
3、方法一通过map保存原始节点与拷贝节点的映射关系，拷贝节点直接通过map获取random对应的拷贝节点；而方法二直接将每个原始节点的拷贝节点连接在拷贝节点之后（例如原始节点为S，拷贝节点为S’，假设原始链表为A—>B—>C，那么我们可以将原始链表拆分为A—>A’—>B—>B’—>C—>C’），拷贝节点可以直接通过原始节点的random找到拷贝节点的random。
总结
- 本题主要需要思考如何获取每个拷贝节点的random，官方题解给出了两种方法，分别为Map映射关系和节点拆分。
