142. &141 Linked List Cycle II

题目要求：

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up :
Can you solve it without using extra space?

解题思路：

• 快慢指针 : fast指针一个循环走两步，slow指针一个循环走一步。
• 示意图

代码：

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
        """
        fast = head
        slow = head
        meet = None

        while fast:
            fast = fast.next
            slow = slow.next
            if fast:
                fast = fast.next
            if fast == slow:
                meet = fast
                break
        if meet == None:
            return None

        while head and meet:
            if head == meet:
                return True
            head = head.next
            meet = meet.next
        return None

if __name__ == "__main__":
    head, head.next, head.next.next = ListNode(1), ListNode(2), ListNode(3)
    head.next.next.next, head.next.next.next.next = ListNode(3), ListNode(4)
    head.next.next.next.next.next, head.next.next.next.next.next.next = ListNode(4), ListNode(5)
    

    print(Solution().detectCycle(head))