My faster and slower runner solution


  • 46
    A
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
     /**
     use faster and lower runner solution. (2 pointers)
     the faster one move 2 steps, and slower one move only one step.
     if there's a circle, the faster one will finally "catch" the slower one. 
     (the distance between these 2 pointers will decrease one every time.)
     
     if there's no circle, the faster runner will reach the end of linked list. (NULL)
     */
    class Solution {
    public:
        bool hasCycle(ListNode *head) {
            if(head == NULL || head -> next == NULL)    
                return false;
     
            ListNode *fast = head;
            ListNode *slow = head;
            
            while(fast -> next && fast -> next -> next){
                fast = fast -> next -> next;
                slow = slow -> next;
                if(fast == slow)
                    return true;
            }
     
            return false;
        }
    };

  • 1
    V
    if(head == NULL || head -> next == NULL)  
    

    we can simplify this line to:

    if(head == NULL) 

  • 0
    V

    no if the length is odd or even .if simplify if(head==null),on case of length,will be wrong!


  • 0
    L

    Error in the situation when fast -> next == NULL ?


  • 0
    P

    Very interesting method. As the test set is not absolute, I use a special value "INT_MAX" to solve it. But the problem's inner mind should be as yours solution. Thanks for share.


  • 0
    W

    Excellent solution! The idea is if two people run in a cycle , the faster will catch up the slower after some time elapsed.


  • 0

    I think this actually works... anyone tried?


  • 0
    V

    Any knows the time complexity of this solution?


  • 0
    A

    actually can avoid checking this

    class Solution(object):
        def hasCycle(self, head):
            """
            :type head: ListNode
            :rtype: bool
            """
            fast, slow = head, head
            while fast and fast.next:
                fast = fast.next.next
                slow = slow.next
                if fast == slow:
                    return True
            return False

  • 0
    C

    the worst-case time complexity is O(N). when the whole List is a circle or it doesn't has any circle


  • 7
    A

    I came up with a similar solution but simplified a bit more:

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

    There's no need to check for

    if(head == NULL || head -> next == NULL)    
            return false;
    

    This information is contained in while(fast && fast->next)


  • 0
    H
    This post is deleted!

Log in to reply
 

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