060.md

142. Linked List Cycle II

Difficulty: 🟡 Medium

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.

Examples:

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.

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• 105 <= Node.val <= 105
• pos is 1 or a valid index in the linked-list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Solutions

O(n) solution

Python 3

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

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None

The given solution uses the Floyd's Cycle Detection algorithm to detect a cycle in the linked list and find the node where the cycle begins.

Here is a step-by-step overview of the solution:

1. Initialize two pointers, slow and fast, to the head of the linked list.
2. Iterate through the linked list using the following conditions:
   • Move the slow pointer one step forward (slow = slow.next).
   • Move the fast pointer two steps forward (fast = fast.next.next).
   • Check if the slow and fast pointers are equal. If they are, it means there is a cycle in the linked list, and we break out of the loop.
3. If the iteration completes without finding a cycle (i.e., the fast pointer reaches the end of the linked list or becomes None), we return None.
4. Reset the slow pointer to the head of the linked list and iterate through the linked list again using the following conditions:
   • Move both the slow and fast pointers one step forward (slow = slow.next, fast = fast.next).
   • Check if the slow and fast pointers are equal. If they are, it means they meet at the node where the cycle begins, and we return that node.
5. If the iteration completes without finding the cycle's start node, we return None.

Complexity Analysis

The time complexity for the solution is O(n), where n is the number of nodes in the linked list. In the worst case, the fast pointer needs to traverse the entire linked list to detect a cycle. The additional iteration to find the cycle's start node also takes O(n) time.

The space complexity is O(1) since we are using only two pointers.

Summary

The given solution uses the Floyd's Cycle Detection algorithm to determine if a linked list has a cycle and find the node where the cycle begins. By using two pointers that move at different speeds, we can detect a cycle by checking if the pointers meet. The time complexity of the solution is O(n), and the space complexity is O(1).

NB: If you want to get community points please suggest solutions in other languages as merge requests.