https://leetcode-cn.com/problems/linked-list-cycle/submissions/
判断链表是否有环 可以使用hashmap来存储是否之前有过
但是由于题目要求只能o1的空间复杂度
所以使用快慢指针来处理该问题
需要注意的几点corner case,fast及slow node可能为空
如果有环则slow会追上fast, 如果没有的话fast.next为空节点.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
slow = head
if not slow:
return False
fast = head.next
if not (fast and fast.next):
return False
while slow != fast and fast and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
else:
return False
https://leetcode-cn.com/problems/linked-list-cycle-ii/
获取环形链表的交叉位置，一样o1的空间复杂度
这里需要用一点证明
假设从最开始到交点的距离为x, fast和slow交点为y, 环剩下的距离为z
因为fast的速度是slow的一倍，所以fast的路径长度为slow的的一倍
（x + y）* 2 = x + n(y + z) + y
左右都去掉一个x + y, 则可得 x + y = n(y + z)
x = (y + z)n - y
x = (n-1)(y+z) + z
由于我们知道y+z为一圈，所以从相交点走z和从头开始走x相遇的地方就位环的相交点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
current = fast = slow = head
if not (fast and fast.next):
return
# 这里因为slow和fast一样 所以需要先slow和fast都走一步再循环往前走
fast = fast.next.next
slow = slow.next
while fast != slow and fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast != slow:
return
while current != fast:
current = current.next
fast = fast.next
return current
