题目
给你单链表的头节点 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
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
解答
- 递归方式
在这个实现中，我们首先检查链表是否为空或只有一个节点。如果是这样，我们直接返回该节点，因为没有必要反转链表。
如果链表中有多个节点，我们将递归调用 reverseList 函数来反转链表的后半部分。然后，我们将当前节点连接到反转后的链表的末尾，将当前节点作为新的尾节点，连接到 NULL。最后，返回新的头节点。
这个递归方法的时间复杂度是 O(n)，其中 n 是链表的长度。虽然它可能需要使用堆栈来存储递归调用的上下文，但它通常比迭代方法更简洁易懂。
/**
* 以链表1->2->3->4->5举例
* @param head
* @return
*/
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
/*
直到当前节点的下一个节点为空时返回当前节点
由于5没有下一个节点了，所以此处返回节点5
*/
return head;
}
//递归传入下一个节点，目的是为了到达最后一个节点
ListNode* newHead = reverseList(head->next);
/*
第一轮出栈，head为5，head->next为空，返回5
第二轮出栈，head为4，head->next为5，执行head->next->next=head也就是5->next=4，
把当前节点的子节点的子节点指向当前节点
此时链表为1->2->3->4<->5，由于4与5互相指向，所以此处要断开4->next=null
此时链表为1->2->3->4<-5
返回节点5
第三轮出栈，head为3，head->next为4，执行head->next->next=head也就是4->next=3，
此时链表为1->2->3<->4<-5，由于3与4互相指向，所以此处要断开3->next=null
此时链表为1->2->3<-4<-5
返回节点5
第四轮出栈，head为2，head->next为3，执行head->next->next=head也就是3->next=2，
此时链表为1->2<->3<-4<-5，由于2与3互相指向，所以此处要断开2->next=null
此时链表为1->2<-3<-4<-5
返回节点5
第五轮出栈，head为1，head->next为2，执行head->next->next=head也就是2->next=1，
此时链表为1<->2<-3<-4<-5，由于1与2互相指向，所以此处要断开1->next=null
此时链表为1<-2<-3<-4<-5
返回节点5
出栈完成，最终头节点5->4->3->2->1
*/
head->next->next = head;
head->next = nullptr;
return newHead;
}
- 迭代方式（头插法）
头插法的基本思路是，将链表的每个节点插入到新链表的头部。由于头插法是从头部开始插入，因此我们需要一个指针来跟踪新链表的头部。
在这个实现中，我们首先定义一个新链表的头部指针 newHead，并将其初始化为 NULL。
然后，我们遍历原链表中的每个节点。在每个迭代中，我们先记录当前节点的下一个节点，然后将当前节点插入到新链表的头部。为此，我们将当前节点的 next 指针指向新链表的头部，然后将新链表的头部指针指向当前节点。
最后，我们将当前节点更新为原链表中的下一个节点，并重复这个过程，直到我们遍历完整个链表。
这个方法的时间复杂度是 O(n)，其中 n 是链表的长度。它不需要额外的空间来存储递归调用的上下文，因此它通常比递归方法更快。
/**
* 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) {
// 新链表的头节点指针，初始为 NULL
ListNode* newHead = NULL;
// 依次遍历原链表中的每个节点
while (head != NULL) {
// 记录当前节点的下一个节点
ListNode* next = head->next;
// 将当前节点插入到新链表的头部
head->next = newHead;
newHead = head;
// 处理下一个节点
head = next;
}
// 返回新链表的头节点指针
return newHead;
}
};