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 }
No comments:
Post a Comment