Movatterモバイル変換

[0]ホーム
URL:

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

 Sign up
Appearance settings

Commitcd5daa6

Browse files
committed
Updated format.
1 parent690427c commitcd5daa6

6 files changed

+157
-115
lines changed

‎en/1-1000/160-intersection-of-two-linked-lists.md

Lines changed: 40 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -36,52 +36,63 @@ The test cases are generated such that there are **no cycles** anywhere in the e
3636
###[Constraints]
3737
- The number of nodes of`listA` is in the`m`.
3838
- The number of nodes of`listB` is in the`n`.
39-
-`1 <= m, n <= 3 *10000`
40-
-`1 <= Node.val <=100000`
39+
-`1 <= m, n <= 3 *10^4`
40+
-`1 <= Node.val <=10^5`
4141

4242
**Follow up**: Could you write a solution that runs in`O(m + n)` time and use only`O(1)` memory?
4343

4444
##Intuition
45+
This is a typical "encounter" problem, and it is best to transform it into a real-life scenario to enhance understanding.
46+
47+
Suppose you are A, and you are pursuing B. The destination is school. On the way to school, the distance at the back is what you both have to go through, and the distance at the front is for each of you to go your own way. The node spacing is assumed to be one kilometer.
48+
49+
Now, one morning, you both finished breakfast at the same time and are going to ride your bike to school. And you have a goal: to meet B and chat with him/her for a few words. What will you do? (Take Example 1 as an example)
50+
51+
You must first calculate how many kilometers her home is farther from the school than your home, and then wait for her to walk these kilometers before setting off. As long as you have the same speed, you will definitely meet, and the node where you meet is the answer.
52+
4553
1. First calculate the number of nodes in the two linked lists A and B. The number of nodes in linked list A is`node_count_a`, and the number of nodes in linked list B is`node_count_b`.
4654
2. If`node_count_b > node_count_a`, then perform`node = node.next` for`node_count_b - node_count_a` times on linked list B.
4755
3. At this time, repeat`node = node.next` on the two linked lists until the same node is found or one of the linked lists has reached the end.
4856

4957
##Steps
5058
1. First calculate the number of nodes in the two linked lists A and B. The number of nodes in linked list A is`node_count_a`, and the number of nodes in linked list B is`node_count_b`.
51-
```python
52-
node_count_a=0
53-
node_count_b=0
5459

55-
node= headA
56-
while node:
57-
node_count_a+=1
58-
node= node.next
59-
```
60+
```python
61+
node_count_a = 0
62+
node_count_b = 0
63+
64+
node = headA
65+
while node:
66+
node_count_a += 1
67+
node = node.next
68+
```
6069

6170
2. If`node_count_b > node_count_a`, then perform`node = node.next` for`node_count_b - node_count_a` times on linked list B.
62-
```python
63-
bigger= headA
64-
smaller= headB
6571

66-
if node_count_b> node_count_a:
67-
bigger= headB
68-
smaller= headA
69-
70-
for _inrange(abs(node_count_b- node_count_a)):
71-
bigger= bigger.next
72-
```
72+
```python
73+
bigger = headA
74+
smaller = headB
75+
76+
if node_count_b > node_count_a:
77+
bigger = headB
78+
smaller = headA
79+
80+
for _ in range(abs(node_count_b - node_count_a)):
81+
bigger = bigger.next
82+
```
7383

7484
3. At this time, repeat`node = node.next` on the two linked lists until the same node is found or one of the linked lists has reached the end.
75-
```python
76-
while biggerand smaller:
77-
if bigger== smaller:
78-
return bigger
7985

80-
bigger= bigger.next
81-
smaller= smaller.next
82-
83-
returnNone
84-
```
86+
```python
87+
while bigger and smaller:
88+
if bigger == smaller:
89+
return bigger
90+
91+
bigger = bigger.next
92+
smaller = smaller.next
93+
94+
return None
95+
```
8596

8697
##Complexity
8798
* Time:`O(m + n)`.

‎en/1-1000/203-remove-linked-list-elements.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -237,7 +237,7 @@ def remove_elements(head, val)
237237
dummy_head.next= head
238238
node= dummy_head
239239

240-
while!node.next.nil?
240+
untilnode.next.nil?
241241
if node.next.val== val
242242
node.next= node.next.next
243243
else

‎en/1-1000/206-reverse-linked-list.md

Lines changed: 39 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -28,45 +28,55 @@ Given the `head` of a singly linked list, reverse the list, and return _the reve
2828
-`-5000 <= Node.val <= 5000`
2929

3030
##Intuition
31-
1. To solve this problem, we only need to define**two** variables:`current` and`previous`.
32-
2.`current.next = previous` is the inversion.
33-
3. The loop condition should be`while (current != null)` instead of`while (current.next != null)`, because the operation to be performed is`current.next = previous`.
31+
1. To solve this problem, we only need to define**two** variables:`current` and`previous`. How do we inverse two node?
32+
33+
<details>
34+
<summary>
35+
Click to view the answer.
36+
</summary>
37+
<p>`current.next = previous` is the inversion.</p>
38+
</details>
39+
40+
2. The loop condition should be`while (current != null)` instead of`while (current.next != null)`, because the operation to be performed is`current.next = previous`.
3441

3542
##Steps
3643
1. Traverse all nodes.
37-
```javascript
38-
previous=null
39-
current= head
4044

41-
while (current!=null) {
42-
current=current.next
43-
}
44-
```
45+
```javascript
46+
previous = null
47+
current = head
48+
49+
while (current != null) {
50+
current = current.next
51+
}
52+
```
4553

4654
2. Add`current.next = previous`.
47-
```javascript
48-
previous=null
49-
current= head
5055

51-
while (current!=null) {
52-
tempNext=current.next
53-
current.next= previous
54-
current= tempNext
55-
}
56-
```
56+
```javascript
57+
previous = null
58+
current = head
59+
60+
while (current != null) {
61+
tempNext = current.next
62+
current.next = previous
63+
current = tempNext
64+
}
65+
```
5766

5867
3.`previous` is always`null`, we need to change it:`previous = current`.
59-
```javascript
60-
previous=null
61-
current= head
6268

63-
while (current!=null) {
64-
tempNext=current.next
65-
current.next= previous
66-
previous= current
67-
current= tempNext
68-
}
69-
```
69+
```javascript
70+
previous = null
71+
current = head
72+
73+
while (current != null) {
74+
tempNext = current.next
75+
current.next = previous
76+
previous = current
77+
current = tempNext
78+
}
79+
```
7080

7181
##Complexity
7282
* Time:`O(n)`.

‎zh/1-1000/160-intersection-of-two-linked-lists.md

Lines changed: 38 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -42,46 +42,57 @@
4242
**进阶**：你能否设计一个时间复杂度`O(m + n)` 、仅用`O(1)` 内存的解决方案？
4343

4444
##思路
45+
这是一个典型的“相遇”问题，最好转化为现实的场景去加强理解。
46+
47+
假设你是A，B是你追求的对象，终点是学校。在上学的路上，靠后面的路程是你们都要经过的，靠前面的路程是各走各的。节点间距假定为一公里。
48+
49+
现在，某个早晨，你们同时都吃完了早饭，要骑车去学校了。而你有个目标：和B相遇，聊上几句，你会怎么做？(以示例一为例)
50+
51+
你一定是先测算出她家比你家到学校远多少公里，然后**等她走完这些公里后，再出发**。只要你们速度相同，就一定能相遇，而相遇的节点就是答案。
52+
4553
1. 先把A, B两个链表的节点数计算出来。链表A的节点数为`node_count_a`，链表B的节点数为`node_count_b`。
4654
2. 假如`node_count_b > node_count_a`，那么对链表B做`node_count_b - node_count_a`次`node = node.next` 操作。
4755
3. 这时，两个链表同时重复进行`node = node.next`操作，直到找到相同的节点或者其中一个链表已经到尾部。
4856

4957
##步骤
5058
1. 先把A, B两个链表的节点数计算出来。链表A的节点数为`node_count_a`，链表B的节点数为`node_count_b`。
51-
```python
52-
node_count_a=0
53-
node_count_b=0
5459

55-
node= headA
56-
while node:
57-
node_count_a+=1
58-
node= node.next
59-
```
60+
```python
61+
node_count_a = 0
62+
node_count_b = 0
63+
64+
node = headA
65+
while node:
66+
node_count_a += 1
67+
node = node.next
68+
```
6069

6170
2. 假如`node_count_b > node_count_a`，那么对链表B做`node_count_b - node_count_a`次`node = node.next` 操作。
62-
```python
63-
bigger= headA
64-
smaller= headB
6571

66-
if node_count_b> node_count_a:
67-
bigger= headB
68-
smaller= headA
69-
70-
for _inrange(abs(node_count_b- node_count_a)):
71-
bigger= bigger.next
72-
```
72+
```python
73+
bigger = headA
74+
smaller = headB
75+
76+
if node_count_b > node_count_a:
77+
bigger = headB
78+
smaller = headA
79+
80+
for _ in range(abs(node_count_b - node_count_a)):
81+
bigger = bigger.next
82+
```
7383

7484
3. 这时，两个链表同时重复进行`node = node.next`操作，直到找到相同的节点或者其中一个链表已经到尾部。
75-
```python
76-
while biggerand smaller:
77-
if bigger== smaller:
78-
return bigger
7985

80-
bigger= bigger.next
81-
smaller= smaller.next
82-
83-
returnNone
84-
```
86+
```python
87+
while bigger and smaller:
88+
if bigger == smaller:
89+
return bigger
90+
91+
bigger = bigger.next
92+
smaller = smaller.next
93+
94+
return None
95+
```
8596

8697
##复杂度
8798
* 时间：`O(m + n)`。

‎zh/1-1000/203-remove-linked-list-elements.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -235,7 +235,7 @@ def remove_elements(head, val)
235235
dummy_head.next= head
236236
node= dummy_head
237237

238-
while!node.next.nil?
238+
untilnode.next.nil?
239239
if node.next.val== val
240240
node.next= node.next.next
241241
else

‎zh/1-1000/206-reverse-linked-list.md

Lines changed: 38 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -29,44 +29,54 @@
2929

3030
##思路
3131
1. 解决这个问题，只需要定义**两**个变量：`current`和`previous`。
32-
2.`current.next = previous`就是反转了。
33-
3. 循环条件应是`while (current != null)`，而不应该是`while (current.next != null)`，因为需要操作的是`current.next = previous`.
32+
33+
<details>
34+
<summary>
35+
点击查看答案
36+
</summary>
37+
<p>`current.next = previous`就是反转了。</p>
38+
</details>
39+
40+
2. 循环条件应是`while (current != null)`，而不应该是`while (current.next != null)`，因为需要操作的是`current.next = previous`.
3441

3542
##步骤
3643
1. 遍历所有节点。
37-
```javascript
38-
previous=null
39-
current= head
4044

41-
while (current!=null) {
42-
current=current.next
43-
}
44-
```
45+
```javascript
46+
previous = null
47+
current = head
48+
49+
while (current != null) {
50+
current = current.next
51+
}
52+
```
4553

4654
2. 加入`current.next = previous`。
47-
```javascript
48-
previous=null
49-
current= head
5055

51-
while (current!=null) {
52-
tempNext=current.next
53-
current.next= previous
54-
current= tempNext
55-
}
56-
```
56+
```javascript
57+
previous = null
58+
current = head
59+
60+
while (current != null) {
61+
tempNext = current.next
62+
current.next = previous
63+
current = tempNext
64+
}
65+
```
5766

5867
3.`previous`目前始终是`null`，需要让它变化起来：`previous = current`。
59-
```javascript
60-
previous=null
61-
current= head
6268

63-
while (current!=null) {
64-
tempNext=current.next
65-
current.next= previous
66-
previous= current
67-
current= tempNext
68-
}
69-
```
69+
```javascript
70+
previous = null
71+
current = head
72+
73+
while (current != null) {
74+
tempNext = current.next
75+
current.next = previous
76+
previous = current
77+
current = tempNext
78+
}
79+
```
7080

7181
##复杂度
7282
* 时间：`O(N)`。

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp