leetcode筆記：Linked List Cycle

leetcode筆記：Linked List Cycle

一. 題目描述

Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space?

二. 題目分析

題目的意思是給定一個鏈表的頭指針，快速判斷一個鏈表是不是有環，如果有環，返回環的起始位置。該題的經典做法是使用兩個指針，兩個指針均指向頭結點，其中一個是快指針，一次走兩步；另一個是慢指針，一次只走一步，當兩個指針相遇時，證明有環。這種方法的時間復雜度為O(n)，空間復雜度O(1)，這裡需要考慮一些特殊情況：

空鏈表無環

鏈表只有一個節點時可能構成自環

三. 示例代碼

#include 

struct ListNode
{
    int value;
    ListNode* next;
    ListNode(int x) :value(x), next(NULL){}
};

class Solution
{
public:
    bool hasCycle(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return false;
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) return true;
        }
        return false;
    }
};

鏈表只有一個節點且該節點構成自環：

鏈表3->4->5->6->7，4->5->6->7形成環：

四. 小結

關於有環鏈表中快慢指針一定會相遇的解決方法，可以簡單地證明：

如果有環的話，快慢指針都會進入有環的部分。

而一旦進入有環的部分，一快一慢，學過物理都知道，其實可以相當於一個靜止另一個每次移動一格。

到此，為什麼一定會相遇應該已經很明顯了吧~

該方法廣為人知，不知是否有更為精妙的解法？