Linked List Cycle
Given a linked list, determine if it has a cycle in it.
http://www.lintcode.com/en/problem/linked-list-cycle/
Discussion
设置两个指针,一个快一个慢,快 的指针每次走两步, 慢的指针每次走一步, 如果快指针和慢指针相遇, 则说明有环.
反正以我的聪明才智是想不到的,能想到用hash就不错了
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: True if it has a cycle, or false
*/
bool hasCycle(ListNode *head) {
ListNode *slow = head;
ListNode *fast = head;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if(slow == fast) {
return true;
}
}
return false;
}
};