友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
206. Reverse Linked List
递归需要加强一下，反转链表的递归细节再推敲推敲。
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULLFollow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
思路分析
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
*
* Memory Usage: 38 MB, less than 6.48% of Java online submissions for Reverse Linked List.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-12 12:47
*/
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode curr = null;
while (head != null) {
ListNode next = head.next;
head.next = curr;
curr = head;
head = next;
}
return curr;
}
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
*
* Memory Usage: 37.8 MB, less than 51.44% of Java online submissions for Reverse Linked List.
*/
public ListNode reverseListRecursion(ListNode head) {
if (Objects.isNull(head) || Objects.isNull(head.next)) {
return head;
}
// 这个反转地方，还要再仔细推敲一下！！
ListNode node = reverseListRecursion(head.next);
head.next.next = head;
head.next = null;
return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-13 16:24:00
*/
public ListNode reverseList(ListNode head) {
return reverseList(head, null);
}
public ListNode reverseList(ListNode head, ListNode pre) {
if (head == null) {
return pre;
}
ListNode result = reverseList(head.next, head);
head.next = pre;
return result;
}