[Python] Floyd's Tortoise & Hare Algorithm - Time O(N) | Space O(1)
Explaination:\nThis problem is asking us to find the middle of a linked list, to do this we will utilize Floyd\'s Tortoise & Hare Algorithm aka Fast and Slow Po
# Explaination:\nThis problem is asking us to find the middle of a linked list, to do this we will utilize Floyd\'s Tortoise & Hare Algorithm aka Fast and Slow Pointers.\n\n1. We start off with two variables `slow` and `fast` and initialize both to start at the head of the linked list.\n2. The `slow` pointer will always move ahead by 1 node at a time. The `fast` pointer will always move ahead by 2 nodes at a time. So since the `fast` pointer is moving twice as fast as the `slow` pointer, by the time the `slow` pointer reaches the middle of the linked list, the `fast` should have reached the end of the linked list.\n3. So we setup the `while` loop and the conditions are `while fast and fast.next` the reason this is the condition is because we are moving 2 nodes ahead at a time for the `fast` pointer. So if `fast` is `null`/`None`, there is no `.next` for a node that doesn\'t exist. Same for `fast.next`, we need to check if that node exists, since we will be trying to do `fast.next.next` so if `fast.next` is `null`/`None` then we wont have a `.next` since there is no node.\n5. Now we move `slow` pointer by 1 node by doing `slow.next` and move `fast` pointer by 2 nodes by doing `fast.next.next`.\n6. Once that `fast` pointer has reached the end of the linked list, the `while` loop should break since it will no longer meet the conditions to continue the loop. \n7. Finally we return the `slow` pointer since it will have reached the middle of the linked list.\n\n**Time O(N) | Space O(1)**\nTime is O(N) because we will be doing 1 iteration through the linked list, realistically we wont be doing a full iteration since the `fast` pointer moves 2 nodes at a time, so its more accurately `N / 2` but we rounded it to just `N`\nSpace is O(1) because we aren\'t using any space that scales with the input size, we are just using some variables and updating them.\n\n```\nclass Solution:\n    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:\n        slow = head\n        fast = head\n        \n        while fast and fast.next:\n            slow = slow.next # Move by one node ahead\n            fast = fast.next.next # Move by two nodes ahead\n        \n        return slow\n```
['Linked List', 'Two Pointers', 'Python', 'Python3']