주어진 linkedlist에서 cycle 찾는 문제

gistfile1.txt

Q. Given a linked list, determine if it has a cycle in it. Can you solve it without using extra space?


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 * 
 * test case: 1->2->1, 1->2->NULL, 1->NULL, 1->2->3->4->2 ... 
 * solution : slow, fast runner를 이용하여 fast, slow runner가 한번이라도 만나면 return false.
 * Time Complexity : O(2n) 
 */
 
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fastRunner = head;
        ListNode* slowRunner = head;
        
        while(fastRunner != NULL && fastRunner->next != NULL) {
            fastRunner = fastRunner->next;
            
            if(fastRunner == slowRunner) return true;
            fastRunner = fastRunner->next;
            
            slowRunner = slowRunner->next;
            if(fastRunner == slowRunner) return true;
        }//end while
        
        return false;
    }
};