問題描述
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?
問題分析
兩個(gè)題目結(jié)合來看，目的是判斷一個(gè)鏈表是否有環(huán)并求環(huán)的入口遮精。
核心思路是使用快慢指針怪嫌，快指針每次走兩步粪躬，慢指針每次走一步晓殊，通過兩者的相遇進(jìn)行判斷和求解磷瘤。
判斷是否有環(huán)
快慢指針都從head出發(fā)，快指針每次走兩步，慢指針每次走一步挎塌。如果快指針走到了None，說明鏈表是無環(huán)的内边，如果鏈表是有環(huán)的榴都，快指針應(yīng)該一直在環(huán)上繞圈。當(dāng)慢指針也進(jìn)入環(huán)中后漠其，每次快指針更接近慢指針一步嘴高，因此兩針會(huì)在環(huán)上相遇，即可結(jié)束判斷和屎。
求環(huán)的入口
鏈表如上圖所示阳惹，無環(huán)長度為x，兩針相遇點(diǎn)距環(huán)入口距離為y眶俩，設(shè)環(huán)長為s，相遇前快指針已在環(huán)上繞了n圈快鱼，因?yàn)榭熘羔標(biāo)俣仁锹羔樀膬杀兜哂。虼擞械仁剑?br>
2 * (x + y) = x + y + ns
即 x + y = ns, x = ns - y = (n-1) * s + (s - y) 此處n至少是為1的，因?yàn)榭熘羔樞枰獜暮竺孀飞下羔槨?br>
因此讓慢指針繼續(xù)從初次相遇位置接著繞圈抹竹，快指針回到head线罕，每次兩指針都只走一步，則相遇位置就是環(huán)的入口窃判。
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.
