剑指 Offer 35. 复杂链表的复制
剑指 Offer 35. 复杂链表的复制
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 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;
}
}
参考链接：
//leetcode-cn.com/leetbook/read/illustration-of-algorithm/9plk45/
