今天和大家聊的问题叫做 复制带随机指针的链表，我们先来看题面：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); }
本题还有很多其他的解法，大家都多思考一下 。
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。
