LeetCode:Linked List Cycle

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

Follow up:
Can you solve it without using extra space?

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10     public:
11         bool hasCycle(ListNode *head) {
12             if(head==NULL)
13                 return false;
14             ListNode *p=head,*q;
15             int n=0,m;
16             while(p!=NULL)
17             {
18                 q=head;
19                 m=0;
20                 while(m<=n)
21                 {
22                     if(q==p->next)
23                         return true;
24                     else
25                     {
26                         q=q->next;
27                         m++;
28                     }
29                 }
30                 p=p->next;
31                 n++;
32             }
33             return false;
34         }
35 };

后记：在做Linked List Cycle II 的时候，发现上述解法效率太低，所以换了种思路：

（1）定义slow和fast指针，都指向head结点，然后slow指针每次向后走1个结点，fast指针每次向后走2个结点。

（2）如果fast指针为空，则说明不存在环；如果fast指针和slow指针相等，则说明存在环。

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10     public:
11         bool hasCycle(ListNode *head) {
12             if(head==NULL||head->next==NULL)
13                 return false;
14             ListNode *slow=head,*fast=head;
15             while(fast!=NULL)
16             {
17                 slow=slow->next;
18                 fast=fast->next;
19                 if(fast!=NULL)
20                     fast=fast->next;
21                 if(slow==fast)
22                     return true;
23             }
24             return false;
25         }
26 };