euisblue
141. Linked List Cycle

C++

1class Solution { 2 public: 3 bool hasCycle(ListNode *head) { 4 if (!head) return false; 5 if (!head->next) return false; 6 7 ListNode *tortoise = head->next; 8 ListNode *hare = head->next->next; 9 10 for(int i=0; i<10001; ++i) { 11 if (tortoise == hare) return true; 12 tortoise = tortoise->next; 13 if (!tortoise) return false; 14 hare = hare->next; 15 if(!hare || !hare->next) return false; 16 hare = hare->next; 17 } 18 19 return false; 20 } 21};

Javascript

1var hasCycle = function(head) { 2 if (!head || !head.next) return false; 3 4 let tortoise = head.next; 5 let hare = head.next.next; 6 7 for(let i=0; i<10001; ++i) { 8 if (tortoise === hare) return true; 9 tortoise = tortoise.next; 10 if(!tortoise) return false; 11 hare = hare.next; 12 if(!hare || !hare.next) return false; 13 hare = hare.next; 14 } 15 16 return false; 17};

Ruby

1def hasCycle(head) 2 return false if !head or !head.next 3 4 tortoise = head.next 5 hare = head.next.next 6 7 0.upto(10000) do |_| 8 return true if tortoise == hare 9 10 tortoise = tortoise.next 11 return false if !tortoise 12 13 hare = hare.next 14 return false if !hare or !hare.next 15 hare = hare.next 16 end 17 18 false 19end