hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Linked List Cycle


  • Approach:

    1. Declare a slow and a fast pointer.

    2. The slow pointer moves 1 step each time and the first pointer moves 2 steps each time.

    3. Keep traversing until the slow pointer meets the first pointer.

    4. If the fast pointer accesses a NULL node that means the list does not have any cycle. Hence return false.

    5. Return true at the end.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(1)


Code [C++]

/**

* 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 false;

ListNode *slow = head, *fast = head->next;

while(slow!=fast){

slow = slow->next;

fast = fast->next;

if(!fast) return false;

fast = fast->next;

if(!fast) return false;

}

return true;

}

};