剑指offer 复杂链表的复制 bfs 遍历法

思路

整个复杂链表可以看成图

步骤

1. 先用bfs把图遍历一遍, 把每个node备份一份,存到map<Node,Node>里
2. 遍历map, 重建整张图

代码

    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) return null;

        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();

        Queue<RandomListNode> queue = new LinkedList<>();
        queue.offer(pHead);

        // 遍历整个图(这里的链表其实已经算图了)
        while (queue.size() > 0) {
            RandomListNode out = queue.poll();
            if (!map.containsKey(out)) {
                RandomListNode new_node = new RandomListNode(out.label);
                map.put(out, new_node);

                if (!map.containsKey(out.next) && out.next != null) {
                    queue.offer(out.next);
                }

                if (!map.containsKey(out.random) && out.random != null) {
                    queue.offer(out.random);
                }
            }
        }


        // 重建图
        for (RandomListNode node : map.keySet()) {
            // 拿出对应的node
            RandomListNode corres = map.get(node);

            // 按原来的样子连接
            if (node.next != null) {
                RandomListNode next_node = map.get(node.next);
                corres.next = next_node;
            } else {
                corres.next = null;
            }

            if (node.random != null) {
                RandomListNode random_node = map.get(node.random);
                corres.random = random_node;
            } else {
                corres.random = null;
            }
        }
        return map.get(pHead);
    }

复杂度

时间:O(n)
空间:O(n)