【算法通关】递归：汉诺塔、合并链表、反转链表、两两交换、快速幂全解

1. 汉诺塔问题

题目链接：汉诺塔问题
题目描述：

题解思路：递归

将 n 个盘子从 A 柱移到 C 柱（以 A 为起点、C 为目标、B 为辅助）拆分为三个步骤，其中包含两个结构完全相同的子问题：

1. 子问题一：将上面 n-1 个盘子从 A 柱移到 B 柱（以 A 为起点、B 为目标、C 为辅助）
2. 独立操作：将最底层唯一的最大盘子从 A 柱直接移到 C 柱
3. 子问题二：将n-1 个盘子从 B 柱移到 C 柱（以 B 为起点、C 为目标、A 为辅助）

两个子问题与原问题的解题逻辑完全一致，仅盘子数量、柱子角色不同，符合递归的拆分要求。

每一层递归只处理固定数量的盘子移动，执行完整的三步流程：

1. 先递归调用自身，完成上层 n-1 个盘子的转移，为最大盘子腾出移动空间
2. 执行唯一的直接移动操作，将当前最底层的最大盘子移到目标柱
3. 再次递归调用自身，将之前转移走的 n-1 个盘子，从辅助柱移到目标柱，叠在最大盘子之上

递归过程自顶向下拆分问题，自底向上逐步完成移动，最终合并为完整解。当盘子数量 n = 1 时，无需再拆分，直接将这一个盘子从起始柱移到目标柱即可。

示例代码：

classSolution{publicvoidhanota(List<Integer>A,List<Integer>B,List<Integer>C){movePlant(A,B,C,A.size());}publicvoidmovePlant(List<Integer>start,List<Integer>temp,List<Integer>target,intsize){if(size==1){target.add(start.remove(start.size()-1));return;}// a 借助 c 将n-1个盘子放到bmovePlant(start,target,temp,size-1);// a 剩下的一个盘子 放到ctarget.add(start.remove(start.size()-1));// b 借助a 将 n-1 个盘子放到cmovePlant(temp,start,target,size-1);}}

2. 合并两个有序链表

题目链接：21. 合并两个有序链表
题目描述：

题解思路：递归

1. 递归函数：接收两个有序链表的头节点，将它们合并为一个新的有序链表，并返回合并后链表的头节点。
2. 函数体逻辑：比较两个链表当前头节点的值，选择值较小的节点作为合并后链表的头节点，然后将该节点的next指针指向「剩余两个链表」递归合并后的结果。
3. 递归出口：当其中一个链表为空时，直接返回另一个非空链表（空链表也会被正确处理）。

示例代码：

classSolution{publicListNodemergeTwoLists(ListNodelist1,ListNodelist2){if(list1==null)returnlist2;if(list2==null)returnlist1;if(list1.val<=list2.val){list1.next=mergeTwoLists(list1.next,list2);returnlist1;}else{list2.next=mergeTwoLists(list2.next,list1);returnlist2;}}}

3. 反转链表

题目链接：206. 反转链表
题目描述：

题解思路：递归

1. 递归函数：接收一个链表的头指针，完成链表逆序操作，并返回逆序后链表的头节点。
2. 函数体逻辑：先递归处理「当前节点之后的子链表」并完成逆序，再将当前节点添加到已逆序的子链表末尾。
3. 递归出口：当当前节点为空，或当前链表仅含一个节点时，无需逆序，直接返回当前节点。

示例代码：

classSolution{publicListNodereverseList(ListNodehead){if(head==null||head.next==null)returnhead;ListNodenewNode=reverseList(head.next);head.next.next=head;head.next=null;returnnewNode;}}

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

题目链接：24. 两两交换链表中的节点
题目描述：

题解思路：递归

1. 递归函数：接收一个链表，完成链表节点的两两交换，并返回交换后链表的头节点。
2. 函数体逻辑：先递归处理「第二个节点之后的子链表」，再将当前的两个节点进行交换，最后将交换后的当前节点组与已处理好的后续子链表连接。
3. 递归出口：当当前节点为空，或当前链表仅含一个节点时，无需交换，直接返回当前节点。

示例代码：

classSolution{publicListNodeswapPairs(ListNodehead){if(head==null||head.next==null)returnhead;ListNodenewNode=swapPairs(head.next.next);ListNodetemp=head.next;temp.next=head;head.next=newNode;returntemp;}}

5. 快速幂

题目链接：50. Pow(x,n)
题目描述：

题解思路：快速幂

这道题递归的核心是：不直接算 xⁿ，而是把它拆成规模更小、解法完全相同的子问题，递归解决后再合并答案。
就是求 x 的 n 次方 = 求 x 的 n/2 次方 × 自己（再根据奇偶决定是否多乘一个 x，n是奇数则多乘一个 x）

负数处理：
x 的负 n 次方 = 1 / (x 的正 n 次方)，先把负指数变成正指数，仍然用上面完全相同的递归逻辑计算，最后取倒数即可。

示例代码：

classSolution{publicdoublemyPow(doublex,intn){returnn<0?1.0/pow(x,-n):pow(x,n);}publicdoublepow(doublex,intn){if(n==0)return1.0;doubletmp=pow(x,n/2);returnn%2==0?tmp*tmp:tmp*tmp*x;}}