142. Linked List Cycle II

Problem Statement

link: https://leetcode.com/problems/linked-list-cycle-ii/ https://leetcode.cn/problems/linked-list-cycle-ii/

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Example:

Input: head = [3,2,0,-4], pos = 1 Output: 1

Input: head = [1,2], pos = 0 Output: 0

Solution Approach

Detect the cycle’s starting node in the linked list by employing Floyd’s cycle-finding algorithm, then determining the meeting point.

Algorithm

1. Detect Cycle: Use two pointers, one moving fast and the other slow. If a cycle exists, they will meet at some point.
2. Find Start: Initialize a new pointer at the head and move it forward along with the slow pointer until they meet, which will be the cycle’s starting point.
3. Return Result: If the fast pointer reaches the end without meeting the slow pointer, there’s no cycle. Otherwise, return the node where the two pointers meet as the start of the cycle.

Implement

    #----------- #   a  | c  | b #      ----- # (a + b) * 2 = a + (b + c) * n + b # a = (n - 1)*b + n*c = (n - 1)(b + c) + c
class Solution:
      def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
          slow = fast = head
          while fast and fast.next:
              slow, fast = slow.next, fast.next.next
              if slow == fast:
                  slow2 = head
                  while slow != slow2:
                      slow, slow2 = slow.next, slow2.next
                  return slow
          return None

    
    

Twitter  facebook  Email