文章目录
- 引入 - 快慢指针
- 思考 - 快慢指针行走步数
- 进阶 - 寻找环形链表的头
引入 - 快慢指针
141-环形链表 - Leetcode
关于这道题，大家可以利用快慢指针，一个每次走两步，一个每次走一步，只要他们有一次相撞了就代表说这是一个链表
为了更好的理解我们可以代入下图
我们假设slow进环的时侯，fast已经走了C（环形区域的总长度）-N步了，那么它就距离slow刚刚好N步于是乎没进行一次移动，即fast往前走2步，slow往前走一步，那么它们之间的距离就是N-1步以此类推直到0步
所以这一题的解答代码就是
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; bool hasCycle(struct ListNode *head) { if(head == NULL) return false; ListNode *fast = head, *slow = head; while(fast && fast->next) { fast = fast->next->next; slow = slow->next; if(slow == fast) return true; } return false; }思考 - 快慢指针行走步数
根据上面快指针一次走两步，慢指针一次走一步，我们可以得到结果并知晓原理
但如果快指针一次走的是三步呢，结果还会一样吗。
为此，我们不妨罗列一下三步的情况
假设一次走三步，我们在不分 C（环形区域的总长度） 的情况下，它们之间的距离就会是N -> N-2 -> N-4 -> …
因为不分奇偶就无法得出最后结果，所以我们可以得到下面这个分类讨论
即：
我们发现一旦 C（环形区域的总长度） 为奇数的话，就会导致最后快指针比慢指针多走了一步，这就会导致，追不上吗，
但真的会这样吗
大家肯定会反应过来， C（环形区域的总长度） 的总长度是不会变的，变得只是快慢指针之间的距离，如果在进行一次循环我们可以将 N 的初始值看成 C-1 了，而N每次移动都需要 -2，并且 C 为奇数，因此这一次，就可以看成偶数的这种情况了，这样就能抓到了
同样的我们如果将这种情况以数学公式表示
这是快指针步数为3的情况，为4，为5的讨论情况也差不多这样，无非就是再讨论一下，这里就不赘述了
进阶 - 寻找环形链表的头
142 - 环形链表Ⅱ - Leetcode
乍一看，这道题与上面一道题基本一样，但是细看我们会发现这里返回开始入环的第一个节点，所以还是需要思考
如果有环的话，创建两个指针，一个指针从head节点开始，另一个指针从相遇点meet开始，两个指针每次都走一步，两个指针相遇的点就是链表入环的第一个节点。
因此在上面引入那道题的基础上我们需要增进一步
即为L距离就等于meet在环中转x-1圈，再走C-N，所以说meet和head的相遇点一定是链表入环的第一个节点。
即
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode *detectCycle(struct ListNode *head) { if(head == NULL) return NULL; ListNode *fast = head, *slow = head; while(fast && fast->next) { fast = fast->next->next; slow = slow->next; if(slow == fast) { ListNode* phead = head; ListNode* meet = slow; while(phead != meet) { phead = phead->next; meet = meet->next; } return meet; } } return NULL; }