牛客网算法面试必刷 TOP101 题目汇总链接：https://www.algomooc.com/3080.html
一、题目描述
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围： 0 ≤ n ≤ 1000
要求：空间复杂度 O(1)，时间复杂度 O(n)。
如当输入链表{1,2,3}时，经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
示例1
输入：
{1,2,3,4,5}
返回值：
{5,4,3,2,1}
示例2
输入：
{}
返回值：
{}
说明：
空链表则输出空
二、题目解析
反转链表是非常经典的一道算法题，它的解法非常之多，而递归、迭代是我们最需要掌握的两种，其中递归的代码非常简洁，但很难理解，有不少同学是强行背诵的，那么我们这篇文章通过图片和逐行代码解析的方式来帮助大家理解递归的思路和代码。
如果文字版依旧理解的不够透彻，强烈建议大家看一下动画和视频进行理解。
在下图，包含了反转链表递归解法的全部代码。
我们把目光放到 reverseList 这个函数上，它的返回值是一个链表结点，参数值也是一个链表结点。
在第一次调用 reverseList 这个函数时，参数值 head 是给定的单链表的头节点，它的值 val 是 1。
head.val = 1
于是当前这个函数就是在执行 reverseList(1) 这个过程。
1、执行函数 reverseList(1)
由于 head 不为空并且 head.next 为 2 这个结点也不为空，因此 if 这个语句的判定条件都是 false，不会执行里面的 return 语句。
那么就会来到 ListNode cur = reverseList(head.next) 这句代码，按照函数的执行逻辑，只有这句代码执行完毕之后，才会开始执行下方的 head.next.next = head 等后续代码。
由于 head 是 1 这个结点，head.next 是 2 这个结点，因此 ListNode cur = reverseList(head.next) 这句代码就是在执行 ListNode cur = reverseList(2) 。
综上所述，也就是说只有 reverseList(2) 有了结果，cur 这个变量才有结果，在函数 reverseList(1) 中才能继续执行下方的 head.next.next = head 等后续代码，所以来看看 reverseList(2) 是怎么执行的。
2、执行函数 reverseList(2)
此时，入参值 head 为 2 了，由于 head 不为空并且 head.next 为 3 这个结点也不为空，因此 if 这个语句的判定条件都是 false，不会执行里面的 return 语句。
那么就会来到 ListNode cur = reverseList(head.next) 这句代码，按照函数的执行逻辑，只有这句代码执行完毕之后，才会开始执行下方的 head.next.next = head 等后续代码。
由于 head 是 2 这个结点，head.next 是 3 这个结点，因此 ListNode cur = reverseList(head.next) 这句代码就是在执行 ListNode cur = reverseList(3) 。
综上所述，也就是说只有 reverseList(3) 有了结果，cur 这个变量才有结果，在函数 reverseList(2) 中才能继续执行下方的 head.next.next = head 等后续代码，所以来看看 reverseList(3) 是怎么执行的。
3、执行函数 reverseList(3)
此时，入参值 head 为 3 了，由于 head 不为空并且 head.next 为 4 这个结点也不为空，因此 if 这个语句的判定条件都是 false，不会执行里面的 return 语句。
那么就会来到 ListNode cur = reverseList(head.next) 这句代码，按照函数的执行逻辑，只有这句代码执行完毕之后，才会开始执行下方的 head.next.next = head 等后续代码。
由于 head 是 3 这个结点，head.next 是 4 这个结点，因此 ListNode cur = reverseList(head.next) 这句代码就是在执行 ListNode cur = reverseList(4) 。
综上所述，也就是说只有 reverseList(4) 有了结果，cur 这个变量才有结果，在函数 reverseList(3) 中才能继续执行下方的 head.next.next = head 等后续代码，所以来看看 reverseList(4) 是怎么执行的。
通过上面的三个执行过程，你应该很快就发现了，好像整个执行过程、逻辑都差不多，唯一的区别点就在于参数值不同。
是的！
这个也正是递归的一个精髓所在，同时也是一个递归笑话的来源：当你理解了递归，你也就理解了递归。
那我们继续往下看。
4、执行函数 reverseList(4)
此时，入参值 head 为 4 了，由于 head 不为空并且 head.next 为 5 这个结点也不为空，因此 if 这个语句的判定条件都是 false，不会执行里面的 return 语句。
那么就会来到 ListNode cur = reverseList(head.next) 这句代码，按照函数的执行逻辑，只有这句代码执行完毕之后，才会开始执行下方的 head.next.next = head 等后续代码。
由于 head 是 4 这个结点，head.next 是 5 这个结点，因此 ListNode cur = reverseList(head.next) 这句代码就是在执行 ListNode cur = reverseList(5) 。
综上所述，也就是说只有 reverseList(5) 有了结果，cur 这个变量才有结果，在函数 reverseList(4) 中才能继续执行下方的 head.next.next = head 等后续代码，所以来看看 reverseList(5) 是怎么执行的。
5、执行函数 reverseList(5)
此时，入参值 head 为 5 了，此时 head 不为空但 head.next 为空，意味着 if 语句为 true，会执行里面的 return 语句，同时下方的所有代码都不会再执行。
在函数 reverseList(5) 中执行了 return head 即 return 5 这行代码，那么是返回给谁呢？
返回给执行函数reverseList(5)的地方！
而执行函数 reverseList(5) 是在函数 reverseList(4) 当中 ListNode cur = reverseList(5) 这句代码开始执行的。
6、回到函数 reverseList(4) 继续执行其下方代码
此时的 head 是函数的入参值 4 这个结点，在执行 ListNode cur = reverseList(5) 代码中，cur 的值为 5 这个结点。
head.next.next = head 这行代码有两个 next ，前者的意思表示的事 head 的下一个结点，后者表示的是设置某个结点的 next 属性为等号右边的值。
head.next.next = head 这行代码的意思就是设置 4 这个结点的下一个结点的 next 属性为等号右边的 4 这个节点。
再看后面的代码head.next = null，意思就是 4 这个结点不指向任何结点了，指向了 null 这个空结点。
终于来到了函数reverseList(4) 里面的最后一句代码 return cur。
cur 的值是多少呢？ 是 5 这个结点。
所以最后一句代码就是return 5，那么是返回给谁呢？
返回给执行函数 reverseList(4) 的地方！
而执行函数 reverseList(4) 是在函数 reverseList(3) 当中 ListNode cur = reverseList(4) 这句代码开始执行的。
7、回到函数 reverseList(3) 继续执行其下方代码
此时的 head 是函数的入参值 3 这个结点，在执行 ListNode cur = reverseList(4) 代码中，cur 的值为 5 这个结点。
head.next.next = head 这行代码有两个 next ，前者的意思表示的事 head 的下一个结点，后者表示的是设置某个结点的 next 属性为等号右边的值。
head.next.next = head 这行代码的意思就是设置 3 这个结点的下一个结点的 next 属性为等号右边的 3 这个节点。
再看后面的代码head.next = null，意思就是 3 这个结点不指向任何结点了，指向了 null 这个空结点。
终于来到了函数reverseList(3) 里面的最后一句代码 return cur。
cur 的值是多少呢？ 是 5 这个结点。
所以最后一句代码就是return 5，那么是返回给谁呢？
返回给执行函数 reverseList(3) 的地方！
而执行函数 reverseList(3) 是在函数 reverseList(2) 当中 ListNode cur = reverseList(3) 这句代码开始执行的。
8、回到函数 reverseList(2) 继续执行其下方代码
此时的 head 是函数的入参值 2 这个结点，在执行 ListNode cur = reverseList(3) 代码中，cur 的值为 5 这个结点。
head.next.next = head 这行代码有两个 next ，前者的意思表示的事 head 的下一个结点，后者表示的是设置某个结点的 next 属性为等号右边的值。
head.next.next = head 这行代码的意思就是设置 2 这个结点的下一个结点的 next 属性为等号右边的 2 这个节点。
再看后面的代码head.next = null，意思就是 2 这个结点不指向任何结点了，指向了 null 这个空结点。
终于来到了函数reverseList(2) 里面的最后一句代码 return cur。
cur 的值是多少呢？ 是 5 这个结点。
所以最后一句代码就是return 5，那么是返回给谁呢？
返回给执行函数 reverseList(2) 的地方！
而执行函数 reverseList(2) 是在函数 reverseList(1) 当中 ListNode cur = reverseList(2) 这句代码开始执行的。
9、回到函数 reverseList(1) 继续执行其下方代码
此时的 head 是函数的入参值 1 这个结点，在执行 ListNode cur = reverseList(2) 代码中，cur 的值为 5 这个结点。
head.next.next = head 这行代码有两个 next ，前者的意思表示的事 head 的下一个结点，后者表示的是设置某个结点的 next 属性为等号右边的值。
head.next.next = head 这行代码的意思就是设置 1 这个结点的下一个结点的 next 属性为等号右边的 1 这个节点。
再看后面的代码head.next = null，意思就是 2 这个结点不指向任何结点了，指向了 null 这个空结点。
终于来到了函数reverseList(1) 里面的最后一句代码 return cur。
cur 的值是多少呢？ 是 5 这个结点。
所以最后一句代码就是return 5，那么是返回给谁呢？
返回给执行函数 reverseList(1) 的地方！
而这个地方就是梦开始的地方，编辑器一开始就是在执行 reverseList(1) 这个函数！
把 5 返回去就可以了，并且得到了如下这样一个单链表，头结点是 5 这个结点。
以上的过程就是反转链表使用递归处理的全部步骤了。
递归是一种代码量很少却很难想明白的一种方法，希望上面这些「啰啰嗦嗦」的代码能帮你捋清楚整个思路。
三、参考代码
// 本题文字版详解请访问下方网站
// https://www.algomooc.com
// 作者：程序员吴师兄
public class Solution {
public ListNode ReverseList(ListNode head) {
// 寻找递归终止条件
// 1、head 指向的结点为 null
// 2、head 指向的结点的下一个结点为 null
// 在这两种情况下，反转之后的结果还是它自己本身
if (head == null || head.next == null) return head;
// 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点
// 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head
ListNode cur = ReverseList(head.next);
// 比如原链表为 1 --> 2 --> 3 --> 4 --> 5 --> null
// 5 -- > 4
// 第一次执行下面代码的时候，head 为 4，那么 head.next = 5
// 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点
// 等号右侧为 head，意思就是设置 5 的下一个节点是 4
head.next.next = head;
// head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了
// 否则会发生无限循环
head.next = null;
// 我们把每次反转后的结果传递给上一层
return cur;
}
}
