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 (0-indexed) of the node to which the tail connects. If pos is -1, then there is no cycle in the list.

You must solve the problem using O(1) extra space.

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: We utilize two pointers, a "slow" pointer that moves one step at a time and a "fast" pointer that moves two steps at a time.

2. Cycle Detection: If there's a cycle, the fast pointer will eventually lap the slow pointer. If there's no cycle, the fast pointer will reach the end of the list (null).

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

Explanation

The algorithm leverages the concept of a "tortoise and hare". If a cycle exists, the fast pointer will inevitably catch up to the slow pointer because it's moving at twice the speed. The meeting point doesn't necessarily indicate the beginning of the cycle, but its existence confirms a cycle's presence. The absence of a meeting point before the fast pointer reaches the end confirms the absence of a cycle.

Code

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.next = (next===undefined ? null : next)
    }
}

function hasCycle(head: ListNode | null): boolean {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow!.next;
        fast = fast.next.next;
        if (slow === fast) {
            return true;
        }
    }

    return false;
};

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 iterates through the entire list.
• Space Complexity: O(1). We only use two pointers, slow and fast, which requires constant extra space.