<jupyter_start><jupyter_text>MediumGiven a linked list, return the node where the cycle begins. If there is no cycle, return null.To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.**Note: Do not modify the linked list.** Example 1:    Input: head = [3,2,0,-4], pos = 1    Output: tail connects to node index 1    Explanation: There is a cycle in the linked list, where tail connects to the second node.        Example 2:    Input: head = [1,2], pos = 0    Output: tail connects to node index 0    Explanation: There is a cycle in the linked list, where tail connects to the first node.    Example 3:    Input: head = [1], pos = -1    Output: no cycle    Explanation: There is no cycle in the linked list.  Thought 1Using hash table to save the memory location and index that we have traveled. Then return the index while we visited the same memory location again.Space Complexity: O(N)Time Complexity: O(N)<jupyter_code>class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        
        H = {}
        cnt = 0
        while head:
            try:
                H[head]
            except:
                H[head] = cnt
            else:
                return head
            cnt += 1
            head = head.next             

        return None<jupyter_output><empty_output><jupyter_text>Thought 2Without using extra space, O(1).Explaination is in the following links:https://leetcode.com/problems/linked-list-cycle-ii/discuss/258948/%2B-pythonhttps://www.youtube.com/watch?v=iZVBVCpmugI&t=1s<jupyter_code># 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:

        try:
            slow = head.next
            fast = head.next.next
            while fast != slow:
                fast = fast.next.next
                slow = slow.next
        except:
            return None
        
        
        slow = head
        
        while slow != fast:
            slow = slow.next
            fast = fast.next
        
        
        return slow<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07891332470892626, 'fraction_numerical': 0.0129366106080207, 'mean_word_length': 2.0933333333333333, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 11, 'https://': 2, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '109542', 'license': 'BSD-2-Clause', 'n_tokens_mistral': 671, 'n_tokens_neox': 638, 'n_words': 254, 'path': '142. Linked List Cycle II.ipynb', 'repo_name': 'kkoo1122/Leetcode_Practice', 'size': '2319'}