递归与搜索算法实战：汉诺塔、链表操作及快速幂

注：针对特定笔试场景，若仅需返回结果数组，可直接赋值 c = a，但面试中建议展示完整逻辑。

2. 合并两个有序链表

解题思路

利用递归比较两个链表头结点的值，较小者作为当前头结点，其 next 指针指向剩余部分的合并结果。

代码实现

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 递归出口：任一链表为空，返回另一链表
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;

        // 比较大小，递归处理剩余部分
        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

3. 反转链表

解题思路

递归反转的本质是：先反转 head 之后的链表，然后将 head 接在反转后链表的尾部。

代码实现

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 边界检查：空表或单节点无需反转
        if (head == nullptr || head->next == nullptr) return head;

        // 递归反转后续节点
        ListNode* newHead = reverseList(head->next);
        
        // 调整指针方向
        head->next->next = head;
        head->next = nullptr;

        return newHead;
    }
};

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

解题思路

宏观视角下，交换当前两个节点后，递归处理剩余的节点对。需注意处理空指针和尾节点情况。

代码实现

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        // 出口：节点为空或只剩一个节点
        if (head == nullptr || head->next == nullptr) return head;

        // 递归处理后续节点对
        auto tmp = swapPairs(head->next->next);
        auto ret = head->next;
        
        // 交换当前两个节点
        head->next->next = head;
        head->next = tmp;

        return ret;
    }
};

5. Pow(x, n)

解题思路

普通乘法时间复杂度为 O(n)，利用快速幂可将复杂度降至 O(log n)。核心思想是二分：x^n = (x^(n/2))^2。注意处理负指数情况。

代码实现

class Solution {
public:
    double myPow(double x, int n) {
        // 处理负数指数，转为正数计算后取倒数
        return n < 0 ? 1.0 / pow(x, -(long long)n) : pow(x, n);
    }

private:
    double pow(double x, long long n) {
        // 递归出口
        if (n == 0) return 1.0;

        // 递归计算一半
        double tmp = pow(x, n / 2);
        
        // 根据奇偶性返回结果
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
};

以上五种题型涵盖了递归的基础应用与优化技巧。掌握这些模式后，面对类似的树形结构或分治问题会有更清晰的思路。