题目描述

对于一个给定的链表，返回环的入口节点，如果没有环，返回null

拓展：

你能给出不利用额外空间的解法么？

题解

一、单链表是否有环

定义两个指针，快指针一次走两步，慢指针一次走一步，如果两指针相遇，则存在环

二、找到环的入口节点

法一：定义两个指针p1和p2，如果环中有n个节点，则p1先走n步，然后p1和p2每次都走一步，相遇的节点就是环的入口节点。n可以使用前面的慢指针走一圈得到

法二：需要证明一个结论，从链表头和快慢指针相遇点分别设一个指针，每次都走一步，两指针必定相遇，且相遇点为环的入口点。

证明：设慢指针走的距离为s，快指针走的距离为2s，环长为r，则2s=s+nr，故s=nr

设头结点到环入口的距离为a，环的入口到快慢指针相遇点的距离为x，则a+x=s=nr，故a+x=(n-1)r+r，故a=(n-1)r+(r-x)，其中(r-x)为快慢指针相遇点到环入口的距离。

因此，从头结点出发的指针走了距离a到达环的入口时，从快慢指针相遇点出发的指针正好前进距离(r-x)加若干圈循环，也到达环的入口。

代码

//detectCycle.cpp

#include<iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
 
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == NULL) {
            return NULL;
        }

        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* meet = NULL;
        while (fast->next != NULL && fast->next->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                meet = slow;
                break;
            }
        }
        if (meet == NULL) {
            return NULL;
        }
        int ringLen = 1;
        while (slow->next != meet) {
            slow = slow->next;
            ringLen++;
        }
        ListNode* ptr1 = head;
        ListNode* ptr2 = head;
        for (int i = 0; i < ringLen; i++) {
            ptr1 = ptr1->next;
        }
        while (ptr1 != ptr2) {
            ptr1 = ptr1->next;
            ptr2 = ptr2->next;
        }
        return ptr1;
    }
};

int main() {
    ListNode* head = new ListNode(0);
    head->next = new ListNode(1);
    ListNode* ptr1 = head->next;
    ptr1->next = new ListNode(2);
    ListNode* ptr2 = ptr1->next;
    ptr2->next = new ListNode(3);
    ListNode* ptr3 = ptr2->next;
    ptr3->next = ptr1;

    Solution s;
    ListNode* result = s.detectCycle(head);
    cout << result->val << endl;

    delete head;
    delete ptr1;
    delete ptr2;
    delete ptr3;
}