递归反转单链表
反转从位置m到n的链表，请使用一趟扫描完成反转；说明：1 <= m <= n <= 链表长度
递归反转整个单链表
// 单链表节点的结构
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
ListNode reverse(ListNode head) {
if (head.next == null) return head;
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
对于递归算法，最重要的就是明确递归函数的定义。具体来说，我们的reverse函数定义是这样的：
输入一个节点head，将「以head为起点」的链表反转，并返回反转之后的头结点。
1、递归函数要有 base case，也就是这句：
if (head.next == null) return head;
意思是如果链表只有一个节点的时候反转也是它自己，直接返回即可。
2、当链表递归反转之后，新的头节点是last，而之前的head变成了最后一个节点，别忘了链表的末尾要指向 null：
head.next = null;
反转链表前N个节点
ListNode successor = null; // 后驱节点
// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// 记录第 n + 1 个节点
successor = head.next;
return head;
}
// 以 head.next 为起点，需要反转前 n - 1 个节点
ListNode last = reverseN(head.next, n - 1);
head.next.next = head;
// 让反转之后的 head 节点和后面的节点连起来
head.next = successor;
return last;
}
具体的区别：
1、base case 变为n == 1，反转一个元素，就是它本身，同时要记录后驱节点。
2、刚才我们直接把head.next设置为 null，因为整个链表反转后原来的head变成了整个链表的最后一个节点。但现在head节点在递归反转之后不一定是最后一个节点了，所以要记录后驱successor（第 n + 1 个节点），反转之后将head连接上。
反转链表的一部分
ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
return reverseN(head, n);
}
// 前进到反转的起点触发 base case
head.next = reverseBetween(head.next, m - 1, n - 1);
return head;
}
首先，如果m == 1，就相当于反转链表开头的n个元素嘛，也就是我们刚才实现的功能
如果m != 1怎么办？如果我们把head的索引视为 1，那么我们是想从第m个元素开始反转对吧；如果把head.next的索引视为 1 呢？那么相对于head.next，反转的区间应该是从第m - 1个元素开始的；那么对于head.next.next呢……
k个一组反转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
分析：
链表是一种兼具递归和迭代性质的数据结构，认真思考一下可以发现这个问题具有递归性质。
1、先反转以 head 开头的 k 个元素。
2、将第 k + 1 个元素作为 head 递归调用 reverseKGroup 函数。
3、将上述两个过程的结果连接起来。
如果最后的元素不足 k 个，就保持不变。 这就是 base case
代码
// 迭代反转以 a 为头结点的链表
ListNode reverse(ListNode a) {
ListNode pre, cur, nxt;
pre = null; cur = a; nxt = a;
while (cur != null) {
nxt = cur.next;
// 逐个结点反转
cur.next = pre;
// 更新指针位置
pre = cur;
cur = nxt;
}
// 返回反转后的头结点
return pre;
}
/** 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b) {
ListNode pre, cur, nxt;
pre = null; cur = a; nxt = a;
// while 终止的条件改一下就行了
while (cur != b) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
// 返回反转后的头结点
return pre;
}
ListNode reverseKGroup(ListNode head, int k) {
if (head == null) return null;
// 区间 [a, b) 包含 k 个待反转元素
ListNode a, b;
a = b = head;
for (int i = 0; i < k; i++) {
// 不足 k 个，不需要反转，base case
if (b == null) return head;
b = b.next;
}
// 反转前 k 个元素
ListNode newHead = reverse(a, b);
// 递归反转后续链表并连接起来
a.next = reverseKGroup(b, k);
return newHead;
}
如何高效判断回文单链表？
输入一个单链表的头结点，判断这个链表中的数字是不是回文.
分析：
这道题的难点在于，单链表无法倒着遍历，无法使用双指针技巧。
那么最简单的办法就是，把原始链表反转存入一条新的链表，然后比较这两条链表是否相同。
其实，借助二叉树后序遍历的思路，不需要显式反转原始链表也可以倒序遍历链表，下面来具体聊聊。
链表兼具递归结构，树结构不过是链表的衍生。那么，链表其实也可以有前序遍历和后序遍历：
void traverse(ListNode head) {
// 前序遍历代码
traverse(head.next);
// 后序遍历代码
}
这个框架有什么指导意义呢？如果我想正序打印链表中的val值，可以在前序遍历位置写代码；反之，如果想倒序遍历链表，就可以在后序遍历位置操作：
/* 倒序打印单链表中的元素值 */
void traverse(ListNode head) {
if (head == null) return;
traverse(head.next);
// 后序遍历代码
print(head.val);
}
说到这了，其实可以稍作修改，模仿双指针实现回文判断的功能：
// 左侧指针
ListNode left;
boolean isPalindrome(ListNode head) {
left = head;
return traverse(head);
}
boolean traverse(ListNode right) {
if (right == null) return true;
boolean res = traverse(right.next);
// 后序遍历代码
res = res && (right.val == left.val);
left = left.next;
return res;
}
这么做的核心逻辑是什么呢？实际上就是把链表节点放入一个栈，然后再拿出来，这时候元素顺序就是反的，只不过我们利用的是递归函数的堆栈而已。
优化空间复杂度
更好的思路是这样的：
1、先通过 双指针技巧汇总 中的快慢指针来找到链表的中点：
ListNode slow, fast;
slow = fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow 指针现在指向链表中点
2、如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步,才是反转的开始位置：
if (fast != null)
slow = slow.next;
3、从slow开始反转后面的链表，现在就可以开始比较回文串了：
ListNode left = head;
ListNode right = reverse(slow);
while (right != null) {
if (left.val != right.val)
return false;
left = left.next;
right = right.next;
}
return true;
算法总体的时间复杂度 O(N)，空间复杂度 O(1)，已经是最优的了。(另外可能需要还原链表)