Wednesday, November 20, 2013

[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 }

No comments: