Leetcode 142. 环形链表 II (查找环的入口地址)

Leetcode 142. 环形链表 II (查找环的入口地址)

**题目描述：**给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

/**
 * 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) {
       ListNode* fast = head;
	    ListNode* slow = head;
        // 快指针到尾部时停止
	    while(fast && fast->next) {
        // 慢指针走一步，快指针走两步
		    fast = fast->next->next;
		    slow = slow->next;
        // 快慢指针相遇，说明含有环
            if(fast ==  slow) {
			    slow = head;
                while(fast != slow) {
                    fast = fast->next;
                    slow = slow->next;
                }
                return slow;
		    }
	    }
	    // 不包含环
	    return nullptr; 
    }
};