leetcode141. Linked List Cycle

easy程度题

题目：

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

可以建立一个set集合，每次访问一个新节点，如果集合中没有则将节点放入set,

如果有则说明存在环。不占用额外空间，想不出来

参考了网上解法:

设置两个指针slow fast ,slow每次走一步，fast每次走两步，如果相遇了则存在环

数学证明:

假设存在环，不能相遇，fast越过slow时间距为s ，则s + 1 < 2, s < 1 所以s = 0.

与不能相遇矛盾！

AC解:

class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        if (head == nullptr)
            return false;
            
        ListNode *slower = head,*faster = head;
        while (faster && faster->next)
        {
            faster = faster->next->next;
            slower = slower->next;
            if (faster == slower)
                return true;
        }
        
        return false;
    }
};

不占用额外空间，依然不会，阅读了LeetCode上排名最高的题解

解法:

假设慢指针走了K步时相遇，环的长度为r，则 2K - K = nr, K = nr

设链表起点到环的起点距离为S，相遇点距离环的起点M， 则K = S + M

S = K - M = nr - M = (n - 1)r + r - M,n = 1时 S = r - M 很直观，画图很直观

所以，只需用两个指针分别从头结点处，和相遇点处开始走，每次走一步，那么相遇点

就是环的起始节点

AC解:

class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        if (head == nullptr)
            return head;
        ListNode *first = head,*second = head;
        bool cycled = false;
        while (second && second->next)
        {
            first = first->next;
            second = second->next->next;
            if (first == second)
            {
                cycled = true;
                break;
            }
        }
        
        if (!cycled)
            return nullptr;
        
        first = head;
        while (first != second)
        {
            first = first->next;
            second = second->next;
        }
        return first;
    }
};