# 1. Introduction

In this blog post, we explore a fundamental problem in linked list manipulation using C programming: detecting a cycle in a linked list. Detecting a cycle is a crucial issue in many applications, such as memory management and network routing. It’s a classic problem that tests one’s understanding of pointers and linked list traversal.

## Problem

Given the head of a linked list, the task is to determine if the linked list contains a cycle. A cycle exists in a linked list if a node’s next pointer points back to an earlier node in the list. This problem challenges us to detect such cycles efficiently without modifying the list structure.

# 2. Solution Steps

1. Use two pointers: a slow pointer and a fast pointer.

2. Move the slow pointer by one step and the fast pointer by two steps in each iteration.

3. If there is a cycle, the fast pointer will eventually meet the slow pointer.

4. If the fast pointer reaches the end of the list (null), then there is no cycle.

# 3. Code Program

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
int val;
struct ListNode *next;
};

// Function to check if a linked list has a cycle

while (fast && fast->next) {
slow = slow->next;         // Move slow pointer by one step
fast = fast->next->next;   // Move fast pointer by two steps

if (slow == fast) {
return 1; // Cycle detected
}
}

return 0; // No cycle
}

// Utility function to create a new node
struct ListNode* newNode(int val) {
struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = val;
node->next = NULL;
return node;
}

// Main function to demonstrate hasCycle function
int main() {
// Create a sample list with a cycle: 1->2->3->4->2 (cycle)

int result = hasCycle(head); // Call the function
printf("Output: %d\n", result); // Print the result (1 for true, 0 for false)

// Normally, we should free the list, but it's not possible due to the cycle
// Freeing the list would require breaking the cycle, which is not part of the problem

return 0;
}

1

### Explanation:

The program checks for a cycle in a linked list using the two-pointer (or 'tortoise and hare') approach. Two pointers, slow and fast, traverse the list at different speeds. If there is a cycle, they will eventually meet inside the cycle. If the fast pointer reaches the end (null), it means there is no cycle.

In this example, the list 1->2->3->4->2 forms a cycle starting from the node with value 2. The program correctly identifies the presence of a cycle, hence the output is 1 (true).

This method is efficient as it traverses the list in linear time and does not require extra space.