LeetCode 142.环形链表2 C写法

LeetCOde 142.环形链表2 C写法

思路1🤔：

​ 用环形链表的方法，快慢指针找到slow和fast的相遇点，此时头到入口点的位置与相遇点到入口点的距离一样。

​ 我们假设头到入口点的长度为L，环的长度为C，相遇点到入口点的长度为X。那么我们可以计算出在相遇时，fast走了L+n*C+X步(其中n为fast走的圈数)，slow走了L+X步，且fast步数是slow的两倍，进一步得出等式 2(L+X) = L+n*C+X，化简后得到L = n*C -X，然而n无论走多少圈，最后还是在相遇点，所以可以把n看做1，最后得L = C - X。C-X就是相遇点到入口点的长度，等式成立，推出该方法。

代码🔎：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(slow == fast) //带环则开始找入口点
        {
            struct ListNode* meet = slow;
            while(meet != head) //meet等于head时代表找到入口点
            {
                meet = meet->next;
                head = head->next;
            }
            return meet;
        }
    }
    return NULL;
}

思路2🤔：

​ 在相遇点用一个指针meet等于slow，meet再找到meet的next，然后将slow->next指向空，那么下一次循环的时候就会在空结点停下，将环形链表变为相交链表。

代码🔎：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(slow == fast)
        {
            struct ListNode* meet = slow;
            meet = meet->next; 
            slow->next = NULL; //断环
            struct ListNode* List1 = head;
            struct ListNode* List2 = meet;
            int LenHead = 1;
            int LenMeet = 1;
            int gap = 0;
            while(List1->next) //计算走到尾需要多少步
            {
                ++LenHead;
                List1 = List1->next;
            }
            while(List2->next)
            {
                ++LenMeet;
                List2 = List2->next;
            }
            if(List1 == List2) //这里可以不写，因为有相遇点必定是相交链表
            {
                struct ListNode* shortList = head; //先假设头结点到入口点的长度更短
                struct ListNode* longList = meet;
                gap = abs(LenHead-LenMeet); //更长的的先走gap步
                if(LenHead > LenMeet) //如果假设错了就交换
                {
                    shortList = meet;
                    longList = head;
                }
                while(gap--) //让长短链表距离相等
                {
                    longList = longList->next;
                }
                while(longList != shortList) //相等就说明找到入口点
                {
                    longList = longList->next;
                    shortList = shortList->next;
                }
                return longList;
            }
        }
    }
    return NULL;
}