概念
快慢指针是指移动的步长，即每次向前移动速度的快慢。（例如，让快指针每次沿链表向前移动2，慢指针每次向前移动1）
应用
1.判断单链表是否存在环。如果快指针到达NULL，说明链表以NULL结尾，不存在环。如果快指针追上慢指针，则表示有环。
struct list_node{int data;list_node* next;};bool is_loop(list_node* head){list_node* n1 = head;list_node* n2 = head;while (n2->next != NULL){n1 = n1->next;n2 = n2->next->next;if (n1 == n2)return true;}if (n2->next == NULL)return false;}2.寻找循环链表的入口
将设链表长为L,起始点到环入口长度为a,环长为r，则L=r+a;如上图。在快指针进入到环到慢指针进入环前的这段时间，若环的长度较短，也许快指针已经走了好几圈。然后慢指针进入环，设慢指针和快指针相遇时，慢指针在环内走了X步，走的总步数为S步（S=a+X）,此时快指针在环内走了n圈加X步，即为nr+X步，其中n最少为1，走的总步数为：nr+X+a步。由于快指针走的总步数为慢指针走的总步数的两倍，所以nr+X+a=(X+a)*2的X+a=nr.
即a=nr-X=(n-1)r+r-X
结论：环入口距离起点的距离（a）和相遇点距离环入口的距离（r-x）相差整数倍的r.
故让慢指针回到起点，快指针从相遇点开始继续走，步长都为1，则两者再相遇时，即为环入口。此时慢指针走了a步，快指针走了a步（(n-1)r+r-X）；
struct list_node{int data;list_node* next;};list_node * FindBeginning(list_node* head){list_node*n1 = head;list_node*n2 = head;while (n2->next != NULL){n1 = n1->next;n2 = n2->next->next;if (n1 == n2)break;}if (n2->next == NULL)return NULL; //没有相遇，没有环n1 = head; ///n1从head 开始移动，n2从相遇点开始移动。while (n1 != n2){n1 = n1->next;n2 = n2->next;}return n2;}3.在有序链表中寻找中位数。原理：快指针移动速度是慢指针移动速度的两倍。所以快指针到达链表尾时，慢指针到达中点。（需要判断链表节点奇偶数）如果快指针移动x步到达表尾则为奇数。若为倒数第二个节点则为偶数（可根据规则返回上中位或下中位或上下一半）；
4.两个单向链表判断他们是否相交
思路：首先用快慢指针判断是否有环
1）如果都没有环，如果两个单链表有公共结点，则两个单链表从某个结点开始，他们的next指向同一结点。（由于是单链表结点，每一结点只有一个next,所以从第一个公共结点开始，他们所有结点都是重合的）。既若两个单链表的末尾结点相同则相交。寻找第一个相交结点的方法：
a.在其中一个单链表上顺序遍历每个结点，每遍历一个结点，在另外一个链表上顺序遍历每个结点。
时间复杂度（O（mn））
b.首先两个链表各遍历一次求表长l1,l2，两链表差为l.然后现在长的链表上遍历L,然后同步遍历，第一个相同的结点就是公共结点。时间复杂度（O（m+n））
2)如果一个存在环，另外一个不存在环则不可能相交。
3)如果利用快慢指针发现两单链表都存在环，则判断一个链表上快慢指针相遇的那个结点是否在另一个链表上。如果在则相交，否在不相交。如果相交，两个链表的入口点可能不是环上同一结点，利用上边的方法分别找出各自的入口点，可以定义任意一个入口点为相交的第一个结点。