[数据结构与算法]环形链表ll Python3

?

题解：?

# 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 = slow = head
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                break
        if fast == None or fast.next == None:
            return None
        
        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next
        return slow

解题思路：和141环形链表类似的，这题也采用双指针来解。

显然从141环形链表来看，我们知道fast指针走两步，slow指针走一步，那么，如果slow指针走了k步和fast指针相遇，那么fast指针肯定走了2k步。借用labuladong老师的图：???????

?从环的起始点，到fast和slow相遇点，假设距离为m，那么从head开始，到入环的起始节点距离为k-m；从相遇点到入环的起始节点距离也是k-m。

?所以，可以采取的方式是，当fast指针和slow指针相遇后，将slow指针再指向head， 然后slow指针和fast指针以同样的速度走，当slow和fast指针相遇时，就说明到了环的起始位置。

?

?