141. 环形链表

给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。否则，返回 false 。 进阶：你能用 O(1)（即，常量）内存解决此问题吗？ 示例 1： 输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。 示例 2： 输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。 示例 3： 输入：head = [1], pos = -1 输出：false 解释：链表中没有环。 提示：

链表中节点的数目范围是 [0, 10]
-10 <= Node.val <= 10
pos 为 -1 或者链表中的一个 有效索引 。

解题思路

判断单链表中是否包含环，经典解法就是双指针，一个跑得快，一个跑得慢。如果不含有环，跑得快的那个指针最终会遇到null，说明链表不含环；如果含有环，快指针最终会超慢指针1圈，和慢指针相遇，说明链表有环。
这里的快指针每次移动的距离都是慢指针的两倍。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) return true;
        }
        return false;
    }
};

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。 说明：不允许修改给定的链表。 进阶：你是否可以使用 O(1) 空间解决此题？ 示例 1： 输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。 示例 2： 输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。 示例 3： 输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。 提示：

链表中节点的数目范围在范围 [0, 10] 内
-10 <= Node.val <= 10
pos 的值为 -1 或者链表中的一个有效索引

解题思路

和上题不同的是，这题需要解决的问题是：如果链表中有环，则需要输出的是开始入环的第一个节点。
同样使用快慢指针，如果有环，两个指针一定会相遇，但是相遇点不一定是入环的起点。
假设第一次相遇时，满指针slow走了k步，那么因为快指针每次移动的距离都是慢指针的两倍，所以快指针一定走了2k步，也就是说比slow多走了k步。
设相遇点与环的起点的距离为m，那么环的起点与头节点head的距离为k-m，也就是说从head前进k-m步就能到达环起点。
而与此同时，如果从相遇点继续前进k-m步，也恰好到达环起点。

所以，相遇时，只要把快、慢指针中的任意一个重新指向head，然后两个指针同速前进，k-m步后就会相遇，相遇之处就是环的起点。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        bool hasCycle = false;
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) {//相遇点
                hasCycle = true;
                break;
            } 
        }
        if(!hasCycle) return NULL;
        //先把其中一个指针重新指向head
        slow = head;
        while(slow != fast) {
            fast = fast->next;//两个指针以相同的速度前进
            slow = slow->next;
        }//两个指针相遇的那个单链表结点就是环的起点
        return slow;
    }
};