Linked List Cycle - Java Solution

1. Introduction

In this post, we explore a fundamental problem in linked list operations known as the "Linked List Cycle" problem. It involves determining whether a given linked list contains a cycle — a condition where a node's next pointer points to an earlier node in the list, creating a loop.

Problem

Given the head of a linked list, the task is to determine if the linked list has a cycle. A cycle occurs if a node in the list can be reached again by continuously following the next pointer. The challenge is to identify the presence of such a cycle without knowing the position of the tail's next pointer.

2. Solution Steps

1. Use two pointers, slow and fast, both initially pointing to the head of the list.

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

3. If the linked list has a cycle, slow and fast will eventually meet; otherwise, fast will reach the end of the list.

4. Return true if slow and fast meet; otherwise, return false.

3. Code Program

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class LinkedListCycle {
    public static void main(String[] args) {
        // Example use case
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(-4);
        head.next.next.next.next = head.next; // Creating a cycle

        System.out.println(hasCycle(head)); // Test the function
    }

    // Function to detect a cycle in a linked list
    public static boolean hasCycle(ListNode head) {
        if (head == null) return false;

        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

Output:

true

Explanation:

1. hasCycle: This function checks for the presence of a cycle in the linked list.

2. Two pointers, slow and fast, are used. slow moves one step at a time, while fast moves two steps.

3. If there's a cycle, slow and fast will eventually point to the same node, indicating a cycle.

4. If fast reaches the end of the list (null), it means there's no cycle.

5. The function returns true if a cycle is detected, otherwise false.

6. This approach, known as Floyd's Tortoise and Hare algorithm, efficiently detects cycles without using extra space for storage.