一、反转整个链表
问题：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
//单链表的实现结构
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x;}
}
反转链表利用迭代不难实现，如果使用递归则有些许难度。
首先来看源码实现：
ListNode reverse(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode ret = reverse(head.next);
head.next.next = head;
head.next = null;
return ret;
}
是否看起来不知所云，而又被这如此简洁的代码所震撼？让我们一起探索一下其中的奥秘。
对于递归算法，最重要的是明确递归函数的定义。
我们的 reverse函数的定义如下：
输入一个节点 head,将以 head 为起点的链表反转，并返回反转之后的头节点。
明白了函数的定义后，在来看这个问题。比如我们想反转这个链表
那么输入 reverse（head）后，会在 ListNode ret = reverse(head.next);进行递归
不要跳进递归！（你的脑袋能压几个栈呀？）
根据 reverse函数的定义，函数调用后会返回反转之后的头节点，我们用变量 ret接收
现在再来看一下代码
head.next.next = head;
接下来：
head.next = null;
return ret;
再跳出这层递归就会得到：
神不神奇，这样整个链表就反转过来了！
递归代码就是这么简洁优雅，但要注意两个问题：
1、递归函数要有base case，不然就会一直递归，导致栈溢出
if (head == null || head.next == null) return head;
即链表为空或只有一个节点，直接返回
2、当链表递归反转后，新的头节点为 ret,而 head变成了最后一个节点，应该令链表的某尾指向 null
head.next = null;
理解这两个问题之后，我们可以进一步深入研究链表反转的问题，接下来的问题其实均为在这个算法上的扩展。
二、反转链表前N个节点
接下来我们来看这个问题：
问题：反转链表前N个节点，并返回链表头节点
说明：1
Original: https://www.cnblogs.com/Code-CHAN/p/13620048.html
Author: Code-CHAN
Title: 利用递归方法实现链表反转、前N个节点反转以及中间部分节点反转
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584185/
转载文章受原作者版权保护。转载请注明原作者出处！