明明是道简单题，却是众多公司最爱考的题之一。所以要按题目里的进阶用迭代和递归的方式完成
题目：
给你单链表的头节点 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 指针指向前一个节点，然后更新前一个节点和当前节点，继续遍历下一个节点，直到遍历完整个链表。重要的是写代码的方式。
代码实现：
（1）迭代
class Solution {
public:ListNode* reverseList(ListNode* head) {// 这个指针将用于记录当前节点的前一个节点，在反转过程中会不断更新ListNode* prev = nullptr;// 这个指针将用于遍历链表，从链表的头节点开始ListNode* curr = head;//只要 curr 指针不为 nullptr，就表示链表还没有遍历完while (curr != nullptr) {// 因为在反转过程中，curr->next 会被修改，所以需要提前保存下一个节点的信息ListNode* nextNode = curr->next;// 将当前节点 curr 的 next 指针指向前一个节点 prevcurr->next = prev;// 更新 prev 指针，将其指向当前节点 currprev = curr;// 更新 curr 指针，将其指向下一个节点 nextNodecurr = nextNode;}return prev;}
};复杂度分析
- 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
- 空间复杂度：O(1)，只使用了常数级的额外空间。
（2） 递归
对于反转链表而言，递归的核心在于假设链表从第 k+1 个节点开始的部分已经反转完成，那么只需将第 k 个节点正确接入反转后的部分，就能完成整个链表的反转。
class Solution {
public:ListNode* reverseList(ListNode* head) {// 递归终止条件：链表为空或只有一个节点，直接返回该节点if (head == nullptr || head->next == nullptr) {return head;}// 递归反转当前节点之后的链表ListNode* newHead = reverseList(head->next);// 将当前节点的下一个节点的 next 指针指向当前节点head->next->next = head;// 当前节点的 next 指针置为 nullptrhead->next = nullptr;return newHead;}
};代码解释
- 递归终止条件：当链表为空或者只有一个节点时，不需要进行反转，直接返回该节点。
- 递归调用：递归调用
reverseList函数来反转当前节点之后的链表，得到反转后的新头节点。 - 调整指针：将当前节点的下一个节点的
next指针指向当前节点，同时将当前节点的next指针置为nullptr。 - 返回新头节点：返回反转后的新头节点
复杂度分析
- 时间复杂度：O(n)，这里的 n 是链表的长度。因为需要对链表中的每个节点进行一次递归操作。
- 空间复杂度：O(n)，主要是递归调用栈的空间开销，递归的深度最大为链表的长度 n。
