#141 - Linked List Cycle

EasyLinked List

Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if some node can be reached again by continuously following next. Return true if there is a cycle, false otherwise.

Input	Output
head = [3,2,0,-4], tail connects to index 1	true
head = [1,2], tail connects to index 0	true
head = [1], no cycle	false

Solution Space

Try it

/**
 * Detects whether a linked list contains a cycle (Floyd's algorithm).
 *
 * @param head Head of the linked list
 * @returns    true if a cycle exists, false otherwise
 */
export function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;

    if (slow === fast) return true; // pointers met → cycle
  }

  return false; // fast reached the end → no cycle
}

Approach: Floyd's tortoise and hare – `slow` advances one node, `fast` advances two. If a cycle exists they will eventually meet; if not, `fast` reaches `null`.

Time: O(n) – in the worst case, `fast` traverses the cycle at most twice before meeting `slow`.

Space: O(1) – two pointer variables.

Alternative approaches:

Approach	Idea	Time	Space
Hash set	Store every visited node in a Set; if next is already in the set, there is a cycle.	O(n)	O(n)

Why Floyd's algorithm is preferred: it achieves the same O(n) time with O(1) space, making it strictly better in memory usage.

#138 Copy List with Random Pointer

#206 Reverse Linked List