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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == NULL)
return false;
if(head->next == NULL)
return false;
ListNode *p,*q;
p = head;
q = head;
while(p != NULL && p->next != NULL)
{
p = p->next->next;
q = q->next;
if(p == q)
return true;

}
return false;
}
};