单链表

• 递归反转链表
• 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;
    }

缺点：上面解法虽然高效，但破坏了输入链表的原始结构。

总结：上述的题目都涉及链表的递归操作，是训练递归思维的练手题目，通过这些题目可以对递归有一个直观的认识。

---

参考链接：

递归反转链表：如何拆解复杂问题

递归思维：k 个一组反转链表

如何高效判断回文单链表？