Member Avatar for dilip.mathews

Hi all,

What is the effficient way to check whether a single linked list is looped somewhere.The number of nodes in the list is not known.
In that case traversal of SLL will go into an infinite loop.

One solution I have is to store each address of node in array and compare the nest address with the address in the array. But this solution will be of order O(n*n). Can somebody give me an efficient solution.

  • 2 Contributors
  • 2 Replies
  • 102 Views
  • 18 Hours Discussion Span
  • Latest Post Latest Post by dilip.mathews

Dani AI

Generated

As pointed out, this is a classic cycle-detection problem. The standard, efficient solution is Floyd's cycle-finding (tortoise and hare): advance one pointer by one step and another by two steps; if they ever meet, a loop exists. To locate the loop start, reset one pointer to the head and advance both one step at a time until they meet again. This runs in O(n) time with O(1) extra space (Floyd's cycle-finding algorithm).

Example C implementation that returns the start node of the loop (or NULL if none):

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

struct Node *find_cycle_start(struct Node *head) {
    struct Node *slow = head, *fast = head;
    while (fast && 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; /* start of loop */
        }
    }
    return NULL; /* no loop */
}

If only detection is needed, return true at the first slow == fast. To measure loop length, count steps from the meeting point until you return to it. Alternatives: use a hash set of visited node addresses (O(n) time, O(n) space) or Brent's algorithm (sometimes slightly faster in practice) — see the general cycle detection notes for trade-offs.

Practical cautions: do not destructively alter next unless you own the list; handle head == NULL, single-node self-loop, and two-node loops in tests; watch concurrency and memory-safety issues. If debugging an unknown list, guard traversals with a counter or use the detection routine to avoid infinite loops.

Member Avatar for dilip.mathews

Thnks BOBD

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.