Linked List Cycle easy

Problem Statement

Given head, the head of a linked list, determine if the linked list has a cycle in it. A linked list has a cycle if there is a node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list, false otherwise.

Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the first node.

Example 3:

Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.

Steps to Solve

The most efficient approach to detect a cycle in a linked list is using the Floyd's Tortoise and Hare algorithm (also known as the "fast and slow pointer" method).

1. Initialization: Start two pointers, slow and fast, both at the head of the linked list.
2. Iteration: Move slow one step at a time, and fast two steps at a time.
3. Cycle Detection: If there is a cycle, fast will eventually lap slow. This means that slow and fast will meet at some point in the cycle. If there is no cycle, fast will reach the end of the list (its next will be null).
4. Return Value: Return true if slow and fast meet (meaning a cycle exists), and false otherwise.

Explanation

The algorithm works because if there's a cycle, the fast pointer will inevitably catch up to the slow pointer. Imagine the slow pointer as a car traveling at a constant speed, and the fast pointer as a car traveling at double the speed. If both cars are on a circular track, the faster car will eventually overtake the slower one.

The absence of a cycle implies that the fast pointer will reach the end of the list (null), indicating no cycle exists.

Code (Java)

class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false; // Empty or single-node list cannot have a cycle
        }

        ListNode slow = head;
        ListNode fast = head.next;

        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false; // No cycle detected
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        return true; // Cycle detected
    }
}

Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes in the linked list. In the worst case (no cycle), the fast pointer traverses the entire list.
• Space Complexity: O(1). The algorithm uses only a constant amount of extra space to store the slow and fast pointers.

Note: The ListNode class is assumed to be defined as follows (this is the standard definition used in LeetCode problems):

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