10
10
11
11
今天给大家带来一个不是那么难的题目,这个题目的解答方法很多,只要能AC的就是好方法,虽然题目不是特别难但是也是剑指offer上的经典题目所以大家要记得打卡呀。
12
12
13
- 然后今天我们的链表板块就算结束啦。周末的时候我会对链表的题目做一个总结,俗话说温故而知新嘛。好啦废话不多说,我们一起来看一下今天的题目吧
13
+ 然后今天我们的链表板块就算结束啦。周末的时候我会对链表的题目做一个总结,俗话说温故而知新嘛。好啦废话不多说,我们一起来看一下今天的题目吧!
14
14
15
15
题目描述:
16
16
@@ -41,16 +41,19 @@ public class Solution {
41
41
ListNode tempb = headB;
42
42
// 定义Hashset
43
43
HashSet<ListNode > arr = new HashSet<ListNode > ();
44
+ // 遍历链表A,将所有值都存到arr中
44
45
while (tempa != null ) {
45
46
arr. add(tempa);
46
47
tempa = tempa. next;
47
48
}
49
+ // 遍历列表B,如果发现某个结点已在arr中则直接返回该节点
48
50
while (tempb != null ) {
49
51
if (arr. contains(tempb)) {
50
52
return tempb;
51
53
}
52
54
tempb = tempb. next;
53
55
}
56
+ // 若上方没有返回,此刻tempb为null
54
57
return tempb;
55
58
56
59
}
@@ -67,21 +70,73 @@ public:
67
70
ListNode * tempb = headB;
68
71
//定义Hashset
69
72
set <ListNode * > arr;
73
+ //遍历链表A,将所有值都存到arr中
70
74
while (tempa != nullptr) {
71
75
arr.insert(tempa);
72
76
tempa = tempa->next;
73
77
}
78
+ //遍历列表B,如果发现某个结点已在arr中则直接返回该节点
74
79
while (tempb != nullptr) {
75
80
if (arr.find(tempb) != arr.end()) {
76
81
return tempb;
77
82
}
78
83
tempb = tempb->next;
79
84
}
85
+ //若上方没有返回,此刻tempb为null
80
86
return tempb;
81
87
}
82
88
};
83
89
```
84
90
91
+ JS Code:
92
+
93
+ ```js
94
+ var getIntersectionNode = function(headA, headB) {
95
+ let tempa = headA;
96
+ let tempb = headB;
97
+ //定义Hashset
98
+ let arr = new Set();
99
+ //遍历链表A,将所有值都存到arr中
100
+ while (tempa) {
101
+ arr.add(tempa);
102
+ tempa = tempa.next;
103
+ }
104
+ //遍历列表B,如果发现某个结点已在arr中则直接返回该节点
105
+ while (tempb) {
106
+ if (arr.has(tempb)) {
107
+ return tempb;
108
+ }
109
+ tempb = tempb.next;
110
+ }
111
+ //若上方没有返回,此刻tempb为null
112
+ return tempb;
113
+ };
114
+ ```
115
+
116
+ Python Code:
117
+
118
+ ``` py
119
+ class Solution :
120
+ def getIntersectionNode (self , headA : ListNode, headB : ListNode) -> ListNode:
121
+ tempa = headA
122
+ tempb = headB
123
+ # 定义Hashset
124
+ arr = set ()
125
+ # 遍历链表A,将所有值都存到arr中
126
+ while tempa is not None :
127
+ arr.add(tempa)
128
+ tempa = tempa.next
129
+ # 遍历列表B,如果发现某个结点已在arr中则直接返回该节点
130
+ while tempb is not None :
131
+ if tempb in arr:
132
+ return tempb
133
+ tempb = tempb.next
134
+ # 若上方没有返回,此刻tempb为null
135
+ return tempb
136
+ ```
137
+
138
+
139
+
85
140
下面这个方法比较巧妙,不是特别容易想到,大家可以自己实现一下,这个方法也是利用我们的双指针思想。
86
141
87
142
下面我们直接看动图吧,特别直观,一下就可以搞懂。
@@ -108,7 +163,7 @@ public class Solution {
108
163
tempa = tempa != null ? tempa. next: headB;
109
164
tempb = tempb != null ? tempb. next: headA;
110
165
}
111
- return tempa;
166
+ return tempa;// 返回tempb也行
112
167
}
113
168
}
114
169
```
@@ -124,15 +179,48 @@ public:
124
179
ListNode * tempb = headB;
125
180
//循环
126
181
while (tempa != tempb) {
127
- //如果不为空就指针下移,为空就跳到另一链表的头部
182
+ //如果不为空就指针下移,为空就跳到另一链表的头部
128
183
tempa = tempa != nullptr ? tempa->next: headB;
129
184
tempb = tempb != nullptr ? tempb->next: headA;
130
185
}
131
- return tempa;
186
+ return tempa;//返回tempb也行
187
+ }
188
+ };
189
+ ```
190
+
191
+ JS Code:
192
+
193
+ ```js
194
+ var getIntersectionNode = function(headA, headB) {
195
+ //定义两个节点
196
+ let tempa = headA;
197
+ let tempb = headB;
198
+ //循环
199
+ while (tempa != tempb) {
200
+ //如果不为空就指针下移,为空就跳到另一链表的头部
201
+ tempa = tempa != null ? tempa.next: headB;
202
+ tempb = tempb != null ? tempb.next: headA;
132
203
}
204
+ return tempa;//返回tempb也行
133
205
};
134
206
```
135
207
208
+ Python Code:
209
+
210
+ ``` py
211
+ class Solution :
212
+ def getIntersectionNode (self , headA : ListNode, headB : ListNode) -> ListNode:
213
+ # 定义两个节点
214
+ tempa = headA
215
+ tempb = headB
216
+ # 循环
217
+ while tempa is not tempb:
218
+ # 如果不为空就指针下移,为空就跳到另一链表的头部
219
+ tempa = tempa.next if tempa is not None else headB
220
+ tempb = tempb.next if tempb is not None else headA
221
+ return tempa # 返回tempb也行
222
+ ```
223
+
136
224
好啦,链表的题目就结束啦,希望大家能有所收获,下周就要更新新的题型啦,继续坚持,肯定会有收获的。
137
225
138
226
0 commit comments