連結清單中的一些問題——快慢指針

如果需要判斷一個連結清單是否循環，或者是否帶環，或是單向的連結清單求中位數、倒數第n個數，可以用到快慢指針以達到最簡單的方法。

判斷連結清單是否帶環

可以用兩個指針p1,p2均指向頭結點，p1每移動一次，p2周遊整個連結清單，查找是否有與p1位址相等的位置。

//連結清單定義
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
           

bool doesExistLoop(ListNode *pHead)
{
    ListNode *p1, *p2;
    p1 = p2 = pHead;
    while (p1->next)
    {
        while (p2->next)
        {
            p2 = p2->next;
            if (p2 == p1) return true;
        }
        p1 = p1->next;
    }
    return false;   
}
           

此種方法時間複雜度為O(n^2)，效率比較低。下面介紹一種經典的、效率高一些的方法——快慢指針。

快慢指針的思路很簡單，就好像兩個人在賽跑，一個跑得快一個跑得慢。如果跑的是環形跑道，時間足夠長的話，跑得慢的總會被套圈，即他倆的位置總有一個時間是沖個的；反之如果跑道是一條直線的話，倆人位置是永遠不會重合的。

應用到這個問題中，可以設定兩個指針p1,p2，p1每次向後走一步，p2每次向後走兩步，若兩個指針能夠重合，就說明連結清單是帶環的。

bool doesExistLoop(ListNode *pHead)
{
    ListNode *fast, *slow;
    fast = slow = pHead;
    while (fast)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}
           

這種方法時間複雜度是O(n)，效率會比第一種方法高不少。

如果連結清單帶環，如何找環的入口

思路如下：先利用上邊尋找環的方法，當快慢指針相遇的時候，一個指針從頭開始，另一個從相遇的地方開始，兩個同步走，下一次相遇的地方一定是入口（不知道什麼原理，但是親自試了幾個後發現真是……）

ListNode* findLoopPort(ListNode *pHead)
{
    ListNode *fast, *slow;
    fast = slow = pHead;
    while (fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (fast == slow) break;
    }
    if (fast == NULL&&fast->next == NULL) return NULL;
    while (slow != fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return fast;
}
           

在有序連結清單中尋找中位數

若不借助計數器變量實作查找中位數的功能，快慢指針也是最好的選擇。讓快指針的速度保持為慢指針的兩倍，這樣當快指針達到連結清單最後的時候，慢指針正好到達連結清單的中間。注意判斷連結清單有奇數個節點還是偶數個節點，若奇數個節點，則慢指針的值就是所求；若偶數個節點，則慢指針和慢指針下一個的值的平均數就是所求。

int findMiddle(ListNode *pHead)
{
    ListNode *fast, *slow;
    fast = slow = pHead;
    while (fast)
    {
        if (fast->next == NULL) return slow->val;
        else if (fast->next == NULL&&fast->next->next == NULL) return (slow->val + slow->next->val) / ;
        else
        {
            fast = fast->next->next;
            slow = slow->next;
        }
    }
}
           

傳回連結清單中倒數第n個數

保持快指針的速度比慢指針快n即可。

ListNode* lastButOne(ListNode *pHead)
{
    ListNode *fast, *slow;
    if (!pHead || !pHead->next || !pHead->next->next) return NULL;
    fast = pHead->next->next;
    slow = pHead;
    while (!fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;