给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
示例 1：
**输入：** head = [1,2,3,4,5]
**输出：** [5,4,3,2,1]
示例 2：
**输入：** head = [1,2]
**输出：** [2,1]
示例 3：
**输入：** head = []
**输出：** []
提示：
- 链表中节点的数目范围是
[0, 5000]
-5000 <= Node.val <= 5000
进阶： 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
注意：本题与主站 206 题相同： https://leetcode-cn.com/problems/reverse-linked-list/
方法一：迭代
假设链表为 1 \rightarrow 2 \rightarrow 3 \rightarrow \varnothing，我们想要把它改成 \varnothing \leftarrow 1 \leftarrow 2 \leftarrow 3。
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
| var reverseList = function(head) {
let prev = null;
let curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
};
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
| func reverseList(head *ListNode) *ListNode {
var prev *ListNode
curr := head
for curr != nil {
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev
}
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
| struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* curr = head;
while (curr) {
struct ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
|
复杂度分析
方法二：递归
递归版本稍微复杂一些，其关键在于反向工作。假设链表的其余部分已经被反转，现在应该如何反转它前面的部分？
假设链表为：
n_1\rightarrow \ldots \rightarrow n_{k-1} \rightarrow n_k \rightarrow n_{k+1} \rightarrow \ldots \rightarrow n_m \rightarrow \varnothing
若从节点 n_{k+1 到 n_m 已经被反转，而我们正处于 n_k。
n_1\rightarrow \ldots \rightarrow n_{k-1} \rightarrow n_k \rightarrow n_{k+1} \leftarrow \ldots \leftarrow n_m
我们希望 n_{k+1 的下一个节点指向 n_k。
所以，n_k.\textit{next}.\textit{next} = n_k。
需要注意的是 n_1 的下一个节点必须指向 \varnothing。如果忽略了这一点，链表中可能会产生环。
[sol2-Java]1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
|
[sol2-JavaScript]1
2
3
4
5
6
7
8
9
| var reverseList = function(head) {
if (head == null || head.next == null) {
return head;
}
const newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
};
|
[sol2-Golang]1
2
3
4
5
6
7
8
9
| func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
newHead := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return newHead
}
|
[sol2-C++]1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};
|
[sol2-C]1
2
3
4
5
6
7
8
9
| struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
|
复杂度分析
