206. 反转链表
题目描述
给你单链表的头节点 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
双指针
该段代码的目标是实现链表的反转。这里使用了迭代法，不断地更改当前节点的 next 指针，直到遍历完整个链表。反转过程中，需要一个额外的指针 tmp 来保存下一个节点的信息，以防止链表断裂。
- ListNode* cur = head; 初始化当前节点指针 cur，开始时指向链表头 head。
- ListNode* pre = nullptr; 初始化前一个节点指针 pre，开始时没有前一个节点，因此设置为 nullptr。
- 在 while(cur) 循环中，只要当前节点不是 nullptr（即没有到达链表尾部），循环就继续。
- ListNode* tmp = cur->next; 保存当前节点 cur 的下一个节点，因为 cur 的 next 指针即将改变。
- cur->next = pre; 反转操作，让当前节点 cur 的 next 指针指向前一个节点 pre。
- pre = cur; 和 cur = tmp; 更新 pre 和 cur 指针，为下一次迭代移动到下一个节点。
循环结束时，pre 指向最后一个处理的节点，这时 pre 就是反转后链表的新头节点，因此函数最后返回 pre。
class Solution {
public:
// 反转链表的函数
ListNode* reverseList(ListNode* head) {
ListNode* cur = head; // cur指针用于遍历链表，初始指向头节点
ListNode* pre = nullptr; // pre指针用于追踪cur的前一个节点，初始为nullptr
// 遍历链表直到cur指针为空，即到达链表末尾
while(cur) {
// tmp暂存cur的下一个节点，因为接下来要改变cur->next的指向
ListNode* tmp = cur->next;
// 反转cur指针的指向，将cur的next指向pre
cur->next = pre;
// 移动pre和cur指针，为下一次迭代做准备
pre = cur; // pre向前移动到cur的位置
cur = tmp; // cur向前移动到原来cur的下一个节点
}
// 当循环结束时，cur为nullptr，pre指向原链表的最后一个节点，即反转后的链表头
return pre;
}
};
递归
在这个代码中，reverseList 是一个公有方法，它为用户提供了反转链表的接口。它依赖于一个私有递归辅助函数 reverse 来实际执行反转操作。递归辅助函数 reverse 接受两个参数：当前要处理的节点 cur 和前一个节点 pre。通过不断地将 cur->next 指向 pre 并递归调用 reverse，链表被逐个节点反转，直到 cur 为 nullptr，意味着链表已经完全反转，此时 pre 是新链表的头节点。
// 解决方案类，包含反转链表的方法
class Solution {
public:
// 公有方法，接口，它接受一个链表的头节点，并返回反转后的链表的头节点
ListNode* reverseList(ListNode* head) {
// 调用私有的递归函数来执行实际的反转操作
// 初始调用时，先前节点设置为nullptr，因为头节点没有前驱
return reverse(head, nullptr);
}
private:
// 私有递归函数，用于实际执行反转过程
// 参数cur是当前正在访问的节点
// 参数pre是cur节点之前的节点，即在反转后，cur应该指向的节点
ListNode* reverse(ListNode* cur, ListNode* pre) {
// 如果当前节点为空（nullptr），意味着我们到达了原始链表的尾端
// 此时，pre是反转链表的头节点，应返回它
if (cur == nullptr) return pre;
// 保存当前节点的下一个节点，因为接下来需要改变当前节点的next指针
ListNode* tmp = cur->next;
// 反转操作：将当前节点的next指针指向pre节点
cur->next = pre;
// 递归调用reverse函数处理剩余的链表部分
// 此时，当前节点成为下一步的pre，而tmp（原cur->next）成为下一步的cur
return reverse(tmp, cur);
}
};
