思路:
- 参考yxc大佬
- 龟兔赛跑,兔被追上龟时,则兔变龟’,
- 龟’从起点重头来,原龟则在龟兔相遇点继续走
- 两龟相遇则为入口
参考一
# 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:
fast = head; slow = head
while fast:
fast = fast.next
slow = slow.next
if fast: # 快指针一次走两步,因为走得快,所以用fast判断是否到达空节点(链表是否存在环)
fast = fast.next
else:
break
if fast == slow: # 快慢指针第一次相遇时,让快指针回到头节点,然后两个指针每次都只走一步
fast = head
while fast != slow:
fast = fast.next
slow = slow.next
return slow
return None
参考二
class Solution(object):
def entryNodeOfLoop(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
#进入环内
fast = head # 快慢指针
slow = head
n = 0 #记录慢指针走的步数
while fast and slow:
if not slow.next or not fast.next.next:
return None
fast = fast.next.next
slow = slow.next
n += 1
if fast == slow:
break
if not fast or not slow:
return None
#找入口
slow2 = head
k = 0 # 起点离入口的位置
while slow2 != slow:
slow2 = slow2.next
slow = slow.next
k += 1
return slow