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

文章目录1. 汉诺塔问题2. 合并两个有序链表3. 反转链表4. 两两交换链表中的节点5. 快速幂1. 汉诺塔问题题目链接汉诺塔问题题目描述题解思路递归将 n 个盘子从 A 柱移到 C 柱以 A 为起点、C 为目标、B 为辅助拆分为三个步骤其中包含两个结构完全相同的子问题子问题一将上面 n-1 个盘子从 A 柱移到 B 柱以 A 为起点、B 为目标、C 为辅助独立操作将最底层唯一的最大盘子从 A 柱直接移到 C 柱子问题二将n-1 个盘子从 B 柱移到 C 柱以 B 为起点、C 为目标、A 为辅助两个子问题与原问题的解题逻辑完全一致仅盘子数量、柱子角色不同符合递归的拆分要求。每一层递归只处理固定数量的盘子移动执行完整的三步流程先递归调用自身完成上层 n-1 个盘子的转移为最大盘子腾出移动空间执行唯一的直接移动操作将当前最底层的最大盘子移到目标柱再次递归调用自身将之前转移走的 n-1 个盘子从辅助柱移到目标柱叠在最大盘子之上递归过程自顶向下拆分问题自底向上逐步完成移动最终合并为完整解。当盘子数量 n 1 时无需再拆分直接将这一个盘子从起始柱移到目标柱即可。示例代码classSolution{publicvoidhanota(ListIntegerA,ListIntegerB,ListIntegerC){movePlant(A,B,C,A.size());}publicvoidmovePlant(ListIntegerstart,ListIntegertemp,ListIntegertarget,intsize){if(size1){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. 合并两个有序链表题目描述题解思路递归递归函数接收两个有序链表的头节点将它们合并为一个新的有序链表并返回合并后链表的头节点。函数体逻辑比较两个链表当前头节点的值选择值较小的节点作为合并后链表的头节点然后将该节点的next指针指向「剩余两个链表」递归合并后的结果。递归出口当其中一个链表为空时直接返回另一个非空链表空链表也会被正确处理。示例代码classSolution{publicListNodemergeTwoLists(ListNodelist1,ListNodelist2){if(list1null)returnlist2;if(list2null)returnlist1;if(list1.vallist2.val){list1.nextmergeTwoLists(list1.next,list2);returnlist1;}else{list2.nextmergeTwoLists(list2.next,list1);returnlist2;}}}3. 反转链表题目链接206. 反转链表题目描述题解思路递归递归函数接收一个链表的头指针完成链表逆序操作并返回逆序后链表的头节点。函数体逻辑先递归处理「当前节点之后的子链表」并完成逆序再将当前节点添加到已逆序的子链表末尾。递归出口当当前节点为空或当前链表仅含一个节点时无需逆序直接返回当前节点。示例代码classSolution{publicListNodereverseList(ListNodehead){if(headnull||head.nextnull)returnhead;ListNodenewNodereverseList(head.next);head.next.nexthead;head.nextnull;returnnewNode;}}4. 两两交换链表中的节点题目链接24. 两两交换链表中的节点题目描述题解思路递归递归函数接收一个链表完成链表节点的两两交换并返回交换后链表的头节点。函数体逻辑先递归处理「第二个节点之后的子链表」再将当前的两个节点进行交换最后将交换后的当前节点组与已处理好的后续子链表连接。递归出口当当前节点为空或当前链表仅含一个节点时无需交换直接返回当前节点。示例代码classSolution{publicListNodeswapPairs(ListNodehead){if(headnull||head.nextnull)returnhead;ListNodenewNodeswapPairs(head.next.next);ListNodetemphead.next;temp.nexthead;head.nextnewNode;returntemp;}}5. 快速幂题目链接50. Pow(x,n)题目描述题解思路快速幂这道题递归的核心是不直接算 xⁿ而是把它拆成规模更小、解法完全相同的子问题递归解决后再合并答案。就是求 x 的 n 次方 求 x 的 n/2 次方 × 自己再根据奇偶决定是否多乘一个 xn是奇数则多乘一个 x负数处理x 的负 n 次方 1 / (x 的正 n 次方)先把负指数变成正指数仍然用上面完全相同的递归逻辑计算最后取倒数即可。示例代码classSolution{publicdoublemyPow(doublex,intn){returnn0?1.0/pow(x,-n):pow(x,n);}publicdoublepow(doublex,intn){if(n0)return1.0;doubletmppow(x,n/2);returnn%20?tmp*tmp:tmp*tmp*x;}}