Linked List Cycle

class Solution {
public:
    bool checkCycle(ListNode* start) {
        if (!start) {
            return false;
        }
        ListNode* slowPtr = start;
        ListNode* fastPtr = start->next;
        while (slowPtr != fastPtr) {
            if (!fastPtr || !fastPtr->next) {
                return false;
            }
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
        }
        return true;
    }
};

Detect if a linked list has a cycle using the two-pointer technique in C++. The provided solution implements a function named checkCycle that determines if a cycle exists within a linked list. Here's a brief on what happens in the function:

• Initialize two pointers, slowPtr and fastPtr, where slowPtr advances one node at a time, and fastPtr advances two nodes.
• The loop continues until the two pointers meet, indicating a cycle, or until the fastPtr reaches the end of the list, indicating no cycle.

Remember, the function handles edge cases as well:

• If the starting node is null, it immediately returns false - no cycle.
• If fastPtr or its next node is null anytime during the iteration, it returns false, confirming no cycle is present.

Upon confirming the presence or absence of a cycle, the function returns the appropriate boolean value. This implementation is efficient and commonly utilizes the Floyd’s Cycle Detection Algorithm, sometimes known as the "Tortoise and the Hare" algorithm.

public class Solution {
    public boolean checkCycle(ListNode start) {
        if (start == null) {
            return false;
        }

        ListNode turtle = start;
        ListNode rabbit = start.next;
        while (turtle != rabbit) {
            if (rabbit == null || rabbit.next == null) {
                return false;
            }
            turtle = turtle.next;
            rabbit = rabbit.next.next;
        }
        return true;
    }
}

The provided Java solution addresses the problem of detecting a cycle in a linked list. The method checkCycle takes a ListNode as its start point and returns a boolean indicating whether a cycle is present.

• In the method, first, check if the start node is null. If it is, return false since an empty list cannot have a cycle.
• Initialize two pointers, turtle and rabbit. The turtle moves one step at a time (slow pointer), while the rabbit (fast pointer) moves two steps at a time.
• Use a while loop to continue moving the pointers until they either meet (indicating a cycle) or the rabbit encounters a null (indicating the end of the list).
  • If rabbit or rabbit.next is null, it means rabbit has reached the end of the list without looping back, thus return false.
  • If turtle and rabbit pointers meet at some point in the loop, return true indicating a cycle exists.

This approach uses the Floyd's Cycle-Finding Algorithm (also known as the "tortoise and the hare" algorithm) which is efficient for cycle detection in linked lists.

bool containsLoop(struct ListNode* start) {
    if (start == NULL) {
        return false;
    }
    struct ListNode* tortoise = start;
    struct ListNode* hare = start->next;
    while (tortoise != hare) {
        if (hare == NULL || hare->next == NULL) {
            return false;
        }
        tortoise = tortoise->next;
        hare = hare->next->next;
    }
    return true;
}

Detecting a cycle in a linked list is a classic problem in data structures. In this summary, you'll learn how to use the "Floyd's Cycle Detection Algorithm" or "Tortoise and Hare" approach to solve this in C.

Here's a compact guide to the provided C function:

• The containsLoop function takes a pointer to the start of a linked list.
• It first checks if the starting node is NULL. If it is, the function immediately returns false because a non-existent list does not contain a cycle.
• The function initializes two pointers, tortoise and hare. Tortoise moves one step at a time, while hare moves two steps at a time.
• A while loop runs as long as tortoise and hare do not meet.
  • If hare or hare->next is NULL at any point, it returns false indicating there is no cycle, as hare has reached the end of the list.
  • In every cycle of the loop, tortoise is moved to the next node and hare is moved two nodes forward.
• If tortoise and hare meet, meaning tortoise equals hare, the function returns true, indicating a cycle exists in the list.

This approach efficiently detects loops with a time complexity of O(n) and a space complexity of O(1), where n is the number of nodes in the list. Implementing this algorithm helps prevent errors like infinite loops that could occur when traversing cyclic linked lists.

var cycleCheck = function(headNode) {
    if (headNode === null) {
        return false;
    }
    let walker = headNode;
    let runner = headNode.next;
    while (walker !== runner) {
        if (runner === null || runner.next === null) {
            return false;
        }
        walker = walker.next;
        runner = runner.next.next;
    }
    return true;
};

Detect if a linked list has a cycle using the provided JavaScript function named cycleCheck. This function takes the head of the linked list as its only parameter (headNode). If the input list is empty (i.e., headNode is null), the function immediately returns false to indicate there's no cycle.

The function implements the "Floyd’s Tortoise and the Hare" algorithm where two pointers, walker (tortoise) and runner (hare), are used. Initially, walker starts at the head node, and runner starts at the second node. The function iterates while walker does not equal runner:

• If runner or runner.next is null, it means the end of the list is reached without encountering a cycle, and the function returns false.
• In each iteration, walker moves one step, and runner moves two steps.

If at any point walker meets runner, it indicates that a cycle is present, and the function returns true, confirming the cycle’s presence. This efficient approach works with O(n) time complexity where n is the number of nodes in the list.

class Solution:
    def detectCycle(self, node_head: ListNode) -> bool:
        if node_head is None:
            return False
        ptr1 = node_head
        ptr2 = node_head.next
        while ptr1 != ptr2:
            if ptr2 is None or ptr2.next is None:
                return False
            ptr1 = ptr1.next
            ptr2 = ptr2.next.next
        return True

The program written in Python3 aims to determine if a linked list contains a cycle. The solution involves the fast and slow pointer technique, also known as the Floyd's Tortoise and Hare algorithm. Here's the breakdown of the process:

• Initialize two pointers, ptr1 and ptr2. ptr1 moves one step at a time (slow pointer), and ptr2 moves two steps at a time (fast pointer).
• Start the traversal from the head of the linked list. ptr1 starts from the node_head and ptr2 starts from node_head.next.
• Continue moving both pointers at their respective speeds until they either meet or ptr2 reaches the end of the list.
• If ptr2 reaches the end (ptr2 or ptr2.next becomes None), the list doesn't contain a cycle, and the function returns False.
• If ptr1 and ptr2 meet, a cycle exists in the linked list, and the function returns True.

By utilizing this algorithm, the detection of the cycle in the list is performed efficiently by checking the intersection of two pointers, which results in a time complexity of O(n) and a space complexity of O(1).