← Back to DSA Course | Chapter 4: Linked Lists | Lesson 5 of 8

Floyd का Cycle Detection Algorithm

Floyd का cycle detection एक track पर दो runners जैसा है, एक तेज़ और एक धीमा। अगर track loops करता है, तेज़ वाला आखिरकार धीमे वाले को पकड़ लेगा।

In this page:

  1. Cycle in a List
  2. Floyd's Method
  3. Meeting Point
  4. Complexity
  5. Practical Use
Syntax
markup 
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return True    # cycle found
return False

Cycle in a List

एक linked list में एक cycle मौजूद है जब किसी node से next pointers follow करना आखिरकार आपको एक ऐसे node पर वापस ले जाता है जिसे आप पहले visit कर चुके हैं, बजाय कभी एक null end तक पहुंचने के, जो अन्यथा infinite traversal का कारण बनता।

उदाहरण: Cycle in a List

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* a = new Node{1, nullptr};
    Node* b = new Node{2, nullptr};
    Node* c = new Node{3, nullptr};
    a->next = b; b->next = c; c->next = b;
    cout << "list has a cycle: node c points back to b, not to null" << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2), c = new Node(3);
        a.next = b; b.next = c; c.next = b;
        System.out.println("list has a cycle: node c points back to b, not to null");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

a, b, c = Node(1), Node(2), Node(3)
a.next = b
b.next = c
c.next = b
print("list has a cycle: node c points back to b, not to None")
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    struct Node *c = malloc(sizeof(struct Node));
    a->data = 1; b->data = 2; c->data = 3;
    a->next = b; b->next = c; c->next = b;
    printf("list has a cycle: node c points back to b, not to NULL\n");
    return 0;
}

Floyd's Method

Floyd का algorithm, tortoise and hare technique भी कहा जाता है, list में अलग speeds पर move होते दो pointers उपयोग करता है: एक slow pointer जो एक समय में एक node advance करता है, और एक fast pointer जो एक समय में दो nodes advance करता है।

उदाहरण: Floyd's Method

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
bool hasCycle(Node* head) {
    Node* slow = head; Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}
int main() {
    Node* a = new Node{1, nullptr}; Node* b = new Node{2, nullptr};
    a->next = b; b->next = a;
    cout << "has cycle: " << hasCycle(a) << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    static boolean hasCycle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next; fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2);
        a.next = b; b.next = a;
        System.out.println("has cycle: " + hasCycle(a));
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

a, b = Node(1), Node(2)
a.next = b
b.next = a
print("has cycle:", has_cycle(a))
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int hasCycle(struct Node *head) {
    struct Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}
int main() {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    a->next = b; b->next = a;
    printf("has cycle: %d\n", hasCycle(a));
    return 0;
}

Meeting Point

अगर कोई cycle नहीं है, fast pointer बस पहले आखिर (null) तक पहुंचता है। लेकिन अगर एक cycle है, fast pointer आखिरकार loop के अंदर slow pointer को lap कर लेता है और दोनों pointers बिल्कुल उसी node पर land करते हैं।

उदाहरण: Meeting Point

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* a = new Node{1, nullptr}; Node* b = new Node{2, nullptr}; Node* c = new Node{3, nullptr};
    a->next = b; b->next = c; c->next = b;
    Node* slow = a; Node* fast = a;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) { cout << "met at node with data " << slow->data << endl; break; }
    }
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2), c = new Node(3);
        a.next = b; b.next = c; c.next = b;
        Node slow = a, fast = a;
        while (fast != null && fast.next != null) {
            slow = slow.next; fast = fast.next.next;
            if (slow == fast) { System.out.println("met at node with data " + slow.data); break; }
        }
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

a, b, c = Node(1), Node(2), Node(3)
a.next = b
b.next = c
c.next = b
slow = fast = a
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow is fast:
        print("met at node with data", slow.data)
        break
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    struct Node *c = malloc(sizeof(struct Node));
    a->data = 1; b->data = 2; c->data = 3;
    a->next = b; b->next = c; c->next = b;
    struct Node *slow = a, *fast = a;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) { printf("met at node with data %d\n", slow->data); break; }
    }
    return 0;
}

Complexity

चूंकि fast pointer को list को सिर्फ एक bounded संख्या में ही traverse करना पड़ता है, Floyd का algorithm O(n) time में एक cycle detect करता है सिर्फ दो pointer variables उपयोग करते हुए, इसलिए इसे O(1) extra space चाहिए।

उदाहरण: Complexity

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
bool hasCycle(Node* head) {
    Node* slow = head; Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}
int main() {
    Node* a = new Node{1, nullptr}; Node* b = new Node{2, nullptr};
    a->next = b; b->next = a;
    cout << "O(n) time, O(1) space -- only two pointers used: " << hasCycle(a) << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    static boolean hasCycle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next; fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2);
        a.next = b; b.next = a;
        System.out.println("O(n) time, O(1) space -- only two pointers used: " + hasCycle(a));
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

a, b = Node(1), Node(2)
a.next = b
b.next = a
print("O(n) time, O(1) space -- only two pointers used:", has_cycle(a))
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int hasCycle(struct Node *head) {
    struct Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}
int main() {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    a->next = b; b->next = a;
    printf("O(n) time, O(1) space: %d\n", hasCycle(a));
    return 0;
}

Practical Use

यह technique linked lists तक सीमित नहीं है; वही slow/fast pointer idea किसी भी structure में cycles detect करता है जहां आप बार-बार एक next relationship follow करते हैं, जैसे function calls या states के एक sequence में एक loop detect करना।

उदाहरण: Practical Use

#include <iostream>
using namespace std;
int nextInSequence(int n) {
    int sum = 0;
    while (n) { int d = n % 10; sum += d * d; n /= 10; }
    return sum;
}
int main() {
    int slow = 19, fast = 19;
    do {
        slow = nextInSequence(slow);
        fast = nextInSequence(nextInSequence(fast));
    } while (slow != fast);
    cout << "cycle detected in number sequence at value " << slow << endl;
    return 0;
}
public class Main {
    static int nextInSequence(int n) {
        int sum = 0;
        while (n > 0) { int d = n % 10; sum += d * d; n /= 10; }
        return sum;
    }
    public static void main(String[] args) {
        int slow = 19, fast = 19;
        do {
            slow = nextInSequence(slow);
            fast = nextInSequence(nextInSequence(fast));
        } while (slow != fast);
        System.out.println("cycle detected in number sequence at value " + slow);
    }
}
def next_in_sequence(n):
    total = 0
    while n:
        d = n % 10
        total += d * d
        n //= 10
    return total

slow = fast = 19
while True:
    slow = next_in_sequence(slow)
    fast = next_in_sequence(next_in_sequence(fast))
    if slow == fast:
        break
print("cycle detected in number sequence at value", slow)
#include <stdio.h>
int nextInSequence(int n) {
    int sum = 0;
    while (n) { int d = n % 10; sum += d * d; n /= 10; }
    return sum;
}
int main() {
    int slow = 19, fast = 19;
    do {
        slow = nextInSequence(slow);
        fast = nextInSequence(nextInSequence(fast));
    } while (slow != fast);
    printf("cycle detected in number sequence at value %d\n", slow);
    return 0;
}
Related Topics

Cycle Detection कैसे करें · Linked List को Reverse करना · दो Sorted Lists को Merge करना · Circular Linked List क्या है

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. fast->next जांचे बिना fast को दो steps move करना, जो even/odd length वाली lists पर nullptr dereference करता है।
  2. slow और fast को अलग positions पर शुरू करना और उनके move होने से पहले equality जांचना, इसलिए यह तुरंत एक cycle report करता है।
  3. Cycle detect करने को यह ढूंढने के साथ confuse करना कि यह कहां शुरू होता है, क्योंकि meeting point cycle की शुरुआत नहीं है।
🔒

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson Linked List Reversal Next Lesson → Merge Two Sorted Lists

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.