快慢指針
快慢指針中的快慢指的是移動的步長，即每次向前移動速度的快慢。例如可以讓快指針每次沿連結清單向前移動2，慢指針每次向前移動1次。
快慢指針的應用
（1）判斷單連結清單是否存在環
如果連結清單存在環，就好像操場的跑道是一個環形一樣。此時讓快慢指針都從連結清單頭開始周遊，快指針每次向前移動兩個位置，慢指針每次向前移動一個位置；如果快指針到達NULL，說明連結清單以NULL為結尾，沒有環。如果快指針追上慢指針，則表示有環。代碼如下：
bool HasCircle(Node *head)
{
if(head == NULL)
return false;
Node *slow = head, *fast = head;
while(fast != NULL && fast->next!=NULL)
{
slow = slow->next; //慢指針每次前進一步
fast = fast->next->next;//快指針每次前進兩步
if(slow == fast) //相遇，存在環
return true;
}
return false;
}
（2）在有序連結清單中尋找中位數
快指針的移動速度是慢指針移動速度的2倍，是以當快指針到達連結清單尾時，慢指針到達中點。
程式還要考慮連結清單結點個數的奇偶數因素，當快指針移動x次後到達表尾（1+2x），說明連結清單有奇數個結點，直接傳回慢指針指向的資料即可。
如果快指針是倒數第二個結點，說明連結清單結點個數是偶數，這時可以根據“規則”傳回上中位數或下中位數或（上中位數+下中位數）的一半。
while (fast && slow)
{
if (fast->next==NULL)
return slow ->data;
else if (fast->next!= NULL && fast->next->next== NULL)
return (slow ->data + slow ->next->data)/2;
else
{
fast= fast->next;
fast= fast->next;
slow = slow ->next;
}
}
(3) 輸對外連結表中的倒數第K個節點(即正數第K-1個節點)
可以定義兩個指針，第一個指針從連結清單的頭指針開始周遊向前走k-1步，第二個指針保持不動；從第K步開始，第二個指針也開始從連結清單的頭指針開始周遊。由于兩個指針的距離保持在k-1，當第一個指針到達連結清單的尾節點時候，第二個指針正好是倒數第K個節點，代碼如下：
// 查找單連結清單中倒數第K個結點
ListNode * RGetKthNode(ListNode * pHead, unsigned int k) // 函數名前面的R代表反向
{
if(k == 0 || pHead == NULL) // 這裡k的計數是從1開始的，若k為0或連結清單為空傳回NULL
return NULL;
ListNode * pAhead = pHead;
ListNode * pBehind = pHead;
for(int i=0;i<k-1;i++){
pAhead=pAhead->next;
if(pAhead==null) return null;//當連結清單長度小于k時候，傳回Null
}
while(pAhead->next != NULL) // 前後兩個指針一起向前走，直到前面的指針指向最後一個結點
{
pBehind = pBehind->next;
pAhead = pAhead->next;
}
return pBehind; // 後面的指針所指結點就是倒數第k個結點
}
(4) 判斷連結清單是否存在環，如果存在，找到環入口
有一個單連結清單，其中可能有一個環，也就是某個節點的next指向的是連結清單中在它之前的節點，這樣在連結清單的尾部形成一環。
如何判斷一個連結清單是否存在環？設定兩個指針slow，fast，均從頭指針開始，每次分别前進1步、2步。如存在環，則兩者相遇；如不存在環，fast遇到NULL退出。
如果連結清單存在環，如果找到環的入口點？當fast若與slow相遇時，slow肯定沒有走周遊完連結清單或者恰好周遊一圈。于是我們從連結清單頭與相遇點分别設一個指針，每次各走一步，兩個指針必定相遇，且相遇第一點為環入口點。
node* findLoopPort(node *head) {
node *fast, *slow;
fast = slow = head;
while (fast && fast->next) {
//第一步：判斷連結清單是否存在環
slow = slow->next;
fast = fast->next->next;
if (slow == fast) { //連結清單存在環
break;
}
}
if ((fast == NULL) || (fast->next == NULL)) { //連結清單不存在環
return NULL;
}
//第二步：尋找環的入口點
slow = head; //讓slow回到連結清單的起點，fast留在相遇點
while (slow != fast) { //當slow和fast再次相遇時，那個點就是環的入口點
slow = slow->next;
fast = fast->next;
}
return slow;
}
(5) 判斷兩個單連結清單是否相交，如果相交，找到他們的第一個公共節點
判斷兩個單連結清單是否相交,如果相交，給出相交的第一個點（假設兩個連結清單都不存在環）。
思路：
首先利用快慢指針判斷連結清單是否存在環。
(1)如果都不存在環，則如果兩個單向連結清單有公共節點，也就是兩個連結清單從某一節點開始，他們的p_next都指向同一個節點，每個節點隻有一個p->next。是以從第一個公共節點開始，之後它們所有節點都是重合的。是以，首先兩個連結清單各周遊一次，求出兩個連結清單的長度L1、L2，然後可以得到它們的長度差L。然後現在長的連結清單上周遊L個節點，之後再同步周遊，于是在周遊中，第一個相同的節點就是第一個公共的節點。此時，若兩個連結清單長度分别為M，N,則時間複雜度為O(M+N).
(2)如果一個存在環，另外一個不存在環，則這兩個連結清單是不可能相交的。
(3)如果利用快慢指針發現兩個連結清單都存在環，則判斷任意一個連結清單上快慢指針相遇的那個節點，在不在另外一個連結清單上，如果在，則相交，不在，則不相交。
下面讨論兩個沒有環的連結清單如果是相交于某一結點的情況：
相交的連結清單示意圖如下所示：
方法一：
兩個沒有環的連結清單如果是相交于某一結點，如上圖所示，這個結點後面都是共有的。是以如果兩個連結清單相交，那麼兩個連結清單的尾結點的位址也是一樣的。程式實作時分别周遊兩個單連結清單，直到尾結點。判斷尾結點位址是否相等即可。時間複雜度為O(L1+L2)。
如何找到第一個相交結點？判斷是否相交的時候，記錄下兩個連結清單的長度，算出長度差len，接着先讓較長的連結清單周遊len個長度，然後兩個連結清單同時周遊，判斷是否相等，如果相等，就是第一個相交的結點。
void Is_2List_Intersect(LinkList L1, LinkList L2) {
if (L1 == NULL || L2 == NULL) {
exit(ERROR);
}
LinkList p = L1;
LinkList q = L2;
int L1_length = 0;
int L2_length = 0;
int len = 0;
while (p->next) {
L1_length ++;
p = p->next;
}
while (q->next) {
L2_length ++;
q = q->next;
}
printf("p: = %d\n", p);
printf("q: = %d\n", q);
printf("L1_length: = %d\n", L1_length);
printf("L2_length: = %d\n", L2_length);
if (p == q) {
printf(" 相交\n");
/*p重新指向短的連結清單 q指向長連結清單*/
if (L1_length > L2_length) {
len = L1_length - L2_length;
p = L2;
q = L1;
}
else {
len = L2_length - L1_length;
p = L1;
q = L2;
}
while (len) {
q = q->next;
len--;
}
while (p != q) {
p = p->next;
q = q->next;
}
printf("相交的第一個結點是：%d\n", p->data );
}
else {
printf("不相交 \n");
}
}
方法二：
另外一個方法則是将一個連結清單首尾相接，然後判斷另外一個連結清單是否有環，如果有環，則兩個連結清單相交。那麼求第一個交點則求出有環的的那個連結清單的環結點即是。
int Is_ListLoop(LinkList L) {
LinkList fast, slow;
if (L == NULL || L->next == NULL) {
exit(ERROR);
}
fast = slow = L;
while (fast->next != NULL && fast->next->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (fast == slow) {
return True;
}
}
return False;
}
int Find_Loop(LinkList L) {
LinkList fast, slow;
if (L == NULL || L->next == NULL) {
exit(ERROR);
}
fast = slow = L;
while (fast->next != NULL && fast->next->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (fast == slow) {
break;
}
}
slow = L;
while (fast != slow) {
slow = slow->next;
fast = fast->next;
}
printf("%d\n", slow->data );
return TRUE;
}
void Is_2List_Intersect2(LinkList L1, LinkList L2) {
if (L1 == NULL || L2 == NULL) {
exit(ERROR);
}
LinkList p = L1;
LinkList q = L2;
while (p->next) {
p = p->next;
}
p->next = L1->next;
if(Is_ListLoop(L2)){
printf("相交\n");
printf("相交的第一個結點是：");
Find_Loop(L2);
}
else{
printf("不相交\n");
}
}
參考連結：
https://blog.csdn.net/a1091220321/article/details/47706711
https://www.cnblogs.com/hxsyl/p/4395794.html
https://blog.csdn.net/zwhlxl/article/details/45745825
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)