Problem statement

Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

Solution

This is a classical problem in a linked list. It is chosen for interview by many high-tech companies.

The generally idea is also a very good philosophy in linked list -->  Fast and slow pointers.

• Define two pointers, fast and slow.
• Each time fast goes two step and slow goes one step.
• If there is a loop, they must met sometime.
• Otherwise, fast will become NULL first.

Time complexity is O(n), space complexity is O(1)

The following solution follows the idea to find the middle of a link list. Fast pointer should goes faster than slow at start.

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

This solution do not need to do the test at beginning of the program, however, fast is initialized the same value of slow.

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