一些算法

快速幂算法

传统的求幂算法，当n非常大的时候，需要执行的循环次数也非常多，算法的复杂度为O(N)

快速幂算法能以O(logN)的复杂度计算非常大的幂，核心思想就是每一步把指数分成两半，而相应的底数做平方运算

例子：

$3^{10}$ = $9^5$

此时指数缩减为原来的一半，底数变为原来的平方

而对于 $9^5$ 指数不能缩减为原来的一半，但可以

$9^5$ = $9^4 * 9^1$

对于剩下的 $9^4$ 继续进行指数缩减为原来的一半的操作

$3^{10} = 9^5 = (9^4)(9^1) = (81^2)(9^1) = (6561^1)*(9^1)$

快慢指针

假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

一快一慢。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针（如果存在环，在进入环后每次移动快指针和慢指针的距离减小1），就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。