给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
1
2
3
|
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
|
示例 2：
1
2
3
|
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
|
示例 3：
1
2
3
|
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
|
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
思路
1
2
|
当一个链表有环时，快慢指针都会陷入环中进行无限次移动，然后变成了追及问题。想象一下在操场跑步的场景，只要一直跑下去，快的总会追上慢的。当两个指针都进入环后，每轮移动使得慢指针到快指针的距离增加一，同时快指针到慢指针的距离也减少一，只要一直移动下去，快指针总会追上慢指针。
根据上述表述得出，如果一个链表存在环，那么快慢指针必然会相遇。
|
代码
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
# -*- coding: utf-8 -*-
# @Time : 2020/7/22 22:19
# @Author : affectalways
# @Site :
# @Contact : affectalways@gmail.com
# @File : 141.py
# @Software : PyCharm
# -*- coding: utf-8 -*-
# @Time : 2020/7/16 22:27
# @Author : affectalways
# @Site :
# @Contact : affectalways@gmail.com
# @File : 0201.py
# @Software : PyCharm
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if not head:
return False
fast = head.next
slow = head
while fast != slow:
if fast is None or fast.next is None:
return False
slow = slow.next
fast = fast.next.next
return True
def create_link(tmp):
head = None
cur = None
for i in tmp:
node = ListNode(i)
if head is None:
head = node
cur = head
else:
cur.next = node
cur = cur.next
return head
def traversal_link(head):
cur = head
while cur:
print(cur.val)
cur = cur.next
if __name__ == '__main__':
head = create_link([1, 2, 3, 3, 2, 1])
# traversal_link(head)
solution = Solution()
result = solution.hasCycle(head)
traversal_link(result)
|
