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?

Solution: Floyd’s Tortoise and Hare

To find whether there is a circle, we can use two pointers, hare and tortoise, one advances twice as fast as the other. There exists a cycle when tortoise and hare reaches the same point, or hare reaches the end of the linked list.

Two pointers, one at head and the other at the meeting point of hare and tortoise, will meet at the start of the cycle if they travel at the same speed.

See Leetcode solution for detailed explanation.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
# = None

class Solution(object):
    def detectCycle(self, head):
        :type head: ListNode
        :rtype: ListNode
        if head is None or is None:
            return None

        hare, tortoise = head, head
        while True:
                hare =
            except AttributeError:
                return None
            tortoise =
            if hare == tortoise:

        node1, node2 = head, hare
        while node1 != node2:
            node1 =
            node2 =

        return node1