LeetCode 142. Linked List Cycle II【快慢指针】（Floyd判圈法）
题目描述
一百个Chocolate
博客专家
原创文章 620获赞 2397访问量 39万+
关注
私信
展开阅读全文
作者：一百个Chocolate
给定一个链表，如果有环路，找出环路的开始点。
解题思路对于链表找环路的问题，有一个通用的解法——快慢指针（Floyd判圈法）。给定两个指针， 分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步，slow 前进一步。如果 fast 可以走到尽头，那么说明没有环路；如果fast可以无限走下去，那么说明一定有环路，且一定存 在一个时刻slow和fast相遇。当slow和fast第一次相遇时，我们将fast重新移动到链表开头，并 让slow和fast每次都前进一步。当slow和fast第二次相遇时，相遇的节点即为环路的开始点。
AC/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head,*fast = head;
do{
//看fast是否走到链表结尾，进而判断是否存在环路
if(!fast||!fast->next) return NULL;
fast=fast->next->next;
slow=slow->next;
}while(slow!=fast);
//如果存在，找节点位置
fast=head;
while(slow!=fast){
fast=fast->next;
slow=slow->next;
}
return fast;
}
};
学如逆水行舟，不进则退
一百个Chocolate
博客专家
原创文章 620获赞 2397访问量 39万+
关注
私信
展开阅读全文
作者：一百个Chocolate
