Given the head node of a singly linked list, return the node where the cycle begins. If there is no cycle, return None. The linked list may contain a cycle, where a node's next pointer points to a previous node in the list. Do not modify the linked list.
Example 1
Input: head = ListNode(7, ListNode(9, ListNode(5, ListNode(2)))) # create cycle: node 3 points to node 1 node0 = head node1 = head.next node2 = node1.next node3 = node2.next node3.next = node1 # call detect_cycle_node(head)
Output: node1
Explanation: Cycle starts at node with value 9 (index 1).
Example 2
Input: head = ListNode(4, ListNode(8)) # create cycle: node 1 points to node 0 node0 = head node1 = head.next node1.next = node0 # call detect_cycle_node(head)
Output: node0
Explanation: Cycle starts at node with value 4 (index 0).
Example 3
Input: head = ListNode(10) # no cycle detect_cycle_node(head)
Output: None
Explanation: No cycle in the list.
Constraints
Case 1
Input: head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))) # create cycle: node 4 points to node 2 node0 = head node1 = node0.next node2 = node1.next node3 = node2.next node4 = node3.next node4.next = node2 # call detect_cycle_node(head)
Expected: node2
Case 2
Input: head = ListNode(6, ListNode(7, ListNode(8))) # no cycle detect_cycle_node(head)
Expected: None
Case 3
Input: head = ListNode(11, ListNode(12, ListNode(13))) # create cycle: node 2 points to node 0 node0 = head node1 = node0.next node2 = node1.next node2.next = node0 # call detect_cycle_node(head)
Expected: node0