单链表
- 递归反转链表
- k个一组反转链表
- 回文链表
图片来源于网络
1. 递归反转链表
单链表节点的结构如下：
public class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
1.1 递归反转整个单链表
/**
* 递归反转整个单链表
*/
private ListNode reverse(ListNode head) {
if (head.next == null) return head; // base case
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
值得注意的是：
- 递归函数要有 base case
- 当链表递归反转之后，新的头节点是
last，而之前的head变成了最后一个节点，链表的末尾要指向null
1.2 反转链表前 N 个节点
ListNode successor = null; // 后驱节点
/**
* 将链表的前 n 个节点反转（n <= 链表长度）
*/
private ListNode reverseN(ListNode head, int n) {
if (n == 1) { // base case
successor = head.next; // 记录第 n + 1 个节点
return head;
}
ListNode last = reverseN(head.next, n - 1); // 以 head.next 为起点，需要反转前 n - 1 个节点
head.next.next = head;
head.next = successor; // 让反转之后的 head 节点和后面的节点连起来
return last;
}
值得注意的是：
- base case 变为n == 1，反转一个元素，就是它本身，同时要记录后驱节点。
- 上面
head节点在递归反转之后不一定是最后一个节点，所以要记录后驱successor（第 n + 1 个节点），反转之后将head连接上。
1.3 反转链表的一部分
/**
* 反转链表的一部分：反转从位置 m 到 n 的链表
*/
private ListNode reverseBetween(ListNode head, int m, int n) {
if (m == 1) { // base case
return reverseN(head, n); // 相当于反转前 n 个元素
}
// 前进到反转的起点触发 base case
head.next = reverseBetween(head.next, m - 1, n - 1);
return head;
}
递归处理的技巧是：不要跳进递归，而是利用明确的定义来实现算法逻辑。
注：递归操作链表并不高效。和迭代解法相比，虽然时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，而递归解法需要堆栈，空间复杂度是 O(N)。
2. k个一组反转链表
力扣25题：给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
K 个一组翻转链表示例
/**
* 用迭代的方式反转整个链表
* 反转以 a 为头结点的链表
*/
private ListNode reverseByIteration(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) 的元素，注意是左闭右开
*/
private ListNode reverse(ListNode a, ListNode b) {
ListNode pre, cur, nxt;
pre = null;
cur = a;
nxt = a;
while (cur != b) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
/**
* k 个一组反转链表
*/
private ListNode reverseKGroup(ListNode head, int k) {
if (head == null) {
return null;
}
// 区间 [a, b) 包含 k 个待反转元素
ListNode a, b;
a = head;
b = head;
for (int i = 0; i < k; i++) {
// 不足 k 个，不需要反转，base case
if (b == null) return head;
b = head.next;
}
// 反转前 k 个元素
ListNode newHead = reverse(a, b);
// 递归反转后续链表并连接起来
a.next = reverseKGroup(b, k);
return newHead;
}
解题技巧：分解问题、发现递归性质。
3. 回文链表
在讲回文链表前先了解下回文串：回文串就是正着读和反着读都一样的字符串，如下：
/**
* 判断一个字符串是不是回文串
*/
private boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
// 从两端向中间逼近
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
因为回文串是对称的，所以正着读和倒着读应该是一样的，这一特点是解决回文串问题的关键。
判断一个字符串是否是回文串，无需考虑奇偶情况，采用「双指针技巧」，从两端向中间逼近即可。
而寻找回文串的核心思想是从中心向两端扩展：
/**
* 寻找回文串
*/
private String palindrome(String s, int l, int r) {
// 防止索引越界
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
// 向两边展开
l--;
r++;
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
return s.substring(l + 1, r - l - 1);
}
3.1 判断回文单链表
输入一个单链表的头结点，判断这个链表中的数字是不是回文
思路：单链表无法倒着遍历，无法使用双指针技巧。简单办法是把原始链表反转存入一条新的链表，然后比较这两条链表是否相同。
ListNode left;// 左侧指针
/**
* 输入一个单链表的头结点，判断这个链表中的数字是不是回文
* 难点：单链表无法倒着遍历，无法使用双指针技巧
*/
private boolean isPalindrome(ListNode head) {
left = head;
return traverse(head);
}
/**
* 借助二叉树后序遍历的思路，不需要显式反转原始链表也可以倒序遍历链表
*/
private 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;
}
上面核心逻辑：把链表节点放入一个栈，然后再拿出来，这时候元素顺序就是反的，利用递归函数的堆栈即可。
缺点：无论造一条反转链表还是利用后续遍历，算法的时间和空间复杂度都是 O(N)
3.2 优化上面的空间复杂度
思路：由于回文的特殊性，可以不完全反转链表，而是仅仅反转部分链表，将空间复杂度降到 O(1)，但需要注意链表长度的奇偶。
/**
* 输入一个单链表的头结点，判断这个链表中的数字是不是回文
* <p>
* 优化后：算法总体的时间复杂度 O(N)，空间复杂度 O(1)
*/
private boolean isPalindrome2(ListNode head) {
// 1. 先通过 双指针技巧汇总 中的快慢指针来找到链表的中点
ListNode slow = head, 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;
}
/**
* 反转链表
*/
private ListNode reverse(ListNode head) {
ListNode pre = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
缺点：上面解法虽然高效，但破坏了输入链表的原始结构。
总结：上述的题目都涉及链表的递归操作，是训练递归思维的练手题目，通过这些题目可以对递归有一个直观的认识。
参考链接：
