Linked List Cycle easy

Problem Statement

Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some 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. Otherwise, return false.

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

1. Fast and Slow Pointers: Use two pointers, slow and fast. slow moves one step at a time, and fast moves two steps at a time.

2. Cycle Detection: If there is a cycle, the fast pointer will eventually lap the slow pointer. This is because the fast pointer is covering ground twice as fast.

3. No Cycle: If there's no cycle, the fast pointer will reach the end of the list (null).

4. Return Value: Return true if the pointers meet (cycle detected), and false otherwise.

Explanation

The algorithm leverages the concept of a "tortoise and hare" race. The fast pointer (hare) moves faster than the slow pointer (tortoise). If there's a cycle, the faster pointer will inevitably catch up to the slower pointer. If there's no cycle, the fast pointer will reach the end of the list before catching the slow pointer. The key insight is that the relative speed difference guarantees a meeting point within the cycle if one exists.

Code

using System;

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

public class Solution {
    public bool HasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false; // Empty list or single node - no cycle
        }

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

        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false; // Reached the end - no cycle
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        return true; // Cycle detected
    }
}

Complexity

• 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 for the slow and fast pointers.