剑指 Offer 35. 复杂链表的复制

题目描述

请实现 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);
    }
}

很显然，我这样的解法很暴力。