[LeetCode] Linked List Cycle, Solution

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

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

 

[Thoughts]

设定两个指针，一个每次走一步，一个每次走两步，如果链表上有环的话，两个指针必定能相遇。否则，则无环

[Code]

 1     bool hasCycle(ListNode *head) {
 2         if(head == NULL) return false;
 3         ListNode* first = head;
 4         ListNode* second = head->next;
 5         
 6         while(first != NULL && second != NULL)
 7         {
 8             if(first == second) return true;
 9             first = first->next;
10             second = second->next;
11             if(second == NULL)
12                 return false;
13             second = second->next;
14         }
15         return false;
16     }