You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: en/1-1000/160-intersection-of-two-linked-lists.md
+40-29Lines changed: 40 additions & 29 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -36,52 +36,63 @@ The test cases are generated such that there are **no cycles** anywhere in the e
36
36
### [Constraints]
37
37
- The number of nodes of `listA` is in the `m`.
38
38
- 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`
41
41
42
42
**Follow up**: Could you write a solution that runs in `O(m + n)` time and use only `O(1)` memory?
43
43
44
44
## 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
+
45
53
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`.
46
54
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.
47
55
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.
48
56
49
57
## Steps
50
58
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
54
59
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
+
```
60
69
61
70
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
65
71
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
+
```
73
83
74
84
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.
Copy file name to clipboardExpand all lines: en/1-1000/206-reverse-linked-list.md
+39-29Lines changed: 39 additions & 29 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -28,45 +28,55 @@ Given the `head` of a singly linked list, reverse the list, and return _the reve
28
28
-`-5000 <= Node.val <= 5000`
29
29
30
30
## 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`.
34
41
35
42
## Steps
36
43
1. Traverse all nodes.
37
-
```javascript
38
-
previous =null
39
-
current = head
40
44
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
+
```
45
53
46
54
2. Add `current.next = previous`.
47
-
```javascript
48
-
previous =null
49
-
current = head
50
55
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
+
```
57
66
58
67
3.`previous` is always `null`, we need to change it: `previous = current`.
0 commit comments