Fork me on GitHub

leetcode之141. 环形链表

发表于 | 分类于
字数统计 283 字 | 阅读时长 1 分钟

题目描述：

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1：

1
2
3
4
> 输入：head = [3,2,0,-4], pos = 1
> 输出：true
> 解释：链表中有一个环，其尾部连接到第二个节点。
>

image-20190403112440347

示例 2：

1
2
3
4
> 输入：head = [1,2], pos = 0
> 输出：true
> 解释：链表中有一个环，其尾部连接到第一个节点。
>

image-20190403112552875

示例 3：

1
2
3
4
> 输入：head = [1], pos = -1
> 输出：false
> 解释：链表中没有环。
>

image-20190403112521441

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

解题思路一：

时间复杂度：$O(n)$,空间复杂度：$O(1)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution
{
	public :
	// 解决方法快慢指针
	bool hasCycle(ListNode *head)
	{
		if(!head || !head -> next) return false;
		ListNode *pfast = head -> next;
		ListNode *plow = head;
		while(pfast != plow)
		{
			// 一直检查快指针是否到了尽头
			if(!pfast || !pfast -> next) return false;
			pfast = pfast -> next -> next;
			plow = plow -> next;
		}
		return true;
	}
};