LeetCode刷题实战138：复制带随机指针的链表 / 开普饭

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 复制带随机指针的链表，我们先来看题面：

https://leetcode-cn.com/problems/copy-list-with-random-pointer/

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val

random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

题意

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。

random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

样例

解题

这题可以利用 HashMap 来实现。

遍历第一遍链表，我们不考虑链表之间的相互关系，仅仅生成所有节点，然后把它存到 HashMap 中，val 作为 key，Node 作为 value。

遍历第二遍链表，将之前生成的节点取出来，更新它们的 next 和 random 指针。

public Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    HashMap<Node, Node> map = new HashMap<>();
    Node h = head;
    while (h != null) {
        Node t = new Node(h.val);
        map.put(h, t);
        h = h.next;
    }
    h = head;
    while (h != null) {
        if (h.next != null) {
            map.get(h).next = map.get(h.next);
        }
        if (h.random != null) {
            map.get(h).random = map.get(h.random);
        }
        h = h.next;
    }
    return map.get(head);
}