快慢指针找链表环入口_快慢指针判断环入口

链表：

struct ListNode {
     int val;
     struct ListNode *next;
 };
1
2
3
4

快慢指针就是指指针每次移动的速度不一样，一般快指针每次移动两步，慢指针移动一步。

既然快慢指针移动的速度不同，那么如果有环，就一定会相遇，无环，就不可能相遇（相当于两个人围着跑道跑步，同起点，如果跑道有环的话，只要速度不同，那么他们肯定会相遇~，如果跑道是直线的，那么他们的距离只会越来越远，不可能再相遇。）终止条件就是链表为空。

bool IsCycle(struct ListNode* head){
	struct ListNode* fast, slow;
	fast = head;
	slow = head;
	while (fast && fast->next) {
		slow = slow->next;
		fast = fast->next->next;
	if (fast == slow) {
		return true;
		}
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

判断环入口，分两步：
1.判断有无环
2.重置快指针，慢指针不变，使快慢指针每次都只移动一步，快慢指针再次相遇就是环入口
如果不能理解可以在链表中画个环，用表格记录fast和slow

找入口：

好了，fast和slow相遇，入口就是1

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    bool isCycle = false;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow){
            isCycle = true;
            break;
        }
    }
    printf("%d %d\n", fast->val,slow->val);
    if(isCycle){
        fast = head;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
            printf("%d %d\n", fast->val,slow->val);
        }
        return fast;
    } 
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

快慢指针用法很多，还要继续学习！