【LeetCode-Algorithms】141.Linked

问题描述

Given a linked list, determine if it has a cycle in it.
题目大意：给定一个链表，判断该链表是否有环

解题思路

设置两个步长不同的指针，当两个指针相遇时，有两种情况：
1、链表有环，步长大的追上了步长小的
2、链表没有环，两个指针在链表的末尾相遇。

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