Skip to content

Commit dbd8fb8

Browse files
gazeldxgazeldx
committed
206-reverse-linked-list.md Added Java and Python solutions.
1 parent b8e567c commit dbd8fb8

4 files changed

Lines changed: 219 additions & 0 deletions

File tree

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@ You can skip the more difficult problems and do them later.
2323

2424
# Linked List
2525
- [203. Remove Linked List Elements](solutions/1-1000/203-remove-linked-list-elements.md) was solved in _Python, Java, C++, JavaScript, C#, Go, Ruby_.
26+
- [206. Reverse Linked List](solutions/1-1000/206-reverse-linked-list.md) was solved in _Python, Java, C++, JavaScript, C#, Go, Ruby_.
2627
- [707. Design Linked List](solutions/1-1000/707-design-linked-list.md) was solved in _Python, Java, JavaScript, C#_.
2728

2829
# Dynamic Programming

‎images/examples/206_1.jpg‎

18.7 KB
Loading

‎images/examples/206_2.jpg‎

7.63 KB
Loading

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

Lines changed: 218 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,218 @@
1+
# 206. Reverse Linked List - LeetCode Solution
2+
LeetCode problem link: [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list),
3+
[206. 反转链表](https://leetcode.cn/problems/reverse-linked-list)
4+
5+
[中文题解](#中文题解)
6+
7+
## LeetCode problem description
8+
Given the `head` of a singly linked list, reverse the list, and return _the reversed list_.
9+
10+
### [Example 1]
11+
![](../../images/examples/206_1.jpg)
12+
**Input**: `head = [1,2,3,4,5]`
13+
14+
**Output**: `[5,4,3,2,1]`
15+
16+
### [Example 2]
17+
![](../../images/examples/206_2.jpg)
18+
**Input**: `[1,2]`
19+
20+
**Output**: `[2,1]`
21+
22+
### [Example 3]
23+
**Input**: `[]`
24+
25+
**Output**: `[]`
26+
27+
### [Constraints]
28+
- The number of nodes in the list is the range `[0, 5000]`.
29+
- `-5000 <= Node.val <= 5000`
30+
31+
## Intuition behind the Solution
32+
[中文题解](#中文题解)
33+
34+
1. To solve this problem, we only need to define **two** variables: `current` and `previous`.
35+
2. `current.next = previous` is the inversion.
36+
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`.
37+
38+
## Steps to the Solution
39+
1. Traverse all nodes.
40+
```javascript
41+
previous = null
42+
current = head
43+
44+
while (current != null) {
45+
current = current.next
46+
}
47+
```
48+
49+
2. Add `current.next = previous`.
50+
```javascript
51+
previous = null
52+
current = head
53+
54+
while (current != null) {
55+
tempNext = current.next
56+
current.next = previous
57+
current = tempNext
58+
}
59+
```
60+
61+
3. `previous` is always `null`, we need to change it: `previous = current`.
62+
```javascript
63+
previous = null
64+
current = head
65+
66+
while (current != null) {
67+
tempNext = current.next
68+
current.next = previous
69+
previous = current
70+
current = tempNext
71+
}
72+
```
73+
74+
## Complexity
75+
* Time: `O(n)`.
76+
* Space: `O(1)`.
77+
78+
## Java
79+
```java
80+
class Solution {
81+
public ListNode reverseList(ListNode head) {
82+
ListNode previous = null;
83+
var current = head;
84+
85+
while (current != null) {
86+
var tempNext = current.next;
87+
current.next = previous;
88+
previous = current;
89+
current = tempNext;
90+
}
91+
92+
return previous;
93+
}
94+
}
95+
```
96+
97+
## Python
98+
```python
99+
# class ListNode:
100+
# def __init__(self, val=0, next=None):
101+
# self.val = val
102+
# self.next = next
103+
104+
class Solution:
105+
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
106+
previous = None
107+
current = head
108+
109+
while current:
110+
temp_next = current.next
111+
current.next = previous
112+
previous = current
113+
current = temp_next
114+
115+
return previous
116+
```
117+
118+
## C++
119+
```cpp
120+
// Welcome to create a PR to complete the code of this language, thanks!
121+
```
122+
123+
## JavaScript
124+
```javascript
125+
// Welcome to create a PR to complete the code of this language, thanks!
126+
```
127+
128+
## C#
129+
```c#
130+
// Welcome to create a PR to complete the code of this language, thanks!
131+
```
132+
133+
## Go
134+
```go
135+
// Welcome to create a PR to complete the code of this language, thanks!
136+
```
137+
138+
## Ruby
139+
```ruby
140+
# Welcome to create a PR to complete the code of this language, thanks!
141+
```
142+
143+
## C
144+
```c
145+
// Welcome to create a PR to complete the code of this language, thanks!
146+
```
147+
148+
## Kotlin
149+
```kotlin
150+
// Welcome to create a PR to complete the code of this language, thanks!
151+
```
152+
153+
## Swift
154+
```swift
155+
// Welcome to create a PR to complete the code of this language, thanks!
156+
```
157+
158+
## Rust
159+
```rust
160+
// Welcome to create a PR to complete the code of this language, thanks!
161+
```
162+
163+
## Other languages
164+
```
165+
// Welcome to create a PR to complete the code of this language, thanks!
166+
```
167+
168+
## 问题描述
169+
170+
171+
### [Example 1]
172+
给你单链表的头节点 `head` ，请你反转链表，并返回反转后的链表。
173+
174+
**输入**: `head = [1,2,3,4,5]`
175+
176+
**输出**: `[5,4,3,2,1]`
177+
178+
## 中文题解
179+
### 思路
180+
1. 解决这个问题，只需要定义**两**个变量：`current`和`previous`。
181+
2. `current.next = previous`就是反转了。
182+
3. 循环条件应是`while current != null`，而不应该是`while current.next != null`，因为需要操作的是`current.next = previous`.
183+
184+
### 步骤
185+
1. 遍历所有节点。
186+
```javascript
187+
previous = null
188+
current = head
189+
190+
while (current != null) {
191+
current = current.next
192+
}
193+
```
194+
195+
2. 加入`current.next = previous`。
196+
```javascript
197+
previous = null
198+
current = head
199+
200+
while (current != null) {
201+
tempNext = current.next
202+
current.next = previous
203+
current = tempNext
204+
}
205+
```
206+
207+
3. `previous`目前始终是`null`，需要让它变化起来：`previous = current`。
208+
```javascript
209+
previous = null
210+
current = head
211+
212+
while (current != null) {
213+
tempNext = current.next
214+
current.next = previous
215+
previous = current
216+
current = tempNext
217+
}
218+
```

0 commit comments

Comments
 (0)