Fast and Slow Pointers

Fast and Slow Pointers is a technique often used in various algorithms and data structures, particularly in linked list operations and cycle detection. This technique involves using two pointers that move at different speeds through a data structure. Here’s a brief explanation of how Fast and Slow Pointers work:

1. Setup: Initialize two pointers, usually named “fast” and “slow,” at the beginning of the data structure (e.g., a linked list or an array).
2. Movement: The “slow” pointer advances one step at a time, and the “fast” pointer advances by multiple steps at a time (e.g., two steps). This difference in movement speed creates a gap between the two pointers.
3. Purpose: Fast and Slow Pointers are often used for different purposes depending on the specific problem being solved.
   • Cycle Detection: In a linked list, if there’s a cycle, the fast and slow pointers will eventually meet at the same node. This property is used to detect cycles efficiently.
   • Middle Element: By the time the fast pointer reaches the end of the data structure, the slow pointer will be halfway through, pointing to the middle element. This property is used to find the middle element of a linked list.
   • Two-Pointer Approach: In algorithms that involve searching, partitioning, or manipulating elements in a data structure, Fast and Slow Pointers can be used together to traverse the structure efficiently.

The key idea behind Fast and Slow Pointers is to leverage their different movement speeds to gather information about the structure or characteristics of the data. This technique is often efficient and can simplify problem-solving by reducing the number of iterations required.

• Linked List Cycle
  Given a linked list, determine if it has a cycle in it. A cycle is when a node in the linked list points to a previously visited node, forming a loop. Return true if there is a cycle, otherwise, return false.
• Linked List Cycle II
  Given a linked list, determine if it contains a cycle. If a cycle is present, find the node where the cycle begins and return it. If there is no cycle, return nullptr.
• Happy Number
  A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle that does not include 1. If the number is a happy number, return true; otherwise, return false.
• Middle of the Linked List
  Given a singly-linked list, find the middle node of the list. If the list contains an even number of nodes, return the second middle node.