1.?返回鏈表的中間節(jié)點
給定一個帶有頭結點 head 的非空單鏈表盲憎，返回鏈表的中間結點幼驶。如果有兩個中間結點汇鞭，則返回第二個中間結點凄敢。
分析：
快慢指針同時指向頭節(jié)點碌冶，快指針走兩步，慢指針走一步
如果長度為偶數(shù)涝缝，那么快指針為NULL的時候停止扑庞，長度為奇數(shù)，fast->next為NULL的時候停止
慢指針指向的位置就是中間節(jié)點了
按照這種思路拒逮，實現(xiàn)代碼如下：
LinkNode?*findMidNode(LinkNode?*head)
{
LinkNode?*fast?=?head;
LinkNode?*slow?=?head;
while(NULL!=?fast?&&NULL!=?fast->next?)
{
fast?=?fast->next->next;
slow?=?slow->next;
}
returnslow;
}
2.鏈表的中間節(jié)點
輸入一個單向鏈表罐氨，輸出該鏈表中倒數(shù)第k個結點。為符合計數(shù)習慣滩援，本題從1開始計數(shù)栅隐，即鏈表的尾節(jié)點是倒數(shù)第1個節(jié)點。
例子
如：一個鏈表有6個節(jié)點玩徊，從頭節(jié)點開始租悄，它們的值依次是1、2恩袱、3泣棋、4、5憎蛤、6外傅。這個鏈表的倒數(shù)第3個節(jié)點是值為4的節(jié)點。
分析：
定義兩個指針俩檬，指針移動一個快萎胰，一個慢(鏈表的長度l)
1.快慢指針同時指向頭結點
2.首先快指針移動k-1步，先走到第k個節(jié)點
3.快慢指針同時移動棚辽，直到快指針指向末尾技竟，這時，快慢指針都走了l-k屈藐，
4.慢指針指向的節(jié)點即為我們需要尋找的節(jié)點
參考代碼實現(xiàn)如下：
LinkNode?*FindKthToTail(LinkNode?*head,unsignedintk)
{
????if(NULL?==?head?||?0?==?k)
????????return?head;
????LinkNode?*pFast?=?head;
????LinkNode?*pSlow?=?head;
????unsigned?int?i?=?0;
????//快指針先移動
????while(i?<?k?-1)
????{
????????if(NULL?!=?pFast)
????????{
????????????pFast?=?pFast->next;
????????}
????????//k大于鏈表的長度
????????else
????????{
????????????return?NULL;
????????}
????????i++;
????}
????//快慢指針一起移動
????while(NULL?!=?pFast->next)
????{
????????pSlow?=?pSlow->next;
????????pFast?=?pFast->next;
????}
????return?pSlow;
}
3.判斷鏈表是否有環(huán)
如何判斷一個單鏈表是否有環(huán)榔组？若有環(huán)，如何找出環(huán)的入口節(jié)點联逻。
按照快慢指針的思路搓扯，使用兩個指針，一個指針每次走一步包归，另一個每次走兩步锨推，如果鏈表有環(huán)，那么它們終將相遇，而如果沒有環(huán)换可，快的指針最后會指向NULL椎椰。
按照這種思路，我們的參考代碼如下：
//0:無環(huán)沾鳄，1：有環(huán)
int hasLoop(LinkNode *head)
{
? ? if(NULL == head)
? ? ? ? return 0;
? ? ? ? LinkNode *slow = head;
? ? ? ? LinkNode *fast = head->next;
? ? ? ? //當快指針到末尾時慨飘，無環(huán)，結束
? ? ? ? while (NULL != fast? && NULL != slow)
? ? ? ?{
? ? ? ? ? ? //快慢相遇译荞，有環(huán)
? ? ? ? ? ? if (fast == slow)
? ? ? ? ? ? ? ? return 1;
? ? ? ? ? ? ? ? slow = slow->next; // 慢指針每次走一步
? ? ? ? ? ? ? ? fast = fast->next;
? ? ? ? ? ? ? ? if (fast != NULL)
? ? ? ? ? ? ? ? ? ? fast = fast->next;
? ? }
? ? return 0;
}
