前置知识
- 数据结构-链表:解法二采用了存粹的链表知识和特殊处理,最优解。
- [可选]数据结构-哈希表:解法一使用了Java语言内置的哈希表
- 【兴趣】哈希思想, 设计哈希函数,开放寻址法,数组模拟哈希表。–笔者未写此法, 如果读者是哈希表的忠实信徒可以尝试写一下, 或无脑开一个大数组避免冲突能够过所有测试用例。
强调, 链表在算法设计其实是练习coding速度的, 笔试应该优先采取容器的方式加快速度, 面试必须采用最优解法。
题目:带随机指针的复制列表
- 题目给定了
Node类
的定义。
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
Node类中的value是节点值, next指针是常规链表的后继节点,不过, 题目还给节点附带了random指针,它随机指向链表中的某个节点,或可能指向为空(null)。
题目要求,我们深拷贝这个链表。
对于自定义类型,引用存储的是对象的地址, 不能简单的浅拷贝(值复制)这些节点, 因为从底层上相当于位的拷贝, 实际两个引用(指针)指向了同一的内存块。怎么做? 单独开一块内存,基本类型进行值拷贝,自定义类型进行深拷贝。
假设节点node.val = 1,那么应该重新创建新节点newNode,它的值也是1,但在不同的堆内存。
这道题,应该避免新列表中的任何指针都不应指向原始列表中的节点。
它们应该在内存中独立,而不是同一块, 而且它们对应的字段应该保持一致。
本质是Java容器的clone拷贝
解法1:Java内置HashMap
为了新链表与原链表建立一个直观的联系。
采用哈希表:
- 遍历原链表,将原链表节点与新链表节点(创建一份副本)映射联系起来, 放入
HashMap
中。 - 再次遍历原链表,根据
key-value
的对应关系,取出对应节点的副本,将next,random
对应原链表节点的副本连接起来。
import java.util.HashMap;
//不要提交这个类
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
//测试链接:https://leetcode.com/problems/copy-list-with-random-pointer/submissions/1426261747/
//提交:将类名改为Solution
public class CopyRandomList {
public static Node copyRandomList(Node head) {
if (head == null) {
return null;//排除空表, 直接返回null
}
//初始化哈希表: key:原链表的节点 value:对应节点的副本
HashMap<Node, Node> map = new HashMap<>();
Node cur;
//第一次遍历为每个节点拷贝一份副本, 存储到哈希表
for (cur = head; cur != null; cur = cur.next) {
map.put(cur, new Node(cur.val));// 拷贝原节点的一份副本。
}
//新链表的头节点和尾节点
Node newHead = map.get(head);
Node newTail = newHead;
//第二次遍历原链表,连接指针。
for (cur = head; cur != null; cur = cur.next) {
//根据哈希表取出节点next,random的副本
newTail.next = map.get(cur.next);
newTail.random = map.get(cur.random);
newTail = newTail.next;//尾节点往后跟。
}
return newHead;//返回头节点。
}
}
时间复杂度:
O
(
n
)
O(n)
O(n), 因为只遍历了两次原链表,哈希表插入查询是常量时间。
空间复杂度:
O
(
n
)
O(n)
O(n), 因为存储了所有节点数及其副本。
解法2:技巧
接下来是进阶方法, 空间复杂度要做到
O
(
1
)
O(1)
O(1)。
前面的哈希表的作用?
存储原节点和副本的联系。通过哈希表, 原链表的连接方式可以很好映射到新链表的处理。
有没有同样的方法, 可以做到常数空间(不用哈希表)也能实现高效的寻址映射呢?
单链表有个很快的特性,已知节点可以迅速找到它的后继,因为只需要node.next
即可。
基本思路:
- 遍历原链表,并将每个节点生成的副本挂在该节点的后面,来达到快速查询的作用。
比如原链表[1->2->3->null]
,这里以1'
视作节点1的副本, 按照上述。应该拷贝原节点并修改原链表[1->1'->2->2'->3->3'->null]
。 - 上述可以快速寻址, 但是有什么显然的意义呢?答:修改
random
指针,比如1的random指针指向3这个节点,那么1’应该指向3’。那么再次遍历原链表修改random指针时。比如修改1‘的random指针,先通过1.random定位到3, 再通过3.next定位到3’, 再让1‘.random连接到3’。总结:第二次遍历根据副本是源节点的后继来设置副本的random指针。 - 最后一步,由于我们修改了原链表,还要获得新链表。因此,需要实现链表分离。
public static Node copyRandomList(Node head) {
// 单独处理空链表的情况,直接返回null
if (head == null) {
return null;
}
// 第一次遍历链表:为每个节点创建一个副本,并将副本插入到原节点的后面
Node cur = head, next = null;
while (cur != null) {
next = cur.next; // 暂存原节点的下一个节点
// 创建副本节点,并插入到原节点的后面
cur.next = new Node(cur.val);
cur.next.next = next; // 将新创建的副本节点的next指向原节点的下一个节点
cur = next; // 移动到原链表的下一个节点
}
// 第二次遍历链表:设置新节点的random指针
cur = head;
Node curCopy = null;
while (cur != null) {
next = cur.next.next; // 跳过副本节点,找到下一个原节点
curCopy = cur.next; // cur的副本节点
// 如果原节点的random指针不为空,设置副本节点的random指针指向原链表random节点的副本
curCopy.random = cur.random == null ? null : cur.random.next;
cur = next; // 移动到下一个原节点
}
// 第三次遍历链表:将原链表和副本链表分离
cur = head;
Node newHead = head.next; // 新链表的头节点
while (cur != null) {
next = cur.next.next; // 获取原链表的下一个节点(跳过副本节点)
curCopy = cur.next; // 获取当前节点的副本
// 恢复原链表的结构:将原节点的next指针指回到下一个原节点
cur.next = next;
// 连接副本链表的next指针:指向下一个副本节点
curCopy.next = next == null ? null : next.next; // 处理next为null的情况
cur = next; // 移动到下一个原节点
}
// 返回新链表的头节点
return newHead;
}