Detecting a Cycle in a Singly Linked List – Fast & Slow Pointer Solution for Tencent Interview

Problem Statement

Given the head pointer of a singly linked list, determine whether the list contains a cycle. The solution should use O(N) time and O(1) extra space.

1. Brute‑Force Attempt (invalid)

A naive approach walks a fixed large number of steps (e.g., one million) and assumes a cycle if the end is not reached. This fails for long acyclic lists and is not acceptable for interviews.

func hasCycle(head *ListNode) bool {
    count := 0
    max := 1000000
    for ; head != nil && count < max; {
        count++
        head = head.Next
    }
    if count == max {
        return true
    }
    return false
}

2. Hash‑Map Marking Method

Store the address of each visited node in a hash map; if a node is encountered again, a cycle exists. This works but requires O(N) additional space, which does not meet the interview constraint.

3. Floyd’s Tortoise‑Hare (Fast & Slow Pointer)

Maintain two pointers: a slow pointer that moves one step per iteration and a fast pointer that moves two steps. If the list contains a cycle, the pointers will eventually meet; otherwise the fast pointer reaches the end (nil).

C++ Implementation

#include <iostream>
using namespace std;

typedef struct node {
    int data;
    struct node *next;
} Node;

Node *createList(int n) {
    Node *p = new Node[n];
    for (int i = 1; i < n; ++i) {
        p[i - 1].next = &p[i];
        p[i - 1].data = i;
    }
    p[n - 1].next = NULL;
    p[n - 1].data = n;
    return p;
}

Node *createListWithRing(int n) {
    Node *p = new Node[n];
    for (int i = 1; i < n; ++i) {
        p[i - 1].next = &p[i];
        p[i - 1].data = i;
    }
    p[n - 1].next = &p[n/2]; // create a cycle
    p[n - 1].data = n;
    return p;
}

// Fast pointer = rabbit, slow pointer = turtle
bool listHasRing(Node *p) {
    Node *pSlow = &p[0];
    Node *pFast = &p[1];
    while (pSlow != NULL && pFast->next != NULL) {
        if (pSlow == pFast) {
            return true; // cycle detected
        }
        pSlow = pSlow->next;
        pFast = pFast->next->next;
    }
    return false; // no cycle
}

int main() {
    Node *head = createList(10);
    cout << listHasRing(head) << endl; // expected 0 (false)
    delete [] head;

    head = createListWithRing(10);
    cout << listHasRing(head) << endl; // expected 1 (true)
    delete [] head;
    return 0;
}

The program prints 0 for an acyclic list and 1 for a list with a cycle, confirming that Floyd’s algorithm satisfies O(N) time and O(1) extra space.