LEET code --linked list cycle

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

我這方法不好 因為順序被我打亂了

好方法是   分兩個pointer
一個走比較慢  一個走比較快
如果快的會走到NULL  那就沒回圈
如果快地碰到曼的就代表有迴圈

為了增加處理速度 可以增加走的速度

1 2 3 4 5 6 7 8 9 10 11 12

bool hasCycle(struct ListNode *head) { if(head==NULL)return false; struct ListNode* current=head; struct ListNode* previous=NULL; while(current!=NULL && current->next!=head){ struct ListNode* next = current->next; current->next=previous; previous= current; current=next; } return (current==NULL) ? false:true; }

---------------------------------------------
改版之後
用快慢pointer來指

1 2 3 4 5 6 7 8 9 10 11 12 13

bool hasCycle(struct ListNode *head) { if(head==NULL)return false; struct ListNode * fast=head; struct ListNode * slow=head; while(fast && fast->next && fast->next->next){ fast=fast->next->next; slow=slow->next; if(fast == slow)return true; } if(fast->next == NULL || fast->next->next==NULL)return false; }