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、要注意几个地方，1、空节点链表无环 2、快指针的两步也是一步一步走的，每走一步都得进行检查

代码：

 1 #include <stddef.h>
 2 
 3 struct ListNode
 4 {
 5     int val;
 6     ListNode *next;
 7     ListNode(int x) : val(x), next(NULL) {};
 8 };
 9 
10 class Solution
11 {
12 public:
13     bool hasCycle(ListNode *head)
14     {
15         if (!head)
16         {
17             return false;
18         }
19 
20         ListNode *one = head;
21         ListNode *two = head;
22 
23         while (true)
24         {
25             two = two->next;
26             if (!two)
27             {
28                 return false;
29             }
30             if (two == one)
31             {
32                 return true;
33             }
34             two = two->next;
35             if (!two)
36             {
37                 return false;
38             }
39             if (two == one)
40             {
41                 return true;
42             }
43             one = one->next;            
44         }
45     }
46 };
47 
48 int main()
49 {
50     return 0;
51 }

View Code

网上基本都是这种方法，主要问题是要考虑特殊情形和边界条件