题目描述

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

说明：不允许修改给定的链表。

进阶：
你是否可以不用额外空间解决此题？

分析

用双指针遍历求相交的节点。
慢指针和快指针的初始位置是：head
慢指针一次前进一步，快指针一次前进两步。
两个指针相交的节点为C。
设非循环链表部分为X,循环链表中C节点之前的部分为Y ,C之后的部分为Z,可以根据快指针和慢指针经过的节点数列出方程：
2*（X + Y） = X + Y + Z + Y
解方程得到：X = Z
让慢指针从C节点出发，快指针从head出发，一次前进一步，相等的节点为入环的第一个节点
方程左边的慢指针遍历的节点数，右边为快指针遍历的节点数，
链表：
1 -> 2 -> 3 -> 4,循环节点为3,
慢指针遍历的节点是：2,3
快指针遍历的节点是：2,3,4,3
起始位置的节点不算
相交的节点是:3
X = 2
Z = 4
Y = 3

代码

/**
 * 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) {
        if(head == NULL) {
            return NULL;
        }
        auto slow = head;
        auto quick = head;
        bool circle = false;
        while(quick != NULL && quick->next != NULL) {
            slow = slow->next;
            quick = quick->next->next;
            if(quick == slow){
                circle = true;
                break;
            }
        }
        if(!circle) {
            return NULL;
        }
        quick = head;
        while(slow != quick) {
            slow = slow->next;
            quick = quick->next;
        }
        return slow;
    }
};

题目链接

https://leetcode-cn.com/explore/interview/card/tencent/222/linked-list/917/