题解 | #判断链表中是否有环#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
	  	//简单情况简单考虑
        if(head == nullptr || head->next == nullptr) return false;
        ListNode* slow = head->next;
        ListNode* fast = head->next->next;
        while(slow && fast && fast->next)
        {
            if(slow == fast) return true;//如果相等说明两个指针走到了一起
            slow = slow->next;
            fast = fast->next->next;
        }//只要快慢指针有一个能到链表尾，说明绝对无环
        return false;
    }
};

这是一种常见的单链表问题：如何判断一个单链表是否有环。给定一个单链表，如果链表中某个节点的.next指针指向了链表中在它之前的节点，则表明该链表中存在环，这是一个经典的数据结构问题。

核心思想就是利用快慢指针去遍历链表。快指针每次移动2个节点，慢指针每次移动1个节点，如果两个指针相遇，则说明链表中有环。如果快指针走到了链表末尾，即fast->next指向nullptr，则说明链表中没有环。

为什么这种方法可行呢？

假设一个链表中有环，现在将快的指针和慢的指针放在相差最远的两个节点上，这时快指针与慢指针中间隔了一个环，因为每次快指针走两步，慢指针走一步，所以慢指针进入环后，被快指针追上的时间为 (n-1)*L+A（n表示圆环长度，L表示链表头到圆环的起点距离，A表示慢指针已经在圆环中位置。此处可以参考数学公式解析） ，当快指针和慢指针在环上某一点相遇时，快指针总共走过的路程可以表示为 S = x1 + x2 + x3 + x4 = 2 * (x1 + x2)。其中，x1 + x2 表示从链表头部，到达环的起点的位置；x3 表示从链表头部经过环的位置；x4 表示从环的起点绕过一周之后回到环的某一位置。由于快指针速度是慢指针速度的2倍，所以 x1 + x2 = x3 + x4。我们现在可以知道，当相遇时，x3 的长度即为圆环长度的整数倍。

因此，在进行链表遍历的过程中，如果没有环存在，快指针一定最先到达链表尾部。如果存在环，则由于快指针每次跨度是慢指针的两倍，所以当快慢指针跑在环上时，快指针一定会在某一个时刻追上慢指针，因此就可以判断出链表中是否存在环。

这种方法时间复杂度为O(N)，空间复杂度为O(1)。代码实现简单，但是思路需要理解清楚。欢迎大家进行实践，并加深对链表的理解。