快慢指針中的快慢指的是移動的步長,即每次向前移動速度的快慢。例如可以讓快指針每次沿鍊表向前移動2,慢指針每次向前移動1次。
快慢指針的套用
判斷單鍊表是否為循環鍊表
fast=slow=head;
fast=fast->next->next;
slow=slow->next;
while(true){
if (fast==NULL || fast->next==NULL)
return false;
else if (fast==slow || fast->next==slow)
return true;
else{
fast=fast->next->next;
slow=slow->next;
}
}
在有序鍊表中尋找中位數
該方法在不藉助計數器變數實現尋找中位數的功能。原理是:快指針的移動速度是慢指針移動速度的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;
}
}
{
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;
}
}