剑指 Offer 35 - 复杂链表的复制
# 📃 题目描述
题目链接:
# 🔔 解题思路
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
// 记录已经复制过的节点,key:原节点, value:复制的节点
Map<Node, Node> copyed = new HashMap<>();
Node newHead = dfs(head, copyed);
return newHead;
}
// dfs 复制 node 链表, 并返回复制后链表的首节点
private Node dfs(Node node, Map<Node, Node> copyed) {
if (node == null) {
return null;
}
if (!copyed.containsKey(node)) {
Node newNode = new Node(node.val);
copyed.put(node, newNode);
// dfs 复制 node.next
newNode.next = dfs(node.next, copyed);
// dfs 复制 node.random
newNode.random = dfs(node.random, copyed);
}
return copyed.get(node);
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10