Detect a cycle in a linked list

Given a singly linked list, the task is to determine if the linked list has a cycle in it. A cycle occurs when a node's next pointer points back to a previous node, creating a loop.

Input-Output Examples

Example 1:

  • Input: 3 -> 2 -> 0 -> -4 -> 2 (tail connects to node with value 2)
  • Output: True (The list has a cycle)

Example 2:

  • Input: 1 -> 2 -> NULL
  • Output: False (The list does not have a cycle)

Example 3:

  • Input: 1 -> NULL
  • Output: False (The list does not have a cycle)

Approach:
Technique to be used: Floyd's Cycle-Finding Algorithm (Tortoise and Hare)

To detect a cycle in a linked list, we can use Floyd's Cycle-Finding Algorithm, also known as the Tortoise and Hare algorithm. This method involves using two pointers moving at different speeds to detect a cycle.

Steps to implement:

  1. Initialize two pointers, slow and fast, both pointing to the head of the list.
  2. Move slow one step at a time, and fast two steps at a time.
  3. If there is a cycle, slow and fast will eventually meet at some node.
  4. If fast reaches the end of the list (i.e., NULL), there is no cycle.

C++ Program to detect a cycle in a linked list

cpp
#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (!head || !head->next) return false;
        
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        
        return false;
    }
};

// Helper function to create a cycle in the linked list
void createCycle(ListNode* head, int pos) {
    if (pos == -1) return;
    
    ListNode* cycleNode = head;
    ListNode* tail = head;
    for (int i = 0; i < pos; i++) {
        cycleNode = cycleNode->next;
    }
    while (tail->next != NULL) {
        tail = tail->next;
    }
    tail->next = cycleNode;
}

int main() {
    // Creating a linked list: 3 -> 2 -> 0 -> -4 -> NULL
    ListNode* head = new ListNode(3);
    head->next = new ListNode(2);
    head->next->next = new ListNode(0);
    head->next->next->next = new ListNode(-4);

    // Creating a cycle: connecting tail to node with value 2 (index 1)
    createCycle(head, 1);

    Solution sol;
    bool has_cycle = sol.hasCycle(head);

    if (has_cycle) {
        cout << "The list has a cycle." << endl;
    } else {
        cout << "The list does not have a cycle." << endl;
    }

    return 0;
}

Java Program to detect a cycle in a linked list

java
// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        
        return false;
    }
    
    // Helper function to create a cycle in the linked list
    public static void createCycle(ListNode head, int pos) {
        if (pos == -1) return;
        
        ListNode cycleNode = head;
        ListNode tail = head;
        for (int i = 0; i < pos; i++) {
            cycleNode = cycleNode.next;
        }
        while (tail.next != null) {
            tail = tail.next;
        }
        tail.next = cycleNode;
    }

    public static void main(String[] args) {
        // Creating a linked list: 3 -> 2 -> 0 -> -4 -> NULL
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(-4);

        // Creating a cycle: connecting tail to node with value 2 (index 1)
        createCycle(head, 1);

        Solution sol = new Solution();
        boolean has_cycle = sol.hasCycle(head);

        if (has_cycle) {
            System.out.println("The list has a cycle.");
        } else {
            System.out.println("The list does not have a cycle.");
        }
    }
}

Python Program to detect a cycle in a linked list

python
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False
        
        slow, fast = head, head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        
        return False

# Helper function to create a cycle in the linked list
def create_cycle(head, pos):
    if pos == -1:
        return
    
    cycle_node = head
    tail = head
    for _ in range(pos):
        cycle_node = cycle_node.next
    
    while tail.next:
        tail = tail.next
    
    tail.next = cycle_node

# Creating a linked list: 3 -> 2 -> 0 -> -4 -> NULL
head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(0)
head.next.next.next = ListNode(-4)

# Creating a cycle: connecting tail to node with value 2 (index 1)
create_cycle(head, 1)

sol = Solution()
has_cycle = sol.hasCycle(head)

if has_cycle:
    print("The list has a cycle.")
else:
    print("The list does not have a cycle.")

Detecting a cycle in a linked list can be efficiently achieved using Floyd's Cycle-Finding Algorithm (Tortoise and Hare). This method ensures a linear time complexity of O(n), where n is the number of nodes in the list.

DSA

4556

462

Related Articles