反转链表算法很经典了，我们面试也经常会遇到。
大致的话会分为两种解法：一种是迭代 一种是递归

一、迭代法

public ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head, tmp = null;
        while (cur != null) {
            //存储下一个节点地址
            tmp = cur.next;
            //把当前节点指向上个节点
            cur.next = pre;

            //两个节点分别往前挪
            //上一个节点往前挪
            pre = cur;
            //当前节点往前拖
            cur = tmp;
        }
        return pre;
    }

主要思路就是
先创建pre节点为null，cur节点指向链表的头结点head，tmp为临时变量用于存储当前节点的下个节点。
然后先tmp将当前节点的next节点存储后，将cur节点反转，指向pre节点。

while第一次循环时我们完成了第一个反转，就是将cur（也就是头结点）指向了pre（上个节点为null）。
随后我们将cur和pre向后移动，因为之前我们用tmp存储了cur的下一个结点，所以我们需要将cur的值先赋值给pre，然后再将tmp(下个要反转的结点)赋值给cur(如果不先赋值pre，cur就被tmp覆盖了，你懂的~)

如图所示

迭代法反转链表示意图（图片来自leedcode-206）

这样我们whlie循环介绍结束以后，以当前节点cur为条件，当cur移动到尾结点的后一个，也就是为null时，这时上个节点pre正好指向链表最后一个节点，我们也完成了链表的反转，此时的头结点就是pre，直接返回。

我们也可以稍稍改造一下 省略掉tmp变量，以head（当前节点）来替代
如下：

public ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            //直接把下个节点指向头结点完成反转
            head = head.next;

            //把当前节点(cur是之前的头结点)指向上个节点 与之前一样
            cur.next = pre;

            //两个节点分别往前挪
            //上一个节点往前挪
            pre = cur;
            //当前节点往前拖 由于头结点已经指向了下一个结点 直接挪动即可
            cur = head;

            //每次循环完毕之后 head就指向下个节点
        }
        return pre;
    }

二、递归法

一般来说，递归解决问题的代码总是精简的，但是思路却很难想得通，我们要做的不仅仅是去演算别人写出的算法，而是要总结出递归的思路，以便应对每个有规律问题的递归解答方式。

先列举下阶乘的递归写法：

int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);
}

阶乘想必大家见识的多了，求n!有很多种解法，最直接的莫过于循环乘积。
上面的是阶乘的递归写法，我们可以看到，递归总是有一个出口---防止代码进行无限循环。
递归的思想首先是假设，求n!的时候我们假设已经算完了1*2*3...*(n-1)

我们甚至可以这么写：

int factorial(int n) {
    if (n == 1) return 1;
    return n * (n - 1) * factorial(n - 2);
}

这个思路也就是我们假设已经算完了1*2*3...*(n-2)

所以递归思想有先决的两个条件 1.假设 2.出口
然后就是核心逻辑，调用自身。

我们来看反转链表的问题：

首先我们有一个1->2->3->4->5->null的链表，想将它反转成5->4->3->2->1->null。如下图所示：

反转链表示意图

1.假设

我们按照阶乘的思路假设，假设除了头结点head(也就是1)，后面都反转好了。也就是：

假设除头结点 其他都反转好了示意图

代码就为：ListNode newHead = reverseList(head.next);
意思就是我们把1的下个 2传进去 期望返回上面图中的样子。

此时的1在干啥？它也在：
1(也就是head)是始终都指向2的。
但是通过我们的假设2345都叛变了，变成了下面的样子:

1(头结点状况示意图)

此时要做什么？就是将1(head)节点和2节点之间弄好：
也就是

     //把1的next节点的next指向自身
     head.next.next = head;

head.next.next = head之后

然后我们发现1仍然指向2（嗯，1很忠贞鉴定不移）,我们最终要反转成图1的样子，也就需要增加：

head.next = null;

就变成如下的样子：

head.next = null
我们发现已经反转成了想要的模样。
此时需要一个返回值，返回什么，是head吗？还是newHead?
我们肯定要返回反转后链表的头结点，也就是我们假设后的返回值，即newHead。

2.出口

情况1：肯定就是我们的head是一个空 那么我们返回null就可以了。

if (head == null) return null;

情况2：反转链表起码两个才有意义，如果当前链表只有一个head呢？那我们返回head就可以了

if (head.next == null) return head;

总结以上情况，代码如下：

public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
}

这就是反转链表的递归解法。

予人玫瑰，手有余香！如果这篇文章帮助了你，并且让你觉得想要放到自己的博客上，欢迎转载，转载请注明出处。

学习路上，与君共勉！
讨论交流可加微信T_Yang_0727，记得备注哦~