"""
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?
"""

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

class Solution:
    # @param head, a ListNode
    # @return a list node
    def detectCycle(self, head):
        if head is None or head.next is None:
            return None
        slow = head.next
        fast = head.next.next
        while slow!=fast:
            if fast is None or fast.next is None:
                return None
            slow = slow.next
            fast = fast.next.next
        fast = head
        while slow!=fast:
            slow = slow.next
            fast = fast.next
        return slow

    # Remember to set slow = head.next and fast = head.next.next before entering the loop

@@ -98,15 +98,717 @@
 l.%0A%0A
+To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed)%C2%A0in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.%0A%0ANote: Do not modify the linked list.%0A%0AExample 1:%0AInput: head = %5B3,2,0,-4%5D, pos = 1%0AOutput: tail connects to node index 1%0AExplanation: There is a cycle in the linked list, where tail connects to the second node.%0A%0A%0AExample 2:%0AInput: head = %5B1,2%5D, pos = 0%0AOutput: tail connects to node index 0%0AExplanation: There is a cycle in the linked list, where tail connects to the first node.%0A%0A%0AExample 3:%0AInput: head = %5B1%5D, pos = -1%0AOutput: no cycle%0AExplanation: There is no cycle in the linked list.%0A%0A
 Follow
- 
+-
 up:%0A
@@ -1108,150 +1108,125 @@
     
-if head is None or head.next is None:%0A            return None%0A        slow = head.next%0A        fast = head.next.next%0A        while slow!=fast:
+fast = slow = head%0A        while (%0A            fast and%0A            fast.next%0A        ):%0A            slow = slow.next
 %0A   
@@ -1238,44 +1238,57 @@
     
-if 
 fast 
-is None or fast.next is None
+= fast.next.next%0A            if fast == slow
 :%0A  
@@ -1305,82 +1305,52 @@
     
+b
 re
-turn None%0A            slow = slow.next%0A            fast = fast.next.next
+ak%0A        else:%0A            return None%0A
 %0A   
@@ -1384,18 +1384,20 @@
 ile 
-slow!=fast
+fast != slow
 :%0A  
@@ -1402,35 +1402,35 @@
             
-slow = slow
+fast = fast
 .next%0A      
@@ -1431,35 +1431,35 @@
             
-fast = fast
+slow = slow
 .next%0A      
@@ -1563,8 +1563,315 @@
 he loop%0A
+    # Assume non-ring_length = a, ring_length = b, pointer fast went through f, pinter slow went through s.%0A    # So we know: f = 2s. f-s = nb%0A    # so s = nb. Which means short has went through n cycle's of the ring so far. So if we put f back to start, at the point they meet again, it's the entry point.%0A

Update 142