C++筆試題之運(yùn)用快慢指針判斷鏈表中是否有環(huán)，并計(jì)算環(huán)的長(zhǎng)度

判斷鏈表中是否有環(huán)最經(jīng)典的方法就是快慢指針，同時(shí)也是面試官大多想要得到的答案。
? ? ? ?快指針pf(f就是fast的縮寫)每次移動(dòng)2個(gè)節(jié)點(diǎn)，慢指針ps(s為slow的縮寫)每次移動(dòng)1個(gè)節(jié)點(diǎn)，如果快指針能夠追上慢指針，那就說(shuō)明其中有一個(gè)環(huán)，否則不存在環(huán)。

? ? ? ?這個(gè)方法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)，實(shí)際使用兩個(gè)指針。

原理

? ? ? ?鏈表存在環(huán)，則fast和slow兩指針必然會(huì)在slow對(duì)鏈表完成一次遍歷之前相遇，證明如下：
? ? ? ?slow首次在A點(diǎn)進(jìn)入環(huán)路時(shí)，fast一定在環(huán)中的B點(diǎn)某處。設(shè)此時(shí)slow距鏈表頭head長(zhǎng)為x，B點(diǎn)距A點(diǎn)長(zhǎng)度為y，環(huán)周長(zhǎng)為s。因?yàn)閒ast和slow的步差為1，每次追上1個(gè)單位長(zhǎng)度，所以slow前行距離為y的時(shí)候，恰好會(huì)被fast在M點(diǎn)追上。因?yàn)閥<s，所以slow尚未完成一次遍歷。

? ? ? ?fast和slow相遇了，可以肯定的是這兩個(gè)指針肯定是在環(huán)上相遇的。此時(shí)，還是繼續(xù)一快一慢，根據(jù)上面得到的規(guī)律，經(jīng)過(guò)環(huán)長(zhǎng)s，這兩個(gè)指針第二次相遇。這樣，我們可以得到環(huán)中一共有多少個(gè)節(jié)點(diǎn)，即為環(huán)的長(zhǎng)度。

實(shí)現(xiàn)

#includeusing?namespace?std;

struct?Node{
????int?data;
????Node*?next;
};

void?Display(Node?*head)//?打印鏈表
{
????if?(head?==?NULL)
????{
????????cout?<<?"the?list?is?empty"?<<?endl;
????????return;
????}
????else
????{
????????Node?*p?=?head;
????????while?(p)
????????{
????????????cout?<<?p->data?<<?"?";
????????????p?=?p->next;
????????????if(p->data==head->data)//加個(gè)判斷，如果環(huán)中元素打印完了就退出，否則會(huì)無(wú)限循環(huán)
????????????????break;
????????}
????}
????cout?<<?endl;
}

bool?IsExistLoop(Node*?head)
{
????Node?*slow?=?head,?*fast?=?head;

????while?(?fast?&&?fast->next?)
????{
????????slow?=?slow->next;
????????fast?=?fast->next->next;
????????if?(?slow?==?fast?)
????????????break;
????}

????return?!(fast?==?NULL?||?fast->next?==?NULL);
}

int?GetLoopLength(Node*?head)
{
????Node?*slow?=?head,?*fast?=?head;

????while?(?fast?&&?fast->next?)
????{
????????slow?=?slow->next;
????????fast?=?fast->next->next;
????????if?(?slow?==?fast?)//第一次相遇
????????????break;
????}
????slow?=?slow->next;
????fast?=?fast->next->next;
????int?length?=?1;???????//環(huán)長(zhǎng)度
????while?(?fast?!=?slow?)//再次相遇
????{
????????slow?=?slow->next;
????????fast?=?fast->next->next;
????????length?++;????????//累加
????}
????return?length;
}

Node*?Init(int?num)?//?創(chuàng)建環(huán)形鏈表
{
????if?(num?data?=?1;
????head?=?cur?=?node;
????for?(int?i?=?1;?i?<?num;?i++)
????{
????????Node*?node?=?(Node*)malloc(sizeof(Node));
????????node->data?=?i?+?1;
????????cur->next?=?node;
????????cur?=?node;
????}
????cur->next?=?head;//讓最后一個(gè)元素的指針域指向頭結(jié)點(diǎn)，形成環(huán)
????return?head;
}

int?main(?)
{
????Node*?list?=?NULL;
????list?=?Init(10);
????Display(list);

????if(IsExistLoop(list))
????{
????????cout<<"this?list?has?loop"<<endl;
????????int?length=GetLoopLength(list);
????????cout<<"loop?length:?"<<length<<endl;
????}
????else
????{
????????cout<<"this?list?do?not?has?loop"<<endl;
????}

????system("pause");
????return?0;
}

輸出結(jié)果

參考鏈接：https://blog.csdn.net/sdujava2011/article/details/39738313