复杂链表的复制

Posted on In Views: Waline: Views: Symbols count in article: 447 Reading time ≈ 1 mins.

题解方法

  • 递归

递归

  • 构建原节点和新节点的映射。
  • 由于当前节点的 next 和 random 可能还未创建，先将当前节点存入 map 中，而后在递归地创建其 next 和 random 节点。
  • 如果当前节点已经被创建，则直接返回新节点。

核心代码

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private Node copy(Node node) {
	if (node == null) {
		return null;
	}
	// 如果该节点已经被复制过，则直接返回
	if (!map.containsKey(node)) {
		Node newNode = new Node(node.val);
		// 先将新节点放入 map 中，再递归复制 next 和 random
		map.put(node, newNode);
		newNode.next = copy(node.next);
		newNode.random = copy(node.random);
	}
	return map.get(node);
}

题目来源

复杂链表的复制 - 力扣（LeetCode）