C++: faster runner will meet the slower one if a cycle exists


  • 4
    T
    /**
     * 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==NULL || head->next==NULL)
                return false;
            
            ListNode* fast = head->next->next;
            ListNode* slow = head->next;
            while(fast && fast->next)
            {
                if(fast==slow)
                    return true;
                else
                {
                    fast = fast->next->next;
                    slow = slow->next;
                }
            }
            
            return false;
        }
    };

  • 0
    S

    Well, good idea. I do the same but mutch shorter.

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


  • 0
    T

    yes, you're right. we can make it much shorter.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.