1. 题目
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
2. 示例
示例1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
提示：
-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000
3. 题解
本题给出了两种解题思路：
-
HashMap
- 建立Hash表，key为原节点，value为新节点。
- 在Hash表中遍历key，就可以不断的获取新节点: map.get(cur)。让其next指向map.get(cur.next)节点即可，同样的，让random指向map.get(cur.random)即可。
- 返回map.get(head)就是返回的新链表的头结点。
-
拼接+拆分
- 需要遍历三次
- 第一次遍历建立拼接链表：原节点1->新节点1->原节点2->新节点2，这样的拼接链表。此时还未引入random。
- 第二次遍历建立random指向：始终存在一个顺序，就是新节点的next一定在原节点中next指向的next节点的后面，新节点的random一定在原节点random指向的andom节点的后面。
- 第三次遍历拆分拼接年链表
4. 实现
4.1 HashMap
1 public class CopyRandomList35 {
2 // HashMap
3 public Node copyRandomListA(Node head) {
4 if(head == null) return null;
5 Node cur = head;
6 // HashMap<Key, value>，key：原节点，value:新节点。
7 Map<Node, Node> map = new HashMap<>();
8 // 遍历各节点，简历“原节点->新节点”的Map映射
9 while (cur != null) {
10 map.put(cur, new Node(cur.val));
11 cur = cur.next;
12 }
13 cur = head;
14 // 遍历map，建立新链表
15 while (cur != null) {
16 map.get(cur).next = map.get(cur.next);
17 map.get(cur).random = map.get(cur.random);
18 cur = cur.next;
19 }
20 // 返回新链表的头结点
21 return map.get(head);
22 }
23 }
4.2 拼接+拆分
1 public class CopyRandomList35 {
2 // 拼接+拆分
3 public Node copyRandomListB(Node head) {
4 // 如果为空，直接返回
5 if(head == null) return null;
6 Node cur = head;
7 // 1. 第一轮遍历，建立只包含next的拼接链表
8 // 新链表结构：原节点1->新节点1->原节点2->新节点2
9 while (cur != null) {
10 Node temp = new Node(cur.val);
11 temp.next = cur.next;
12 cur.next = temp;
13 cur = temp.next;
14 }
15 // 2. 第二轮遍历,建立random指向
16 cur = head;
17 while (cur != null) {
18 // 原节点的random不为Null，说明存在，那么新节点的random需要指向原节点的random的下一个节点。
19 if(cur.random != null) {
20 cur.next.random = cur.random.next;
21 }
22 cur = cur.next.next;
23 }
24 cur = head.next;
25 Node pre = head, res = head.next;
26 // 3. 第三轮遍历，拆分链表
27 while(cur.next != null) {
28 pre.next = pre.next.next;
29 cur.next = cur.next.next;
30 pre = pre.next;
31 cur = cur.next;
32 }
33 pre.next = null;
34 return res;
35 }
36 }
5. 结语
努力去爱周围的每一个人，付出，不一定有收获，但是不付出就一定没有收获！ 给街头卖艺的人零钱，不和深夜还在摆摊的小贩讨价还价。愿我的博客对你有所帮助(*^▽^*)(*^▽^*)！
如果客官喜欢小生的园子，记得关注小生哟，小生会持续更新(#^.^#)(#^.^#)。