给你单链表的头节点 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
进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?
初始代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
}
};
解题思路
递归,迭代
先试着用递归解决。
很明显,将尾节点的next指向其上一个节点,再将上一个节点的next置空就能完成链表逆置。流程图如下:

以尾节点为例。我们需要以下信息:
- 尾节点上一个节点的next
- 尾节点本身
- 尾节点的next
那么我们可以得到代码
完整代码(递归)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==NULL||head->next==NULL)
return head;
ListNode*tmp=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return tmp;
}
};
其中需要注意以下几点:
- head->next->next和head->next的操作不能对调。先改变head->next的话head->next->next的数据就丢失了。
- 为什么需要新建一个节点tmp?因为反转链表后最后新的头节点是原来的尾节点。这意味着我们需要保存链表尾节点的地址。并再最后将其作为新的头节点返回。
接下来看看迭代怎么实现。迭代比起递归就很好懂了。
和迭代一样,我们需要:
- 某节点的上一个节点
- 某节点
- 某节点的next
和递归不同的是,迭代从链表头开始,比如给个[1,2,3]的链表,它前两步循环的流程图如下


其实就是要理解好“地址和链表节点“之间的关系。完整代码如下
完整代码(迭代)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode*end=head;
ListNode*pre=NULL;
while(end)
{
ListNode*tmp=end->next;
end->next=pre;
pre=end;
end=tmp;
}
return pre;
}
};