已解答
简单
相关标签
相关企业
给你单链表的头节点 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
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
迭代法
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* curentNode = head;
ListNode* preNode = nullptr;
ListNode* temp = nullptr;
while (curentNode != nullptr) {
temp = preNode;
preNode = curentNode;
curentNode = curentNode->next;
preNode->next = temp; // 反转指针
}
return preNode; // 返回新的头节点
}
};递归
class Solution {
public:
ListNode* reverse(ListNode* pre, ListNode* cur) {
if (cur == nullptr) {
return pre; // 当cur为nullptr时，返回pre作为新的头节点
}
ListNode* next = cur->next; // 保存当前节点的下一个节点
cur->next = pre; // 将当前节点的next指向前一个节点
pre = cur; // 更新前一个节点为当前节点
return reverse(pre, next); // 递归调用，继续处理下一个节点
}
ListNode* reverseList(ListNode* head) {
// 和双指针法初始化是一样的逻辑
// ListNode* cur = head;
// ListNode* pre = NULL;
return reverse(NULL, head);
}
};核心思路
