25
25
26
26
则我们将 temp 指针指向 low 节点,此时则完成了反转。
27
27
28
- 反转之后我们继续反转下一节点,则
28
+ 反转之后我们继续反转下一节点,则 low = temp 即可。然后重复执行上诉操作直至最后,这样则完成了反转链表。
29
29
30
- low = temp 即可。然后重复执行上诉操作直至最后,这样则完成了反转链表。
31
-
32
- 我们下面看代码吧
30
+ 我们下面看代码吧。
33
31
34
32
我会对每个关键点进行注释,大家可以参考动图理解。
35
33
@@ -41,15 +39,10 @@ Java Code:
41
39
``` java
42
40
class Solution {
43
41
public ListNode reverseList (ListNode head ) {
44
- // 特殊情况
42
+ // 特殊情况
45
43
if (head == null || head. next == null ) {
46
44
return head;
47
45
}
48
- // 反转
49
- return reverse(head);
50
- }
51
- public ListNode reverse (ListNode head ) {
52
-
53
46
ListNode low = null ;
54
47
ListNode pro = head;
55
48
while (pro != null ) {
@@ -64,42 +57,41 @@ class Solution {
64
57
}
65
58
return low;
66
59
}
67
-
68
60
}
69
61
```
70
62
JS Code:
71
63
``` javascript
72
64
var reverseList = function (head ) {
65
+ // 特殊情况
73
66
if (! head || ! head .next ) {
74
67
return head;
75
68
}
76
69
let low = null ;
77
70
let pro = head;
78
71
while (pro) {
72
+ // 代表橙色指针
79
73
let temp = pro;
74
+ // 移动绿色指针
80
75
pro = pro .next ;
76
+ // 反转节点
81
77
temp .next = low;
78
+ // 移动黄色指针
82
79
low = temp;
83
80
}
84
81
return low;
85
82
};
86
83
```
87
84
88
- C++代码
85
+ C++ Code:
89
86
90
87
``` cpp
91
88
class Solution {
92
89
public:
93
90
ListNode* reverseList(ListNode* head) {
94
- //特殊情况
91
+ //特殊情况
95
92
if (head == nullptr || head->next == nullptr) {
96
93
return head;
97
94
}
98
- //反转
99
- return reverse(head);
100
- }
101
- ListNode * reverse (ListNode * head) {
102
-
103
95
ListNode * low = nullptr;
104
96
ListNode * pro = head;
105
97
while (pro != nullptr) {
@@ -117,6 +109,28 @@ public:
117
109
};
118
110
```
119
111
112
+ Python Code:
113
+
114
+ ```py
115
+ class Solution:
116
+ def reverseList(self, head: ListNode) -> ListNode:
117
+ //特殊情况
118
+ if head is None or head.next is None:
119
+ return head
120
+ low = None
121
+ pro = head
122
+ while pro is not None:
123
+ # 代表橙色指针
124
+ temp = pro
125
+ # 移动绿色指针
126
+ pro = pro.next
127
+ # 反转节点
128
+ temp.next = low
129
+ # 移动黄色指针
130
+ low = temp
131
+ return low
132
+ ```
133
+
120
134
上面的迭代写法是不是搞懂啦,现在还有一种递归写法,不是特别容易理解,刚开始刷题的同学,可以只看迭代解法。
121
135
122
136
@@ -148,11 +162,17 @@ class Solution {
148
162
JS Code:
149
163
``` javascript
150
164
var reverseList = function (head ) {
165
+ // 结束条件
151
166
if (! head || ! head .next ) {
152
167
return head;
153
168
}
169
+ // 保存最后一个节点
154
170
let pro = reverseList (head .next );
171
+ // 将节点进行反转。我们可以这样理解 4.next.next = 4;
172
+ // 4.next = 5;
173
+ // 则 5.next = 4 则实现了反转
155
174
head .next .next = head;
175
+ // 防止循环
156
176
head .next = null ;
157
177
return pro;
158
178
};
@@ -181,3 +201,41 @@ public:
181
201
};
182
202
```
183
203
204
+ Python Code:
205
+
206
+ ```py
207
+ class Solution:
208
+ def reverseList(self, head: ListNode) -> ListNode:
209
+ # 结束条件
210
+ if head is None or head.next is None:
211
+ return head
212
+ # 保存最后一个节点
213
+ pro = self.reverseList(head.next)
214
+ # 将节点进行反转。我们可以这样理解 4->next->next = 4;
215
+ # 4->next = 5;
216
+ # 则 5->next = 4 则实现了反转
217
+ head.next.next = head
218
+ # 防止循环
219
+ head.next = None
220
+ return pro
221
+ ```
222
+
223
+ <br/>
224
+
225
+ > 贡献者[ @jaredliw ] ( https://github.com/jaredliw ) 注:
226
+ >
227
+ > 这里提供一个比较直观的递归写法供大家参考。
228
+ >
229
+ > ```py
230
+ > class Solution :
231
+ > def reverseList (self, head: ListNode, prev_nd: ListNode = None) -> ListNode:
232
+ > # 结束条件
233
+ > if head is None:
234
+ > return prev_nd
235
+ > # 记录下一个节点并反转
236
+ > next_nd = head.next
237
+ > head.next = prev_nd
238
+ > # 给定下一组该反转的节点
239
+ > return self.reverseList(next_nd, head)
240
+ > ```
241
+
0 commit comments