【Leetcode】138. Copy List with Random Pointer
程序员文章站
2022-05-23 21:47:42
...
题目地址:
https://leetcode.com/problems/copy-list-with-random-pointer/
给定一个链表,每个node不但指向下一个node,还指向另一个random node。要求deep copy一份这个链表。
法1:DFS。同copy二叉树是类似的,这里可以采用递归的办法。但与二叉树不同的是,二叉树没有环,而这个链表的random有可能会指向之前的node,所以这里需要用一个哈希表记录一下某个node有没有被copy过。如果有的话,直接返回那个之前copy的就行了。否则就new一个新的。代码如下:
import java.util.HashMap;
import java.util.Map;
public class Solution {
public Node copyRandomList(Node head) {
// 记录已经被copy过的node和它们对应的node,
// key是原链表的node,value是深拷贝出来的对应的node
Map<Node, Node> map = new HashMap<>();
// null直接copy为null
map.put(null, null);
return dfs(head, map);
}
// 返回深拷贝出来的与参数node相对应的node
private Node dfs(Node node, Map<Node, Node> map) {
// 如果该node已经被拷贝过,那就直接get出来返回
if (map.containsKey(node)) {
return map.get(node);
}
// 否则说明没拷贝过,那就先拷贝一个出来
map.put(node, new Node(node.val));
// 将其next和random也拷贝出来,接上去
map.get(node).next = dfs(node.next, map);
map.get(node).random = dfs(node.random, map);
// 返回这个新拷贝出来的node
return map.get(node);
}
}
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
时间,空间。
法2:BFS。模仿BFS一个图的方法来做,也是要用一个哈希表记录已经copy过的node和其对应的node,然后用一个队列来做BFS。遇到未copy过的node就new出来接上去,否则直接接上已经copy过的那个对应的node。代码如下:
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
public class Solution {
public Node copyRandomList(Node head) {
// 判空
if (head == null) {
return null;
}
// 记录已经copy过的node及其对应的node。含义同上
Map<Node, Node> map = new HashMap<>();
// 先把head拷贝一份
map.put(head, new Node(head.val));
// 再开一个队列把head放进去,以便于BFS
Queue<Node> queue = new LinkedList<>();
queue.add(head);
while (!queue.isEmpty()) {
Node cur = queue.poll();
// 如果cur的next不为null且cur的next没被copy过的话,就new一个出来,建立map中的关联,并入队
if (cur.next != null && !map.containsKey(cur.next)) {
map.put(cur.next, new Node(cur.next.val));
queue.offer(cur.next);
}
// 把cur对应的node的next给连上去
map.get(cur).next = map.get(cur.next);
// 与上面的next类似,copy出random
if (cur.random != null && !map.containsKey(cur.random)) {
map.put(cur.random, new Node(cur.random.val));
queue.offer(cur.random);
}
map.get(cur).random = map.get(cur.random);
}
return map.get(head);
}
}
时间复杂度,空间。
上一篇: SQL注入手工注入常用的语句