leetCode 141. Linked List Cycle 链表

141. 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

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

<code>/**</code>

<code> </code><code>* Definition for singly-linked list.</code>

<code> </code><code>* struct ListNode {</code>

<code> </code><code>*     int val;</code>

<code> </code><code>*     ListNode *next;</code>

<code> </code><code>*     ListNode(int x) : val(x), next(NULL) {}</code>

<code> </code><code>* };</code>

<code> </code><code>*/</code>

<code>class</code> <code>Solution {</code>

<code>public</code><code>:</code>

<code>    </code><code>bool</code> <code>hasCycle(ListNode *head) {</code>

<code>        </code><code>ListNode *slow,*fast;</code>

<code>        </code><code>if</code><code>(NULL == head || NULL == head-&gt;next)</code>

<code>            </code><code>return</code> <code>false</code><code>;</code>

<code>        </code><code>slow = head;</code>

<code>        </code><code>fast = head;</code>

<code>        </code><code>fast = fast-&gt;next-&gt;next;</code>

<code>        </code><code>slow = slow-&gt;next;</code>

<code>        </code><code>while</code><code>(1)</code>

<code>        </code><code>{</code>

<code>            </code><code>if</code><code>(fast == NULL || fast-&gt;next == NULL)</code>

<code>                </code><code>return</code> <code>false</code><code>;</code>

<code>            </code><code>if</code><code>(fast == slow || fast-&gt;next == slow)</code>

<code>                </code><code>return</code> <code>true</code><code>;</code>

<code>            </code><code>slow = slow-&gt;next;</code>

<code>            </code><code>fast = fast-&gt;next-&gt;next;</code>

<code>        </code><code>}</code>

<code>        </code><code>return</code> <code>false</code><code>;</code>

<code>        </code> 

<code>    </code><code>}</code>

<code>};</code>

总结：快慢指针

快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。

快慢指针可以用来求一个单链表是否存在环，还可以用来求一个单链表的中间位置。

本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1837479