Linked List Cycle - C Solution

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>

// Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};

// Function to check if a linked list has a cycle
int hasCycle(struct ListNode *head) {
    struct ListNode *slow = head, *fast = head;

    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)
    struct ListNode* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = head->next; // Creating a 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;
}

Output:

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.