Linked List Cycle II

class Solution {
public:
    ListNode* findCycleEntry(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) {
                break;
            }
        }

        if (!fast || !fast->next) {
            return nullptr;
        }

        fast = head;

        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};

The C++ solution provided tackles the problem of identifying the start node of a cycle in a linked list. The approach uses a two-pointer strategy known as Floyd's Tortoise and Hare algorithm:

• Start both pointers, slow and fast, from the head of the linked list. Move slow by one step and fast by two steps through the list.
• Continue the process until slow and fast meet, indicating a cycle presence. If fast or its next pointer becomes null, there is no cycle, and return nullptr.
• Post detection, reset fast to the head of the list and proceed to move both slow and fast one step at a time.
• The node where slow and fast meet again is the entrance to the loop.

The efficiency of this method stems from its ability to detect and locate the cycle's start without additional space requirements, maintaining an O(n) time complexity and O(1) space complexity. This way, implement the linked list cycle detection and positioning efficiently.

public class Solution {
    public ListNode findCycleStart(ListNode head) {
        // Pointers for cycle detection
        ListNode slow = head;
        ListNode fast = head;

        // Traverse to find if there is a cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            // Check for cycle
            if (slow == fast) {
                break;
            }
        }

        // Handle no cycle case
        if (fast == null || fast.next == null) {
            return null;
        }

        // Reset pointer to head for cycle entry point detection
        fast = head;

        // Move both pointers at the same rate to find entry point
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        // Node where the cycle starts
        return slow;
    }
}

The provided Java solution implements a function to detect the starting node of a cycle in a linked list. It utilizes the Floyd’s Cycle Detection algorithm, also known as the "hare and tortoise" approach. This algorithm leverages two pointers, slow and fast, which move at different speeds through the linked list.

• Initiate both slow and fast pointers at the head of the linked list.
• Iterate through the list. Move slow pointer by one node and fast pointer by two nodes simultaneously. If these pointers meet, a cycle is detected.
• If fast or fast.next becomes null, it implies that the list does not contain a cycle. Return null in such case.
• Upon cycle detection, position the fast pointer back to the head of the linked list while keeping the slow pointer at the meeting point.
• Move both slow and fast pointers one step at a time. The node where they meet again is the start of the cycle.

This solution efficiently detects the entry point of a cycle in a linked list while maintaining a linear time complexity. It doesn't require additional memory for tracking visited nodes, making it optimal for environments with limited memory resources.

struct ListNode *findCycle(struct ListNode *start) {
    struct ListNode *slow = start;
    struct ListNode *fast = start;

    if (start == NULL || start->next == NULL) {
        return NULL;
    }
  
    do {
        slow = slow->next;
        fast = fast->next->next;
    } while (fast != NULL && fast->next != NULL && slow != fast);
  
    if (fast == NULL || fast->next == NULL) {
        return NULL;
    }
  
    fast = start;
  
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
  
    return slow;
}

This article provides a clear insight into a C function designed to identify the starting point of a cycle within a linked list if one exists. The function named findCycle accepts a pointer to the start of a linked list and returns the node where the cycle begins, using Floyd's Tortoise and Hare algorithm approach.

• The function first initializes two pointers, slow and fast, both pointing to the start of the linked list.
• It checks whether the list is empty or has only one node; if either condition is true, it returns NULL as no cycle could exist.
• The function then enters a loop where the slow pointer advances by one node, and the fast pointer advances by two nodes. This continues until either:
  • The fast pointer encounters a NULL, indicating there is no cycle.
  • The slow and fast pointers meet, indicating a cycle.
• If no cycle is found and the fast pointer reaches the end of the list, the function returns NULL.
• If a cycle is detected, to find the start of this cycle, fast is reset to the start of the list and both fast and slow now move one node at a time.
• The point at which they meet again is the starting node of the cycle, and this node is then returned.

The implementation ensures that the approach is efficient and comprehensible, utilizing a two-pointer technique to effectively determine the presence and origin of a cycle within a linked list, thereby solving the problem in linear time with constant space complexity.

var findCycleStart = function (head) {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            break;
        }
    }
    if (!fast || !fast.next) {
        return null;
    }
    fast = head;
    while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
};

This article provides a solution to detect the start of a cycle in a linked list using JavaScript. The provided solution uses the two-pointer technique, specifically the Floyd's cycle-finding algorithm.

• Begin with two pointers, slow and fast, both initialized at the head of the linked list.
• Progress slow by one node and fast by two nodes in each step of a loop. Continue looping as long as fast and its next node are not null.
• If both pointers meet (slow === fast), a cycle exists. Break out of the loop to find the cycle's start.
• If no cycle is detected (either fast or fast.next is null), return null indicating no cycle.
• Reposition fast at the head of the list and move both slow and fast at the same pace (one step at a time).
• The node at which slow and fast meet again is the start of the cycle. Return this node as the result.

By following these steps, efficiently determine the entry point of a cycle in a linked list, if one exists, using JavaScript.

class Solution:
    def findCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow_pointer = head
        fast_pointer = head

        while fast_pointer and fast_pointer.next:
            slow_pointer = slow_pointer.next
            fast_pointer = fast_pointer.next.next

            if slow_pointer == fast_pointer:
                break

        if not fast_pointer or not fast_pointer.next:
            return None

        fast_pointer = head

        while slow_pointer != fast_pointer:
            slow_pointer = slow_pointer.next
            fast_pointer = fast_pointer.next

        return slow_pointer

This solution detects the presence of a cycle within a linked list and returns the node where the cycle begins using the Turtle and Hare (Floyd's Cycle Detection Algorithm).

The algorithm works in two primary phases:

1. Detect if a cycle exists:

   • Initialize two pointers, slow_pointer and fast_pointer, both starting at the head of the linked list.
   • Move slow_pointer one step at a time and fast_pointer two steps at a time.
   • If a cycle exists, slow_pointer and fast_pointer will eventually meet inside the cycle.

2. Find the entry point of the cycle:

   • If a cycle is detected (from the previous step), reset fast_pointer back to the head of the linked list.
   • Move both slow_pointer and fast_pointer one step at a time.
   • The node where they meet this time is the starting node of the cycle.

If no cycle is detected in the first phase, return None indicating there is no cycle in the list.

The Python code provided effectively handles the identification and retrieving of the cycle's initial node efficiently, addressing the problem as described.