1+ // 138. 复制带随机指针的链表
2+
3+
4+ /*
5+ // Definition for a Node.
6+ class Node {
7+ int val;
8+ Node next;
9+ Node random;
10+
11+ public Node(int val) {
12+ this.val = val;
13+ this.next = null;
14+ this.random = null;
15+ }
16+ }
17+ */
18+
19+
20+ /*
21+ 递归：
22+ 1、成员变量 map 存放新旧节点的映射关系 {原节点：新节点}
23+ 2、定义递归函数
24+ 1）方法功能：入参是一个节点，map存在则直接获取返回，否则拷贝该节点并存入map中，返回拷贝节点
25+ 2）终止条件：节点为空时返回空
26+ 3）返回结果：返回该节点的拷贝节点
27+ 4）递归逻辑：拷贝节点的next指针和random指针需要连接新的拷贝节点，因此调用同样的方法，传入原节点的下一节点和随机节点进行拷贝并返回
28+ */
29+ class Solution {
30+ private Map <Node , Node > map = new HashMap <>();
31+
32+ public Node copyRandomList (Node head ) {
33+ if (head == null ) {
34+ return null ;
35+ }
36+ if (map .containsKey (head )) {
37+ return map .get (head );
38+ }
39+ Node newNode = new Node (head .val );
40+ map .put (head , newNode );
41+ newNode .next = copyRandomList (head .next );
42+ newNode .random = copyRandomList (head .random );
43+ return newNode ;
44+ }
45+ }
46+
47+
48+ /*
49+ 迭代：
50+ 1、在每个原节点后面创建一个新节点
51+ 2、设置新节点的随机节点
52+ 3、将两个链表分离
53+
54+ 1 → 2 → 3
55+ =====================
56+ 1 → 1 → 2 → 2 → 3 → 3
57+ =====================
58+ ------------
59+ ↑ ↓
60+ 1 1 → 2 → 2 → 3 → 3
61+ ↗ cur p
62+ 0
63+
64+ */
65+ class Solution {
66+ public Node copyRandomList (Node head ) {
67+ Node p = head ;
68+ while (p != null ) {
69+ Node newNode = new Node (p .val );
70+ newNode .next = p .next ;
71+ p .next = newNode ;
72+ p = p .next .next ;
73+ }
74+
75+ p = head ;
76+ while (p != null ) {
77+ if (p .random != null ) {
78+ p .next .random = p .random .next ;
79+ }
80+ p = p .next .next ;
81+ }
82+
83+ p = head ;
84+ Node root = new Node (0 );
85+ Node cur = root ;
86+ while (p != null ) {
87+ cur .next = p .next ;
88+ cur = cur .next ;
89+ p .next = p .next .next ;
90+ p = p .next ;
91+ }
92+ return root .next ;
93+ }
94+ }
95+
96+
97+ /*
98+ 哈希表：
99+ 1、创建一个哈希表，再遍历原链表，遍历的同时再不断创建新节点，将原节点作为key，新节点作为value放入哈希表中，原节点和新节点是一一对应的关系，即
100+ map.get(原节点)，得到的就是对应的 新节点
101+ map.get(原节点.next)，得到的就是对应的 新节点.next
102+ map.get(原节点.random)，得到的就是对应的 新节点.random
103+ 2、再遍历原链表，设置新链表的next和random指针
104+ 新节点.next -> map.get(原节点.next)
105+ 新节点.random -> map.get(原节点.random)
106+ */
107+ class Solution {
108+ public Node copyRandomList (Node head ) {
109+ Map <Node , Node > map = new HashMap <>();
110+ Node p = head ;
111+ while (p != null ) {
112+ Node newNode = new Node (p .val );
113+ map .put (p , newNode );
114+ p = p .next ;
115+ }
116+ p = head ;
117+ while (p != null ) {
118+ Node newNode = map .get (p );
119+ if (p .next != null ) {
120+ newNode .next = map .get (p .next );
121+ }
122+ if (p .random != null ) {
123+ newNode .random = map .get (p .random );
124+ }
125+ p = p .next ;
126+ }
127+ return map .get (head );
128+ }
129+ }
0 commit comments