Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 648b5f2

Browse filesBrowse files
suukiisuukii
committed
Update 142&146
1 parent 68b3a70 commit 648b5f2
Copy full SHA for 648b5f2

File tree

Expand file treeCollapse file tree

3 files changed

+272
-94
lines changed
Filter options
Expand file treeCollapse file tree

3 files changed

+272
-94
lines changed

‎basic/linked-list/09.convert-sorted-list-to-binary-search-tree.md

Copy file name to clipboardExpand all lines: basic/linked-list/09.convert-sorted-list-to-binary-search-tree.md
+3-3Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5,11 +5,11 @@
55
- [方法 1：递归](#方法-1递归)
66
- [思路](#思路)
77
- [复杂度分析](#复杂度分析)
8-
- [代码(JavaScript/C++)](#代码javascriptc)
8+
- [代码(JavaScript/C++/Python)](#代码javascriptcpython)
99
- [方法 2：空间换时间](#方法-2空间换时间)
1010
- [思路](#思路-1)
1111
- [复杂度分析](#复杂度分析-1)
12-
- [代码(JavaScript/C++)](#代码javascriptc-1)
12+
- [代码(JavaScript/C++)](#代码javascriptc)
1313

1414
## 题目描述
1515

@@ -47,7 +47,7 @@
4747
- 时间复杂度：$O(NlogN)$，N 为链表长度。
4848
- 空间复杂度：$O(logN)$，N 为链表长度。
4949

50-
### 代码(JavaScript/C++)
50+
### 代码(JavaScript/C++/Python)
5151

5252
JavaScript Code
5353

‎basic/linked-list/11.linked-list-cycle-ii.md

Copy file name to clipboardExpand all lines: basic/linked-list/11.linked-list-cycle-ii.md
+139-71Lines changed: 139 additions & 71 deletions
Original file line numberDiff line numberDiff line change
@@ -2,20 +2,20 @@
22

33
https://leetcode-cn.com/problems/linked-list-cycle-ii/
44

5-
- [142.环形链表 II](#142dot环形链表-ii)
5+
- [142.环形链表 II](#142环形链表-ii)
66
- [题目描述](#题目描述)
7-
- [方法 1：哈希表标记已遍历节点](#方法-1哈希表标记已遍历节点)
7+
- [方法 1：哈希法](#方法-1哈希法)
88
- [思路](#思路)
99
- [复杂度分析](#复杂度分析)
10-
- [代码](#代码)
10+
- [代码(JavaScript/C++)](#代码javascriptc)
1111
- [方法 2：双指针](#方法-2双指针)
1212
- [思路](#思路-1)
1313
- [复杂度分析](#复杂度分析-1)
14-
- [代码](#代码-1)
14+
- [代码(JavaScript)](#代码javascript)
1515
- [方法 3：双指针 + 数学证明](#方法-3双指针--数学证明)
1616
- [思路](#思路-2)
1717
- [复杂度分析](#复杂度分析-2)
18-
- [代码](#代码-2)
18+
- [代码(JavaScript/C++)](#代码javascriptc-1)
1919

2020
## 题目描述
2121

@@ -34,21 +34,21 @@ https://leetcode-cn.com/problems/linked-list-cycle-ii/
3434
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
3535
```
3636

37-
## 方法 1：哈希表标记已遍历节点
37+
## 方法 1：哈希法
3838

3939
### 思路
4040

41-
1. 从头开始遍历链表并给每个节点增加一个“已遍历”的标记；
42-
2. 如果在遍历过程中遇到了一个“已遍历”的节点，说明这个就是环的入口了；
43-
3. 题目要求不允许修改给定的链表，但我们可以用一个 hashmap 来记录；
44-
4. 由于题目中没有提到节点值是否唯一，也就是说两个不同的节点可能会有相同的值，那仅用节点值作为 hashmap 的 key 是不够的，得用整个节点对象来当 key，所以需要 `Map`。
41+
1. 可以从头开始遍历链表并给每个节点增加一个“已遍历”的标记；
42+
2. 如果在遍历过程中遇到了一个“已遍历”的节点，说明这就是环的入口；
43+
3. 但题目不允许修改给定的链表，所以我们可以用一个额外的 hashmap 来记录；
44+
4. 注意题目中没有提到节点值是否唯一，所以仅用节点值作为 hashmap 的 key 是不够的，需要用到整个节点对象来当 key。
4545

4646
### 复杂度分析
4747

48-
- 时间复杂度：$O(n)$, n 为链表长度。
49-
- 空间复杂度：$O(n)$。
48+
- 时间复杂度：$O(n)$, n 为链表长度。
49+
- 空间复杂度：$O(n)$。
5050

51-
### 代码
51+
### 代码(JavaScript/C++)
5252

5353
JavaScript Code
5454

@@ -66,15 +66,41 @@ JavaScript Code
6666
* @return {ListNode}
6767
*/
6868
var detectCycle = function (head) {
69-
const map = new Map();
69+
const map = new Map();
7070

71-
while (head) {
72-
if (map.has(head)) return head;
73-
map.set(head, true);
74-
head = head.next;
75-
}
71+
while (head) {
72+
if (map.has(head)) return head;
73+
map.set(head, true);
74+
head = head.next;
75+
}
76+
77+
return null;
78+
};
79+
```
7680

77-
return null;
81+
C++ Code
82+
83+
```cpp
84+
/**
85+
* Definition for singly-linked list.
86+
* struct ListNode {
87+
* int val;
88+
* ListNode *next;
89+
* ListNode(int x) : val(x), next(NULL) {}
90+
* };
91+
*/
92+
class Solution {
93+
public:
94+
ListNode *detectCycle(ListNode *head) {
95+
set<ListNode*> seen;
96+
ListNode *cur = head;
97+
while (cur != NULL) {
98+
if (seen.find(cur) != seen.end()) return cur;
99+
seen.insert(cur);
100+
cur = cur->next;
101+
}
102+
return NULL;
103+
}
78104
};
79105
```
80106
@@ -83,19 +109,19 @@ var detectCycle = function (head) {
83109
### 思路
84110
85111
1. 先使用快慢指针确定链表是否有环；
86-
2. 如果链表有环，那快慢指针相遇的点一定是在环上；
87-
3. 接着把一个指针 A 移到链表头部，另一个指针 B 留在环内；
88-
4. 指针 A 开始遍历环外的节点，指针 A 每走一步，指针 B 在环内走一圈；
112+
2. 如果链表有环，那快慢指针相遇的点一定是在环中；
113+
3. 接着把指针 A 移到链表头部，指针 B 留在环内；
114+
4. 指针 A 开始遍历环外的节点，指针 B 遍历环内的节点，指针 A 每走一步，指针 B 在环内走一圈；
89115
5. 如果指针 A 和指针 B 相遇了，说明这个节点就是环的入口。
90116
91117
> 因为环和环外的唯一交点就是环的入口点
92118
93119
### 复杂度分析
94120
95-
- 时间复杂度：$O(n*p)$, n 是环外链表的长度，p 是环的长度。
96-
- 空间复杂度：$O(1)$。
121+
- 时间复杂度：$O(n*p)$, n 是环外链表的长度，p 是环的长度。
122+
- 空间复杂度：$O(1)$。
97123
98-
### 代码
124+
### 代码(JavaScript)
99125
100126
JavaScript Code
101127
@@ -113,31 +139,31 @@ JavaScript Code
113139
* @return {ListNode}
114140
*/
115141
var detectCycle = function (head) {
116-
let slow = head,
117-
fast = head;
118-
// 快慢指针确定有环
119-
while (fast && fast.next) {
120-
slow = slow.next;
121-
fast = fast.next.next;
122-
// 确定有环，开始找环的第一个节点
123-
if (slow === fast) return findConnection(head, fast);
124-
}
125-
return null;
126-
127-
// ******************************************
128-
129-
function findConnection(head, loopNode) {
130-
// p1 走一步，p2 绕环一圈
131-
let p1 = head;
132-
while (true) {
133-
let p2 = loopNode;
134-
while (p2.next !== loopNode && p2.next !== p1) {
135-
p2 = p2.next;
136-
}
137-
if (p2.next === p1) return p1;
138-
p1 = p1.next;
139-
}
142+
let slow = head,
143+
fast = head;
144+
// 快慢指针确定有环
145+
while (fast && fast.next) {
146+
slow = slow.next;
147+
fast = fast.next.next;
148+
// 确定有环，开始找环的第一个节点
149+
if (slow === fast) return findConnection(head, fast);
150+
}
151+
return null;
152+
153+
// ******************************************
154+
155+
function findConnection(head, loopNode) {
156+
// p1 走一步，p2 绕环一圈
157+
let p1 = head;
158+
while (true) {
159+
let p2 = loopNode;
160+
while (p2.next !== loopNode && p2.next !== p1) {
161+
p2 = p2.next;
162+
}
163+
if (p2.next === p1) return p1;
164+
p1 = p1.next;
140165
}
166+
}
141167
};
142168
```
143169

@@ -180,25 +206,31 @@ class Solution(object):
180206

181207
### 思路
182208

183-
先用快慢指针确定链表有环，快慢指针会在环上的某个节点相遇。
209+
先用快慢指针确定链表是否有环，如果是环形链表，快慢指针会在环内的某个节点相遇。
184210

185211
![](https://cdn.jsdelivr.net/gh/suukii/91-days-algorithm/assets/first_node_of_loop_in_linked_list_0.png)
186212

187213
我们分别来看一下两个指针相遇前分别走了多少路程。
188214

189215
**快指针**
190216

191-
假设走到相遇点之前，快指针在环内走了 x 圈，那快指针走过的总路程可以用 `S(fast) = a + x(b + c) + b` 来表示，其中 `(b + c)` 就是环的长度。
217+
假设走到相遇点之前，快指针在环内走了 x 圈，那快指针走过的总路程可以用
218+
219+
`S(fast) = a + x(b + c) + b`
220+
221+
来表示，其中 `(b + c)` 就是环的长度。
192222

193223
![](https://cdn.jsdelivr.net/gh/suukii/91-days-algorithm/assets/first_node_of_loop_in_linked_list_1.png)
194224

195225
**慢指针**
196226

197-
假设走到相遇点之前，慢指针在环内走了 y 圈，同理可得慢指针走过的总路程是 `S(slow) = a + y(b + c) + b`。
227+
假设走到相遇点之前，慢指针在环内走了 y 圈，同理可得慢指针走过的总路程是
228+
229+
`S(slow) = a + y(b + c) + b`
198230

199231
而由于快指针的速度是慢指针速度的 2 倍，所以可得以下方程式：
200232

201-
`S(slow) = 2S(fast)` => `a + x(b + c) + b = 2(a + y(b + c) + b)`
233+
`2S(slow) = S(fast)` => `2(a + x(b + c) + b) = a + y(b + c) + b`
202234

203235
稍微整理一下我们就得到了：
204236

@@ -214,10 +246,10 @@ class Solution(object):
214246

215247
### 复杂度分析
216248

217-
- 时间复杂度：$O(n)$，n 为链表长度。
218-
- 空间复杂度：$O(1)$。
249+
- 时间复杂度：$O(n)$，n 为链表长度。
250+
- 空间复杂度：$O(1)$。
219251

220-
### 代码
252+
### 代码(JavaScript/C++)
221253

222254
JavaScript Code
223255

@@ -235,24 +267,60 @@ JavaScript Code
235267
* @return {ListNode}
236268
*/
237269
var detectCycle = function (head) {
238-
let fast = head,
239-
slow = head;
240-
241-
// 快慢指针确定有环
242-
while (fast && fast.next) {
243-
fast = fast.next.next;
270+
let fast = head,
271+
slow = head;
272+
273+
// 快慢指针确定有环
274+
while (fast && fast.next) {
275+
fast = fast.next.next;
276+
slow = slow.next;
277+
278+
// 确定有环，开始找环的第一个节点
279+
if (fast === slow) {
280+
slow = head;
281+
while (slow !== fast) {
244282
slow = slow.next;
283+
fast = fast.next;
284+
}
285+
return slow;
286+
}
287+
}
288+
return null;
289+
};
290+
```
245291

246-
// 确定有环，开始找环的第一个节点
247-
if (fast === slow) {
248-
slow = head;
249-
while (slow !== fast) {
250-
slow = slow.next;
251-
fast = fast.next;
292+
C++ Code
293+
294+
```cpp
295+
/**
296+
* Definition for singly-linked list.
297+
* struct ListNode {
298+
* int val;
299+
* ListNode *next;
300+
* ListNode(int x) : val(x), next(NULL) {}
301+
* };
302+
*/
303+
class Solution {
304+
public:
305+
ListNode *detectCycle(ListNode *head) {
306+
ListNode *slow = head;
307+
ListNode *fast = head;
308+
309+
while (fast && fast->next) {
310+
slow = slow->next;
311+
fast = fast->next->next;
312+
if (slow == fast) {
313+
fast = head;
314+
while (slow != fast) {
315+
slow = slow->next;
316+
fast = fast->next;
317+
}
318+
return slow;
252319
}
253-
return slow;
254320
}
321+
return NULL;
255322
}
256-
return null;
257323
};
258324
```
325+
326+
更多题解可以访问：[https://github.com/suukii/91-days-algorithm](https://github.com/suukii/91-days-algorithm)

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.