Skip to content

Commit 88fcd88

Browse files
jaredliwjaredliw
committed
验证，校对
1 parent 4a8c81e commit 88fcd88

14 files changed

+180
-197
lines changed

‎animation-simulation/链表篇/234. 回文链表.md

Lines changed: 21 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,3 @@
1-
2-
31
> 如果阅读时，发现错误，或者动画不可以显示的问题可以添加我微信好友 **[tan45du_one](https://raw.githubusercontent.com/tan45du/tan45du.github.io/master/个人微信.15egrcgqd94w.jpg)** ，备注 github + 题目 + 问题 向我反馈
42
>
53
> 感谢支持，该仓库会一直维护，希望对各位有一丢丢帮助。
@@ -63,7 +61,6 @@ class Solution {
6361
return true;
6462
}
6563
}
66-
6764
```
6865

6966
C++ Code:
@@ -72,18 +69,23 @@ C++ Code:
7269
class Solution {
7370
public:
7471
bool isPalindrome(ListNode* head) {
72+
//这里需要用动态数组，因为我们不知道链表的长度
7573
vector<int> arr;
7674
ListNode* copynode = head;
75+
//将链表的值复制到数组中
7776
while (copynode) {
7877
arr.push_back(copynode->val);
7978
copynode = copynode->next;
8079
}
80+
//双指针遍历数组
8181
int back = 0;
8282
int pro = arr.size() - 1;
8383
while (back < pro) {
84+
//判断两个指针的值是否相等
8485
if (arr[back] != arr[pro]) {
8586
return false;
8687
}
88+
//移动指针
8789
back++;
8890
pro--;
8991
}
@@ -121,7 +123,7 @@ var isPalindrome = function(head) {
121123

122124
Python Code:
123125

124-
```py
126+
```python
125127
class Solution:
126128
def isPalindrome(self, head: ListNode) -> bool:
127129
arr = []
@@ -145,7 +147,7 @@ class Solution:
145147

146148
这个方法可以直接通过，但是这个方法需要辅助数组，那我们还有其他更好的方法吗？
147149

148-
双指针翻转链表法
150+
**双指针翻转链表法**
149151

150152
在上个题目中我们知道了如何找到链表的中间节点，那我们可以在找到中间节点之后，对后半部分进行翻转，翻转之后，重新遍历前半部分和后半部分进行判断是否为回文。
151153

@@ -165,25 +167,25 @@ class Solution {
165167
}
166168
//找到中间节点，也就是翻转的头节点,这个在昨天的题目中讲到
167169
//但是今天和昨天有一些不一样的地方就是，如果有两个中间节点返回第一个，昨天的题目是第二个
168-
ListNode midenode = searchmidnode(head);
170+
ListNode midnode = searchmidnode(head);
169171
//原地翻转链表，需要两个辅助指针。这个也是面试题目，大家可以做一下
170172
//这里我们用的是midnode.next需要注意，因为我们找到的是中点，但是我们翻转的是后半部分
171-
ListNode backhalf = reverse(midenode.next);
173+
ListNode backhalf = reverse(midnode.next);
172174
//遍历两部分链表，判断值是否相等
173175
ListNode p1 = head;
174176
ListNode p2 = backhalf;
175177
while (p2 != null) {
176178
if (p1.val != p2.val) {
177179
//若要还原，记得这里也要reverse
178-
midenode.next = reverse(backhalf);
180+
midnode.next = reverse(backhalf);
179181
return false;
180182
}
181183
p1 = p1.next;
182184
p2 = p2.next;
183185
}
184186
//还原链表并返回结果，这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
185187
//当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
186-
midenode.next = reverse(backhalf);
188+
midnode.next = reverse(backhalf);
187189
return true;
188190
}
189191
//找到中点
@@ -222,25 +224,25 @@ public:
222224
}
223225
//找到中间节点，也就是翻转的头节点，这个在昨天的题目中讲到
224226
//但是今天和昨天有一些不一样的地方就是，如果有两个中间节点返回第一个，昨天的题目是第二个
225-
ListNode * midenode = searchmidnode(head);
227+
ListNode * midnode = searchmidnode(head);
226228
//原地翻转链表，需要两个辅助指针。这个也是面试题目，大家可以做一下
227229
//这里我们用的是midnode->next需要注意，因为我们找到的是中点，但是我们翻转的是后半部分
228-
ListNode * backhalf = reverse(midenode->next);
230+
ListNode * backhalf = reverse(midnode->next);
229231
//遍历两部分链表，判断值是否相等
230232
ListNode * p1 = head;
231233
ListNode * p2 = backhalf;
232234
while (p2 != nullptr) {
233235
if (p1->val != p2->val) {
234236
//若要还原，记得这里也要reverse
235-
midenode.next = reverse(backhalf);
237+
midnode->next = reverse(backhalf);
236238
return false;
237239
}
238240
p1 = p1->next;
239241
p2 = p2->next;
240242
}
241243
//还原链表并返回结果，这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
242244
//当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
243-
midenode->next = reverse(backhalf);
245+
midnode->next = reverse(backhalf);
244246
return true;
245247
}
246248
//找到中间的部分
@@ -277,25 +279,25 @@ var isPalindrome = function(head) {
277279
}
278280
//找到中间节点，也就是翻转的头节点，这个在昨天的题目中讲到
279281
//但是今天和昨天有一些不一样的地方就是，如果有两个中间节点返回第一个，昨天的题目是第二个
280-
let midenode = searchmidnode(head);
282+
let midnode = searchmidnode(head);
281283
//原地翻转链表，需要两个辅助指针。这个也是面试题目，大家可以做一下
282284
//这里我们用的是midnode.next需要注意，因为我们找到的是中点，但是我们翻转的是后半部分
283-
let backhalf = reverse(midenode.next);
285+
let backhalf = reverse(midnode.next);
284286
//遍历两部分链表，判断值是否相等
285287
let p1 = head;
286288
let p2 = backhalf;
287289
while (p2 != null) {
288290
if (p1.val != p2.val) {
289291
//若要还原，记得这里也要reverse
290-
midenode.next = reverse(backhalf);
292+
midnode.next = reverse(backhalf);
291293
return false;
292294
}
293295
p1 = p1.next;
294296
p2 = p2.next;
295297
}
296298
//还原链表并返回结果，这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
297299
//当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
298-
midenode.next = reverse(backhalf);
300+
midnode.next = reverse(backhalf);
299301
return true;
300302
};
301303
@@ -326,7 +328,7 @@ var reverse = function(slow) {
326328

327329
Python Code:
328330

329-
```py
331+
```python
330332
class Solution:
331333
def isPalindrome(self, head: ListNode) -> bool:
332334
if head is None or head.next is None:
@@ -344,12 +346,11 @@ class Solution:
344346
if p1.val != p2.val:
345347
# 若要还原，记得这里也要reverse
346348
midnode.next = self.reverse(backhalf)
347-
print(head)
348349
return False
349350
p1 = p1.next
350351
p2 = p2.next
351352
# 还原链表并返回结果，这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
352-
当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
353+
# 当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
353354
midnode.next = self.reverse(backhalf)
354355
return True
355356

‎animation-simulation/链表篇/leetcode141环形链表.md

Lines changed: 21 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@
1212

1313
> 给定一个链表，判断链表中是否有环。pos代表环的入口，若为-1，则代表无环。
1414
>
15-
> 如果链表中存在环，则返回 true 。 否则，返回 false 。
15+
> 如果链表中存在环，则返回 true 。否则，返回 false 。
1616
1717
示例1：
1818

@@ -56,22 +56,6 @@ public class Solution {
5656
}
5757
```
5858

59-
JS Code:
60-
```javascript
61-
var hasCycle = function(head) {
62-
let fast = head;
63-
let slow = head;
64-
while (fast && fast.next) {
65-
fast = fast.next.next;
66-
slow = slow.next;
67-
if (fast === slow) {
68-
return true;
69-
}
70-
}
71-
return false;
72-
};
73-
```
74-
7559
C++ Code:
7660

7761
```cpp
@@ -92,17 +76,34 @@ public:
9276
};
9377
```
9478
79+
JS Code:
80+
81+
```javascript
82+
var hasCycle = function(head) {
83+
let fast = head;
84+
let slow = head;
85+
while (fast && fast.next) {
86+
fast = fast.next.next;
87+
slow = slow.next;
88+
if (fast === slow) {
89+
return true;
90+
}
91+
}
92+
return false;
93+
};
94+
```
95+
9596
Python Code:
9697

97-
```py
98+
```python
9899
class Solution:
99100
def hasCycle(self, head: ListNode) -> bool:
100101
fast = head
101102
slow = head
102103
while fast and fast.next:
103104
fast = fast.next.next
104-
low = low.next
105-
if fast == low:
105+
slow = slow.next
106+
if fast == slow:
106107
return True
107108
return False
108109
```

‎animation-simulation/链表篇/leetcode142环形链表2.md

Lines changed: 12 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -18,35 +18,7 @@
1818

1919
我们可以这样假设，两个孩子在操场顺时针跑步，一个跑的快，一个跑的慢，跑的快的那个孩子总会追上跑的慢的孩子。
2020

21-
环形链表：
22-
23-
```java
24-
public class Solution {
25-
public boolean hasCycle(ListNode head) {
26-
//特殊情况，无节点或只有一个节点的情况
27-
if(head == null || head.next == null){
28-
return false;
29-
}
30-
//设置快慢指针
31-
ListNode pro = head.next;
32-
ListNode last = head;
33-
//循环条件
34-
while( pro != null && pro.next!=null){
35-
pro=pro.next.next;
36-
last=last.next;
37-
//两指针相遇
38-
if(pro == last){
39-
return true;
40-
}
41-
}
42-
//循环结束，指针没有相遇，说明没有环。相当于快指针遍历了一遍链表
43-
return false;
44-
45-
}
46-
}
47-
```
48-
49-
其它语言的代码请参考[这里](https://github.com/chefyuan/algorithm-base/blob/main/animation-simulation/%E9%93%BE%E8%A1%A8%E7%AF%87/leetcode141%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8.md)。
21+
代码请参考[【动画模拟】leetcode 141 环形链表](https://github.com/chefyuan/algorithm-base/blob/main/animation-simulation/%E9%93%BE%E8%A1%A8%E7%AF%87/leetcode141%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8.md)。
5022

5123
判断链表是不是含有环很简单，但是我们想找到环的入口可能就没有那么容易了。（入口则为下图绿色节点）
5224

@@ -100,11 +72,15 @@ public:
10072
ListNode *detectCycle(ListNode *head) {
10173
if (head == nullptr) return head;
10274
if (head->next == nullptr) return head->next;
75+
//创建新的HashSet，用于保存节点
10376
set<ListNode *> hash;
77+
//遍历链表
10478
while (head != nullptr) {
79+
//判断哈希表中是否含有某节点，没有则保存，含有则返回该节点
10580
if (hash.count(head)) {
10681
return head;
10782
}
83+
//不含有，则进行保存，并移动指针
10884
hash.insert(head);
10985
head = head->next;
11086
}
@@ -137,7 +113,7 @@ var detectCycle = function(head) {
137113

138114
Python Code:
139115

140-
```py
116+
```python
141117
class Solution:
142118
def detectCycle(self, head: ListNode) -> ListNode:
143119
if head is None:
@@ -253,17 +229,22 @@ JS Code:
253229
254230
```js
255231
var detectCycle = function(head) {
232+
//快慢指针
256233
let fast = head;
257234
let slow = head;
235+
//设置循环条件
258236
while (fast && fast.next) {
259237
fast = fast.next.next;
260238
slow = slow.next;
239+
//相遇
261240
if (fast == slow) {
262241
let newptr = head;
242+
//设置一个新的指针，从头节点出发，慢指针速度为1，所以可以使用慢指针从相遇点出发
263243
while (newptr != slow) {
264244
slow = slow.next;
265245
newptr = newptr.next;
266246
}
247+
//在环入口相遇
267248
return slow;
268249
}
269250
}
@@ -273,7 +254,7 @@ var detectCycle = function(head) {
273254

274255
Python Code:
275256

276-
```py
257+
```python
277258
class Solution:
278259
def detectCycle(self, head: ListNode) -> ListNode:
279260
# 快慢指针

‎animation-simulation/链表篇/leetcode147对链表进行插入排序.md

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88

99
[【绘图解析】链表详解](https://github.com/chefyuan/algorithm-base/blob/main/animation-simulation/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/%E5%85%B3%E4%BA%8E%E9%93%BE%E8%A1%A8%E7%9A%84%E9%82%A3%E4%BA%9B%E4%BA%8B.md)
1010

11-
另外大家如果忘记了[【动画模拟】插入排序](https://github.com/chefyuan/algorithm-base/blob/main/animation-simulation/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F.md)和[【动画模拟】归并排序](https://github.com/chefyuan/algorithm-base/blob/main/animation-simulation/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F.md)思想的话，可以先复习一下，不然这两道题目会看的云里雾里。
11+
另外大家如果忘记了[【动画模拟】插入排序](https://github.com/chefyuan/algorithm-base/blob/main/animation-simulation/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F.md)和[【动画模拟】归并排序](https://github.com/chefyuan/algorithm-base/blob/main/animation-simulation/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F.md)思想的话，可以先复习一下，不然这两道题目会看得云里雾里。
1212

1313
#### [147. 对链表进行插入排序](https://leetcode-cn.com/problems/insertion-sort-list/)
1414

@@ -30,7 +30,7 @@
3030

3131
我们的指针在数组时，可以随意的前后移动，将指针指向值和新元素的值比较后，将新元素插入到合适的位置。
3232

33-
我们知道链表查询元素的时间复杂度为 O（n）,我们只能够通过遍历链表查询元素。
33+
我们知道链表查询元素的时间复杂度为O(n)，我们只能够通过遍历链表查询元素。
3434

3535
那么我们怎么才能将新元素放到合适的位置呢？见下图。
3636

@@ -68,7 +68,7 @@
6868

6969
我们想要将 3 插入到 2 和 4 的中间，此时我们三个指针分别指向 2，4，3。
7070

71-
我们共分 4 步，来完成这个操作，见下图
71+
我们共分 4 步，来完成这个操作，见下图。
7272

7373
![](https://cdn.jsdelivr.net/gh/tan45du/photobed@master/44444444.29mvcvs4yrms.png)
7474

@@ -143,9 +143,9 @@ public:
143143
continue;
144144
}
145145
//开始出发，查找新元素的合适位置
146-
temphead = dummyNode;
146+
ListNode * temphead = dummyNode;
147147
while (temphead->next->val <= pre->val) {
148-
ListNode * temphead = temphead->next;
148+
temphead = temphead->next;
149149
}
150150
//此时我们已经找到了合适位置，我们需要进行插入，大家可以画一画
151151
last->next = pre->next;
@@ -195,7 +195,7 @@ var insertionSortList = function(head) {
195195

196196
Python Code:
197197

198-
```py
198+
```python
199199
class Solution:
200200
def insertionSortList(self, head: ListNode) -> ListNode:
201201
if head is None or head.next is None:

0 commit comments

Comments
 (0)