文章目录
- 递归、搜索与回溯——递归
- 两两交换链表中的节点
- Pow(x, n)
递归、搜索与回溯——递归
该文仍然是解决递归问题，值得注意的是快速幂算法。接下来会系统学习二叉树深搜题目，慢慢走向搜索与回溯。
两两交换链表中的节点
原题链接：24. 两两交换链表中的节点 - 力扣（LeetCode）
先模拟一下示例1：
按照题目要求，结点1和结点2需要交换，由于题目要求只能通过更改指针指向来进行交换操作，所以结点2的next指针一定需要指向结点1，此时整个链表就被分割为两个独立的链表了，即结点3找不到。所以，我们需要先对后面的结点进行交换操作，结点4的next指针一定需要指向结点3，此时结点4和结点3相当于已经交换完毕了，此时要对结点1和结点2进行交换并将其加入到结点4和结点3链表中，结点2的next指针要指向结点1，结点1的next结点要指向结点4。
与反转链表有相似之处，都需要“后序遍历”，不断将前面的结点加入完成任务的链表中，不同之处在于，该题目每次要将交换后的两个结点加入完成任务的链表中。
将递归方法看作一个黑盒子，它要完成的任务就是：将head以及其后的结点构成的链表进行相邻交换并按要求拼接。
当链表为null或者最后一个结点单独存在（没有与之相邻的结点，例如1->2->3->4->5的结点5就是单独存在的结点）直接返回即可。
以宏观的方式编写递归代码：
class Solution {
public ListNode swapPairs(ListNode head) {
//begin
if(head == null || head.next == null) {
return head;
}
ListNode ret = swapPairs(head.next.next);
ListNode tmp = head.next;
head.next.next = head;
head.next = ret;
return tmp;
//end
}
}
Pow(x, n)
原题链接：50. Pow(x, n) - 力扣（LeetCode）
该题目采用暴力方法无法解决，因为当 n 的绝对值过大暴力解法会很慢。这里引入快速幂的算法，用来快速计算Pow问题，具体思路为：
计算x^n时，先计算x^(n/2)，此时x^n = x^(n/2) * x^(n/2)，而计算x^(n/2)时，先计算x^(n/2/2)，x^(n/2) = x^(n/2/2) * x^(n/2/2)，依次类推，直到化简为求x^0再逐层返回，实现了从O(N)到O(logN)。不过，其中要注意的是，n不全为偶数，当n为奇数时，x^n = x^(n/2) * x^(n/2) * x。例如，求4^7（此时n = 7不是偶数），先求4^3，4^7 = 4^3 * 4^3 * 4，求4^3，先求4^1，4^3 = 4^1 * 4^1 * 4……
题目可能会出现 n 为负数的情况，只需要先求x^(-n)，即求x的n的绝对值次幂，再用 1 除 该结果即可。
代码如下：
class Solution {
private double _myPow(double x, int n) {
if(n == 0) {
return 1;
}
double tmp = _myPow(x, n / 2);
return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
}
public double myPow(double x, int n) {
double ret = _myPow(x, Math.abs(n));
if(n < 0) {
return 1 / ret;
}else {
return ret;
}
}
}