剑指 Offer 24. 反转链表

大家好，我是吴师兄。

今天继续来学习《剑指Offer》系列的一道经典题目，依旧给出了非常详细的题解和精美的配图与动画。

一、题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

二、题目解析

这道题目有很多种解法，递归解法最难以理解整个过程，今天我就带大家来探究一次！

先来看分析过程，这里看不懂没关系，一定要看最后的动画过程。

• 1、通过递归函数，一直递归到链表的最后一个结点为止，此时，该结点就是反转成功后的头结点，是最终的返回结果。
• 2、在递归函数中，让当前节点的下一个节点的 next 指针指向当前节点。
• 3、在递归函数中，让当前节点的 next 指针指向 null
• 4、通过二三步的操作，已经让递归函数中的链表实现了局部反转，将结果返回给上一层递归函数
• 5、所有递归结束后，链表反转成功。

为了帮助你更好的理解整个过程，我特意做了一组动画，点开可以查看：

三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
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
        // 第一次执行下面代码的时候，head 为 4，那么 head.next = 5
        // 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点
        // 等号右侧为 head，意思就是设置 5 的下一个节点是 4
        
        // 这里出现了两个 next
        // 第一个 next 是「获取」 head 的下一节点
        // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
		    head.next.next = head;


		    // head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了
        // 否则会发生无限循环
		    head.next = null;

		   // 我们把每次反转后的结果传递给上一层
		   return cur;
	}
}