问题描述
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
问题分析
两个题目结合来看，目的是判断一个链表是否有环并求环的入口。
核心思路是使用快慢指针，快指针每次走两步，慢指针每次走一步，通过两者的相遇进行判断和求解。
判断是否有环
快慢指针都从head出发，快指针每次走两步，慢指针每次走一步。如果快指针走到了None，说明链表是无环的，如果链表是有环的，快指针应该一直在环上绕圈。当慢指针也进入环中后，每次快指针更接近慢指针一步，因此两针会在环上相遇，即可结束判断。
求环的入口
链表如上图所示，无环长度为x，两针相遇点距环入口距离为y，设环长为s，相遇前快指针已在环上绕了n圈，因为快指针速度是慢指针的两倍，因此有等式：
2 * (x + y) = x + y + ns
即 x + y = ns, x = ns - y = (n-1) * s + (s - y) 此处n至少是为1的，因为快指针需要从后面追上慢指针。
因此让慢指针继续从初次相遇位置接着绕圈，快指针回到head，每次两指针都只走一步，则相遇位置就是环的入口。
AC代码
# 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
p_slow = head
p_fast = head.next
while p_fast and p_fast.next:
p_slow = p_slow.next
p_fast = p_fast.next.next
if p_fast == p_slow:
return True
return False
Runtime: 78 ms, which beats 83.41% of Python submissions.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
p_fast = head
p_slow = head
flag = False
while p_fast and p_fast.next:
p_slow = p_slow.next
p_fast = p_fast.next.next
if p_slow == p_fast:
flag = True
break
if not flag:
return None
p_fast = head
while True:
if p_fast == p_slow:
return p_fast
p_fast = p_fast.next
p_slow = p_slow.next
Runtime: 82 ms, which beats 75.09% of Python submissions.
