Given a singly linked list, determine weather it contains a cycle. Return true if a cycle exists; otherwise, return false. The solution must use O(1) auxiliary space.

This problem is classically solved using Floyd’s Cycle Detection Algorrithm — also known as the "tortoise and hare" approach. Two pointers traverse the list at different speeds: one advances by one node per step (slow), the other by two nodes (fast). If a cycle exists, the fast pointer will eventually catch up to the slow pointer inside the loop.

class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (!head || !head->next) return false;

        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }

        return false;
    }
};

Next, implement a function to remove the n-th node from the end of the list in a single pass with O(n) time and O(1) space complexity. A sentinel (dummy) node simplifies edge-case handling, especially when deleting the head.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0);
        dummy.next = head;

        ListNode* ahead = &dummy;
        ListNode* behind = &dummy;

        // Advance 'ahead' by n+1 steps to create proper gap
        for (int i = 0; i <= n; ++i) {
            ahead = ahead->next;
        }

        // Move both until 'ahead' reaches null
        while (ahead) {
            ahead = ahead->next;
            behind = behind->next;
        }

        // Remove the target node
        ListNode* toDelete = behind->next;
        behind->next = toDelete->next;
        delete toDelete;

        return dummy.next;
    }
};

Finally, locate the starting node of the cycle, if one exists. Once the two pointers meet in side the loop, reset one pointer to the head while keeping the other at the meeting point. Then advance both one step at a time — their next meeting occurs precisely at the cycle’s entrance.

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        if (!head || !head->next) return nullptr;

        ListNode* slow = head;
        ListNode* fast = head;

        // Phase 1: Detect if cycle exists
        do {
            if (!fast || !fast->next) return nullptr;
            slow = slow->next;
            fast = fast->next->next;
        } while (slow != fast);

        // Phase 2: Find cycle entrance
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};