My O(n) solution. Let each node points to head.


  • 0
    W
    class Solution {
    public:
    	bool hasCycle(ListNode *head) {
    		ListNode * p1 = head;
    		ListNode * p2;
    		while (p1 != NULL&&p1->next != NULL){
    			p2 = p1->next;
    			p1->next = head;
    			if (p2->next != NULL&&p2->next->next == head)
    				return true;
    			p1 = p2;
    		}
    		return false;
    	}
    };

  • 0
    M

    if i am not wrong, you are actually modifying the entire linked list?


  • 0
    W

    Yes, you are right.


  • 0
    M

    i know a better solution, where we do find if there is a cycle without modifying the list. would you like to know?


  • 0
    W

    Sure. There should be other solutions. My solution is just one way.


  • 0
    M

    i am sorry for the delay,but i hope it helps. you are not really allowed to modify the value in the linked list, though i must admit that your approach was smart.
    here is another method. this method is called Floyd’s Cycle-Finding Algorithm. this is also considered the fastest method. what you precisely do is take two pointers, one that is incremented once, and another that is incremented twice. lets name them slow_ptr and fast_ptr. Suppose we have a linked list like 1->2->3->4->2 where the last 2 actually means that 4 is looping back to the 2 at first index. now the slow_ptr will move as follows : 1->2->3->4 and the fast_ptr will move as : 1->3->2->4.
    at this point, they both point to the same node, and hence we can return true. if at any point we find a null, we can simply return false.
    here is my code to make things more clear.
    p.s. : this solution took 52 ms.

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

Log in to reply
 

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