给你单链表的头节点 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
**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
解题思路：递归
对于链表，其实用迭代的方式是比较好理解的，因为把它抽象成一棵二叉树，其实就是一个单分支的二叉树，所以用迭代反而会更好理解，但是为了学习递归，我们要使用递归的思想来解决这道题，其实也不是很难，就是一个逆序的时机问题！
递归问题，我们要用宏观的角度去看待，只要发现了重复的子问题，我们就把其中的一个子问题拎出来处理，然后交给其它子问题去解决即可，就像这道题的例一，我们要对整个链表进行逆序，如果我们针对前两个节点单独来说的话，将节点二直接指向节点一的话，那么节点三就丢失了，所以我们要换个思路，就是递归的思路，在处理前两个节点之前，应该先保证后面的节点已经处理完逆序了，此时就只需要关心当前的两个节点即可，如下图所示：
可以看到，按照上面的操作次序来看，这就是一个后序遍历，先递归处理后面的节点，再返回来完成当前节点的操作！
只不过要注意一个细节，就是题目要返回的是逆序后新的头节点也就是节点五，如果我们在递归函数中返回当前节点，那最后得到的还是上图中的节点一，所以我们需要在后序遍历到空节点的时候，也就是在递归函数的出口记录下节点五，然后进行返回，经过一层一层的返回之后，最后在原先调用递归函数的入口处就拿到了新节点，进行返回即可！
此外，因为最后我们要让原来的头节点指向空，那么递归函数中就需要有一个操作是把 cur->next 指向空的，这对深层的其它节点其实是没有影响的，因为中间的某些节点在操作的时候虽然也是直接 cur->next = nullptr，但是操作完之后返回到上一层之后，进行操作是 cur->next->next 指向 cur，此时 cur->next->next 为空的话是没问题的！
所以可以统一第三步操作为 cur->next = nullptr。
/**
* 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 == nullptr || head->next == nullptr)
return head;
// 进行后序遍历，因为操作当前节点前要保证后面已经处理完毕。
// 还要将返回的节点记录下来，这个节点是新的头节点
ListNode* newhead = reverseList(head->next);
// 操作当前节点
head->next->next = head;
head->next = nullptr;
// 最后返回记录的新头节点
return newhead;
}
};