递归经典实战：汉诺塔、链表操作与快速幂详解

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list2.next, list1);
            return list2;
        }
    }
}

3. 反转链表

反转链表是面试高频题。递归解法比迭代更优雅，但需要理清指针回退的顺序。

逻辑上分两步：先递归反转当前节点之后的子链表，拿到反转后的头节点；然后把当前节点的 next 指向它自己（即原前驱），并将当前节点的 next 置为 null。注意，递归出口是 head 为空或只有一个节点时，直接返回 head。

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode newNode = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newNode;
    }
}

4. 两两交换链表中的节点

这个题目可以看作是反转链表的变种，只是每次只交换相邻的两个节点。

递归策略很清晰：先递归处理第二个节点之后的部分，拿到后续已交换好的链表头；然后将当前两个节点互换位置，并连接到后续链表上。如果链表只剩一个节点或为空，则不需要交换，直接返回。

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode newNode = swapPairs(head.next.next);
        ListNode temp = head.next;
        temp.next = head;
        head.next = newNode;
        return temp;
    }
}

5. 快速幂

计算 x 的 n 次方，暴力循环时间复杂度是 O(n)，而利用分治思想可以将复杂度降为 O(log n)。

核心逻辑是：x^n = (x^(n/2))^2。根据 n 的奇偶性，如果是奇数再乘一个 x。对于负指数，先转为正数计算后再取倒数。这里要注意整数溢出问题，但在 LeetCode 环境下通常按题目给定的范围处理。

class Solution {
    public double myPow(double x, int n) {
        return n < 0 ? 1.0 / pow(x, -n) : pow(x, n);
    }

    private double pow(double x, int n) {
        if (n == 0) return 1.0;
        double tmp = pow(x, n / 2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
}