【面试高频题】可逐步优化的链表高频题

题目描述
这是 LeetCode 上的 138. 复制带随机指针的链表 &＃xff0c;难度为 中等。
Tag : 「哈希表」、「链表」
给你一个长度为 n 的链表&＃xff0c;每个节点包含一个额外增加的随机指针 random&＃xff0c;该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成&＃xff0c;其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点&＃xff0c;并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如&＃xff0c;如果原链表中有 X 和 Y 两个节点&＃xff0c;其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y &＃xff0c;同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示&＃xff1a;

• val&＃xff1a;一个表示 Node.val 的整数。
• random_index&＃xff1a;随机指针指向的节点索引&＃xff08;范围从 000 到 n−1n-1n−1&＃xff09;&＃xff1b;如果不指向任何节点&＃xff0c;则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1&＃xff1a;

输入&＃xff1a;head &＃61; [[7,null],[13,0],[11,4],[10,2],[1,0]]输出&＃xff1a;[[7,null],[13,0],[11,4],[10,2],[1,0]]



示例 2&＃xff1a;

输入&＃xff1a;head &＃61; [[1,1],[2,1]]输出&＃xff1a;[[1,1],[2,1]]



示例 3&＃xff1a;

输入&＃xff1a;head &＃61; [[3,null],[3,0],[3,null]]输出&＃xff1a;[[3,null],[3,0],[3,null]]



示例 4&＃xff1a;

输入&＃xff1a;head &＃61; []输出&＃xff1a;[]解释&＃xff1a;给定的链表为空&＃xff08;空指针&＃xff09;&＃xff0c;因此返回 null。



提示&＃xff1a;

• 0<&＃61;n<&＃61;10000
• −10000<&＃61;Node.val<&＃61;10000

模拟 &＃43; 哈希表

如果不考虑 random 指针的话&＃xff0c;对一条链表进行拷贝&＃xff0c;我们只需要使用两个指针&＃xff1a;一个用于遍历原链表&＃xff0c;一个用于构造新链表&＃xff08;始终指向新链表的尾部&＃xff09;即可。这一步操作可看做是「创建节点 &＃43; 构建 next 指针关系」。
现在在此基础上增加一个 random 指针&＃xff0c;我们可以将 next 指针和 random 指针关系的构建拆开进行&＃xff1a;

1.先不考虑 random 指针&＃xff0c;和原本的链表复制一样&＃xff0c;创建新新节点&＃xff0c;并构造 next 指针关系&＃xff0c;同时使用「哈希表」记录原节点和新节点的映射关系&＃xff1b;
2.对原链表和新链表进行同时遍历&＃xff0c;对于原链表的每个节点上的 random 都通过「哈希表」找到对应的新 random 节点&＃xff0c;并在新链表上构造 random 关系。

代码&＃xff1a;

class Solution {public Node copyRandomList(Node head) {Node t &＃61; head;Node dummy &＃61; new Node(-10010), cur &＃61; dummy;Map<Node, Node> map &＃61; new HashMap<>();while (head !&＃61; null) {Node node &＃61; new Node(head.val);map.put(head, node);cur.next &＃61; node;cur &＃61; cur.next; head &＃61; head.next;}cur &＃61; dummy.next; head &＃61; t;while (head !&＃61; null) {cur.random &＃61; map.get(head.random);cur &＃61; cur.next; head &＃61; head.next;}return dummy.next;}
}



时间复杂度&＃xff1a;O(n)
空间复杂度&＃xff1a;O(n)

模拟&＃xff08;原地算法&＃xff09;

显然时间复杂度上无法优化&＃xff0c;考虑如何降低空间&＃xff08;不使用「哈希表」&＃xff09;。
我们使用「哈希表」的目的为了实现原节点和新节点的映射关系&＃xff0c;更进一步的是为了快速找到某个节点 random 在新链表的位置。
那么我们可以利用原链表的 next 做一个临时中转&＃xff0c;从而实现映射。
具体的&＃xff0c;我们可以按照如下流程进行&＃xff1a;

1.对原链表的每个节点节点进行复制&＃xff0c;并追加到原节点的后面&＃xff1b;
2.完成 1 操作之后&＃xff0c;链表的奇数位置代表了原链表节点&＃xff0c;链表的偶数位置代表了新链表节点&＃xff0c;且每个原节点的 next 指针执行了对应的新节点。这时候&＃xff0c;我们需要构造新链表的 random 指针关系&＃xff0c;可以利用 link[i &＃43; 1].random &＃61; link[i].random.next&＃xff0c;iii 为奇数下标&＃xff0c;含义为 新链表节点的 random 指针指向旧链表对应节点的 random 指针的下一个值&＃xff1b;
3.对链表进行拆分操作。

代码&＃xff1a;

class Solution {public Node copyRandomList(Node head) {if (head &＃61;&＃61; null) return head;Node t &＃61; head;while (head !&＃61; null) {Node node &＃61; new Node(head.val);node.next &＃61; head.next;head.next &＃61; node;head &＃61; node.next;}head &＃61; t;while (head !&＃61; null) {if (head.random !&＃61; null) head.next.random &＃61; head.random.next;head &＃61; head.next.next;}head &＃61; t;Node ans &＃61; head.next;while (head !&＃61; null) {Node ne &＃61; head.next;if (ne !&＃61; null) head.next &＃61; ne.next;head &＃61; ne;}return ans;}
}



时间复杂度&＃xff1a;O(n)
空间复杂度&＃xff1a;O(1)

源码附件已经打包好上传到百度云了&＃xff0c;大家自行下载即可&＃xff5e;

链接: https://pan.baidu.com/s/14G-bpVthImHD4eosZUNSFA?pwd&＃61;yu27
提取码: yu27
百度云链接不稳定&＃xff0c;随时可能会失效&＃xff0c;大家抓紧保存哈。

如果百度云链接失效了的话&＃xff0c;请留言告诉我&＃xff0c;我看到后会及时更新&＃xff5e;

开源地址
码云地址&＃xff1a;
http://github.crmeb.net/u/defu

Github 地址&＃xff1a;
http://github.crmeb.net/u/defu

链接&＃xff1a;https://juejin.cn/post/7129696149100363789