题目描述
给定一个链表，判断链表中是否有环。你能用 O(1)（即，常量）内存解决此问题吗？
题解
用快慢指针的方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| bool hasCycle(ListNode *head) {
if (!head||!head->next)return false;
ListNode *t1 = head, *t2 = head->next;
while (t1 && t2&&t1!=t2)
{
t1 = t1->next;
t2 = t2->next;
if (t2)
t2 = t2->next;
else
return false;
}
if (!t2)
return false;
return true;
}
|