题目描述
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
解题思路
- 遍历链表，将每一个节点存入
nodes数组。 - 遍历
nodes数组，创建每一个节点的拷贝并存入copyNodes数组，并将random指向的节点index记录到randomNodeIndex数组。 - 遍历
randomNodeIndex数组，将copyNodes中的每一个节点指向下一个节点，并根据randomNodeIndex的取值将random的指向补齐。
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
final ArrayList<Node> nodes = new ArrayList<>();
final ArrayList<Integer> randomNodeIndex = new ArrayList<>();
final ArrayList<Node> copyNodes = new ArrayList<>();
Node thisNode = head;
while (thisNode != null) {
nodes.add(thisNode);
thisNode = thisNode.next;
}
for (Node node : nodes) {
final Node copyNode = new Node(node.val);
copyNodes.add(copyNode);
if (node.random == null) {
randomNodeIndex.add(null);
continue;
}
for (int i = 0; i < nodes.size(); i++) {
if (node.random == nodes.get(i)) {
randomNodeIndex.add(i);
}
}
}
for (int i = 0; i < randomNodeIndex.size(); i++) {
Node currentNode = copyNodes.get(i);
currentNode.next = i == randomNodeIndex.size() - 1 ? null : copyNodes.get(i + 1);
currentNode.random = randomNodeIndex.get(i) == null ? null : copyNodes.get(randomNodeIndex.get(i));
}
return copyNodes.get(0);
}
}
很显然，我这样的解法很暴力。
