Java剑指Offer精讲：链表反转、回文检测与二叉树展开实战

单链表的完全反转

处理链表问题时，最基础且高频的操作是将链表进行原地反转。该操作通常采用迭代方式，通过维护三个指针来实现节点的重新指向，避免内存空间的额外浪费。操作时需注意边界条件，如链表为空或仅有一个节点时的直接返回。

在 Java 中，我们定义 Solution 类来实现这一逻辑。使用 pre 记录前驱节点，cur 作为当前移动节点，nxt 暂存后继节点以防止断链。循环直到 cur 为空，最终返回新的头节点 pre。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

K个一组链表翻转

当需要对链表进行分组反转时，需先统计剩余节点数量是否满足组数要求。如果不满足，则保留原有顺序；如果满足，则对该组进行局部反转，并将前一组的尾节点连接到反转后的新头部。

该方法利用了递归思想。首先通过快指针 b 向前移动 k 步来确认区间，若中途为空则说明剩余不足 k 个，直接返回。随后调用辅助方法 reverse(a, b) 完成局部反转，并通过递归调用处理后续节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
         if (head == null) return null;
         ListNode a = head, b = head;
         for (int i = 0; i < k; i++) {
            if (b == null) return head;
             b = b.next;
         }
         ListNode newHead = reverse(a, b);
         a.next = reverseKGroup(b, k);
         return newHead;
    }
    
    private ListNode reverse(ListNode a, ListNode b) {
        ListNode pre = null;
        ListNode cur = a;
        while(cur != b){
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

基于后序遍历的回文链表判定

判断链表是否为回文结构，除了双指针法外，还可以利用递归的后序遍历特性。由于递归调用栈天然具备“后进先出”的特性，当递归到达链表末尾开始回溯时，实际上是从后往前访问节点，这与从前往后的外层变量形成了对比。

我们在 Solution 中设置一个实例变量 left 初始化为头节点。traverse 方法负责递归至尾部，并在回溯过程中比较 right（当前栈帧节点）与 left 的值，同时推进 left 指针。只有所有对应位置相等，才返回真值。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    ListNode left;
    public 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;
    }
}

二叉树的镜像翻转

翻转二叉树是递归应用的典型场景。核心逻辑是将根节点的左子树与右子树互换，然后递归地对左右子树执行相同的操作，直至叶子节点。

在代码实现中，当遇到空节点时直接返回 null。否则，分别递归获取翻转后的左子树 lf 和右子树 rg，然后将 root.left 指向 rg，root.right 指向 lf，最后返回 root 即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode lf = invertTree(root.left);
        TreeNode rg = invertTree(root.right);
        root.left = rg;
        root.right = lf;
        return root;
    }
}

完美二叉树的节点右侧连接

对于完美二叉树（Perfect Binary Tree），每个节点都有两个子节点，且所有叶子在同一层。任务是让每个节点的 next 指针指向其同层的下一个右侧节点。

我们可以编写一个辅助函数 method(left, right)，它负责处理父节点的两个孩子 left 和 right 之间的连线。逻辑包括：
1. 将 left.next 指向 right。
2. 递归连接 left 的内部子节点。
3. 递归连接 right 的内部子节点。
4. 递归跨越连接 left 的右子节点与 right 的左子节点（这是跨树边连接的关键）。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;
    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
 
class Solution {
    public Node connect(Node root) {
        if(root==null) return null;
        method(root.left, root.right);
        return root;
    }
    
    private void method(Node left, Node right){
        if (left == null || right == null) {
            return;
        }
        left.next = right;
        method(left.left, left.right);
        method(right.left, right.right);
        method(left.right, right.left);
    }
}

二叉树转化为展开链表

将二叉树“展开”为单链表，意味着在保持某种遍历顺序（通常是前序遍历）的前提下，使所有节点的 left 指针为 null，right 指针指向下一个节点。

算法采用自底向上的递归策略。首先递归处理左子树和右子树。此时，左子树和右子树都已经处理成链表形态。接下来，将根的左子树整体移动到根的右边（即 root.right = left，并断开原 left 链接）。找到处理后链表的最末端节点 p，将其 right 指向原来的右子树链表头。这样就实现了按顺序合并。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
 
        flatten(root.left);
        flatten(root.right);
 
        TreeNode left = root.left;
        TreeNode right = root.right;
 
        root.left = null;
        root.right = left;
 
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        p.right = right;
    }
}