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?

题目大意：

判断一个单链表是否存在环。

思路：

采用快慢指针来处理。

代码如下：


/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode(intx):val(x),next(NULL){}*};*/classSolution{public:boolhasCycle(ListNode*head){ListNode*slow,*fast;if(NULL==head||NULL==head->next)returnfalse;slow=head;fast=head;fast=fast->next->next;slow=slow->next;while(1){if(fast==NULL||fast->next==NULL)returnfalse;if(fast==slow||fast->next==slow)returntrue;slow=slow->next;fast=fast->next->next;}returnfalse;}};


总结：快慢指针

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

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


2016-08-13 00:34:46