快慢指針

我們定義兩個(gè)指針，一快一滿。慢指針每次只移動(dòng)一步，而快指針每次移動(dòng)兩步。初始時(shí)，慢指針在位置 head，而快指針在位置 head->next。這樣一來(lái)，如果在移動(dòng)的過(guò)程中，快指針?lè)催^(guò)來(lái)追上慢指針，就說(shuō)明該鏈表為環(huán)形鏈表。否則快指針將到達(dá)鏈表尾部，該鏈表不為環(huán)形鏈表。

為什么我們要規(guī)定初始時(shí)慢指針在位置 head，快指針在位置 head->next，而不是兩個(gè)指針都在位置 head？

觀察下面的代碼，我們使用的是 while 循環(huán)，循環(huán)條件先于循環(huán)體。由于循環(huán)條件一定是判斷快慢指針是否重合，如果我們將兩個(gè)指針初始都置于 head，那么 while 循環(huán)就不會(huì)執(zhí)行。因此，我們可以假想一個(gè)在 head 之前的虛擬節(jié)點(diǎn)，慢指針從虛擬節(jié)點(diǎn)移動(dòng)一步到達(dá) head，快指針從虛擬節(jié)點(diǎn)移動(dòng)兩步到達(dá) head->next，這樣我們就可以使用 while 循環(huán)了。
當(dāng)然，我們也可以使用 do-while 循環(huán)。此時(shí)，我們就可以把快慢指針的初始值都置為 head。

bool hasCycle(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return false;
    }
    struct ListNode* slow = head;
    struct ListNode* fast = head->next;
    while (slow != fast) {
        if (fast == NULL || fast->next == NULL) {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}