题目描述

给定一个链表，判断是否存在环。

进一步：能否只使用额外 O(1)O(1) 的空间？

思路

经典的快慢指针，类似于操场跑圈，如果两人一块一慢，最终肯定会相遇，如果不是环形的，最终都会到达终点。

/**
 * 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||!head->next) return 0;//如果空链表或者只有一个元素的链表，必然不成环
        ListNode *first = head,*second = first->next;//first是块指针，一次移动1，second是慢指针，一次移动2
        while(first&&second){//快慢都到达终点停止
            if(first==second) return true;//相遇，成环
            first = first->next;//快指针移动
            second = second->next;
            if(second) second = second->next;//慢指针移动
        }
        return false;
    }
};

另一种写法

在判断是否成环时候除了找到成立情况退出外，也可以反过来写，找到不成了情况退出，找不到就是成立

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head||!head->next) return 0;
        ListNode *l = head,*r = l->next;
        while(l!=r){
            if(r==NULL||r->next ==NULL) return false;
            l=l->next,r=r->next->next;
        }
        return true;
    }
};