Linked List Cycle: Detecting Loops in Data Structures

The "Linked List Cycle" problem involves identifying whether a cycle exists in a singly linked list.

Problem Statement

Determine if a given singly linked list has a cycle in it. In a linked list with a cycle, a node's next pointer points to an earlier node, creating a loop.

Example

Consider a linked list where the next pointer of a node points back to a previous node, forming a loop. The challenge is to detect this loop.

Solution Approach - Floyd's Tortoise and Hare Algorithm

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: ListNode | null = head;
  let fast: ListNode | null = head;

  while (fast && fast.next) {
    slow = slow ? slow.next : null;
    fast = fast.next ? fast.next.next : null;

    if (slow === fast) {
      return true; // Cycle detected
    }
  }

  return false; // No cycle found
}

Breaking Down the Solution

• Two Pointers: Initialize two pointers, slow and fast. slow moves one step at a time, while fast moves two steps.
• Iterate Through List: Move through the list, with slow and fast progressing at their respective speeds.
• Detecting the Cycle: If there is a cycle, slow and fast will eventually meet at some node. If they do, return true.
• Termination Condition: If fast or fast.next becomes null, it means the list has no cycle, and we return false.

Conclusion

The Linked List Cycle problem is a fundamental concept in data structures, particularly in understanding linked lists. Floyd's Tortoise and Hare algorithm provides an efficient way to detect cycles, demonstrating the importance of pointer manipulation and two-pointer techniques in algorithm design.