leetcode：142. 环形链表 II

一、题目

 

函数原型：

struct ListNode *detectCycle(struct ListNode *head)

二、思路

要找到入环结点，就要计算头结点到入环结点之间的距离。

设链表环外的长度为a；慢指针与快指针相遇时，它们逆时针到入环结点的距离为b，顺时针到入环结点的距离为c，那么链表中环的长度就是b+c。

当慢指针与快指针相遇时，设快指针已经在环内走了n圈。由于快指针走过的距离始终是慢指针的两倍，因此a+b+n(b+c)=2(a+b)，即a=c+(n-1)(b+c)。

有上述式子可得，头结点到入环结点间的距离就等于快、慢指针相遇位置顺时针到入环结点的距离再加上（n-1）环的长度。

因此，如果设置一个遍历指针从头结点开始遍历，它与慢指针相遇时的位置就是入环结点位置。

三、代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *slow=head;
    struct ListNode *fast=head;
 
    int answer=0;//判定有无环的标志
 
    while(fast&&fast->next)
    {
        fast=fast->next->next;//快指针一次走两步
        slow=slow->next;//慢指针一次走一步
        if(slow==fast)//快慢指针相遇
        {
            answer=1;
            break;
        }
    }
 
    if(answer==0)//找到了空结点，说明链表无环
        return NULL;
    else//链表有环
    {
        struct ListNode *cur=head;//遍历指针，从头结点开始遍历
        while(slow!=cur)//找遍历指针和慢指针相遇的位置
        {
            cur=cur->next;
            slow=slow->next;
        }
        return cur;//找到并返回入环结点
    }
}