相爱相杀好基友——数组与链表
作为线性表的两种存储方式—-链表和数组，各有优缺点
面试问题
无法高效获取长度，无法根据下标快速找到访问元素，是链表的两个劣势；然而面试中会经常碰到诸如如何获取第k个元素、获取中间位置元素、判断链表是否存在环、判断环的长度这些与长度和位置有关的问题。都可以用双指针来解决
Tips：双指针并不是固定的公式，而是一种思维方式
- 倒数第k个问题
设有两个指针 p 和 q，初始时都指向头节点。首先，先让 q 沿着 next 移动 k 次；此时，p 指向头节点，q 指向 k+1 个节点，两个指针的距离为 k。然后，同时移动 p 和 q，直到 q 指向空，此时，p 指向倒数第 k 个节点
获取中间元素问题
遍历一遍链表，得知链表长度；即可知道中间元素，再次遍历（u1s1，有点蠢）
设有两个指针 a 和 b。每次移动时，a 向前走一次，b 向前走两次，直到 b 无法再走两次；即 b.next.next=null ；
设链表长度为 n，那么最多移动 n/2 轮。当 n 为奇数，a 恰好指向中间节点；当 n 为偶数，a 恰好指向中间两个节点靠前的那个
是否存在环的问题。如果尾节点的指针指向其他任意一个节点，就代表有环的存在
当链表有环，快慢指针会陷入无限次移动，然后变成追击问题；快指针一次移动两步，慢指针一次移动一步；只要一直移动下去，快指针总会追上慢指针；快慢指针相遇，代表有环的存在
最后，如果存在环，如何判断环的长度？快慢指针继续移动，直到相遇第二次。两次相遇间的移动次数即为环的长度