032随机链表的复制

随机链表的复制题目链接https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public Node copyRandomList(Node head) { Node dummy new Node(-1); Node curhead, newCur, newPredummy; MapNode, Integer map new HashMap(); MapInteger, Node newMap new HashMap(); int count0; 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:拷贝节点 MapNode,Node map new HashMap(); public Node copyRandomList(Node head) { if(headnull){ 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(headnull){ return null; } //第一遍遍历拷贝原始节点并将拷贝节点连接在原始节点之后 for(Node curhead; cur!null; curcur.next.next){ Node newCur new Node(cur.val); newCur.next cur.next; cur.next newCur; } //第二遍遍历拷贝原始节点的random for(Node curhead; cur!null; curcur.next.next){ Node newCur cur.next; newCur.random cur.randomnull ? null : cur.random.next; } //第三遍遍历拆分原始链表和拷贝链表 Node newHead head.next; for(Node curhead; cur!null; curcur.next){ Node newCur cur.next; cur.next newCur.next; newCur.next newCur.nextnull ? 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映射关系和节点拆分。