Fast and Slow Pointers (Hare & Tortoise Algorithm)
The Fast and Slow Pointers approach, also known as the Hare & Tortoise Algorithm, is a pointer algorithm that uses two pointers which move through the array (or sequence/linked list) at different speeds.
This approach is extremely useful when dealing with cyclic linked lists or arrays, or when you need to find the middle node of a linked list.
By moving at different speeds, if there is a cycle, the two pointers are bound to meet.
1. Linked List Cycle
Problem: Given the head of a linked list, determine if the linked list has a cycle in it.
Approach:
Initialize two pointers, slow and fast, both pointing to the head. slow moves 1 step at a time, while fast moves 2 steps. If there is a cycle, the fast pointer will eventually catch up to the slow pointer. If fast reaches the end (null), there is no cycle.
const hasCycle = function(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
return true; // Cycle detected
}
}
return false;
};Time Complexity: O(N)
Space Complexity: O(1)
2. Linked List Cycle II (Find Cycle Start)
Problem: Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Approach:
First, detect the cycle using the Hare & Tortoise algorithm. Once slow and fast meet, reset slow to the head. Then, move both slow and fast one step at a time. The node where they meet again is the start of the cycle.
const detectCycle = function(head) {
let slow = head, fast = head;
let hasCycle = false;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
hasCycle = true;
break;
}
}
if (!hasCycle) return null;
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // Start of cycle
};Time Complexity: O(N)
Space Complexity: O(1)
3. Middle of the Linked List
Problem: Given the head of a singly linked list, return the middle node of the linked list.
Approach:
Move slow by 1 step and fast by 2 steps. When fast reaches the end of the list, slow will be exactly at the middle.
const middleNode = function(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
};Time Complexity: O(N)
Space Complexity: O(1)
4. Happy Number
Problem: Write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process: replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1, or it loops endlessly in a cycle.
Approach: Any number will either reach 1 or fall into a cycle. We can use the fast and slow pointer technique to detect this cycle.
const isHappy = function(n) {
const getNext = (num) => {
let totalSum = 0;
while (num > 0) {
let d = num % 10;
num = Math.floor(num / 10);
totalSum += d * d;
}
return totalSum;
};
let slow = n;
let fast = getNext(n);
while (fast !== 1 && slow !== fast) {
slow = getNext(slow);
fast = getNext(getNext(fast));
}
return fast === 1;
};Time Complexity: O(log N) (The number of digits)
Space Complexity: O(1)
5. Find the Duplicate Number
Problem: Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n], return the only repeated number without modifying the array and using O(1) space.
Approach:
Treat the array values as pointers to indices (e.g., nums[i] points to index nums[i]). Because there is a duplicate, there will be a cycle. This problem then reduces to finding the start of the cycle (Linked List Cycle II).
const findDuplicate = function(nums) {
let slow = nums[0];
let fast = nums[0];
// Find intersection point in the cycle
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow !== fast);
// Find the "entrance" to the cycle
slow = nums[0];
while (slow !== fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
};Time Complexity: O(N)
Space Complexity: O(1)
6. Palindrome Linked List
Problem: Given the head of a singly linked list, return true if it is a palindrome.
Approach:
- Find the middle of the linked list using fast and slow pointers.
- Reverse the second half of the linked list.
- Compare the first half and the reversed second half.
const isPalindrome = function(head) {
if (!head || !head.next) return true;
// 1. Find the middle
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
// 2. Reverse the second half
let prev = null;
let curr = slow;
while (curr !== null) {
let nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
// 3. Compare the halves
let p1 = head;
let p2 = prev; // Head of the reversed second half
while (p2 !== null) {
if (p1.val !== p2.val) return false;
p1 = p1.next;
p2 = p2.next;
}
return true;
};Time Complexity: O(N)
Space Complexity: O(1)
7. Maximum Twin Sum of a Linked List
Problem: In a linked list of size n, the ith node and the (n-1-i)th node are twins. Find the maximum twin sum of the linked list.
Approach: Similar to the Palindrome problem: find the middle, reverse the second half, and then iterate through both halves simultaneously, calculating the sum of the twins and keeping track of the maximum.
const pairSum = function(head) {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
let prev = null, curr = slow;
while (curr !== null) {
let nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
let maxSum = 0;
let p1 = head, p2 = prev;
while (p2 !== null) {
maxSum = Math.max(maxSum, p1.val + p2.val);
p1 = p1.next;
p2 = p2.next;
}
return maxSum;
};Time Complexity: O(N)
Space Complexity: O(1)
8. Circular Array Loop
Problem: Determine if an array has a cycle of length > 1, where nums[i] represents the number of jumps forward/backward. The cycle must be entirely in one direction (all positive or all negative jumps).
Approach:
Use fast and slow pointers. For each index, trace the path. If the direction changes or the cycle length is 1, break. If slow meets fast, a valid cycle exists.
const circularArrayLoop = function(nums) {
const getNextIndex = (i) => {
let n = nums.length;
let next = (i + nums[i]) % n;
if (next < 0) next += n; // Handle negative JS modulo
return next === i ? -1 : next; // Cycle length must be > 1
};
for (let i = 0; i < nums.length; i++) {
if (nums[i] === 0) continue;
let slow = i, fast = i;
let isForward = nums[i] > 0;
while (true) {
slow = getNextIndex(slow);
if (slow === -1 || (nums[slow] > 0) !== isForward) break;
fast = getNextIndex(fast);
if (fast === -1 || (nums[fast] > 0) !== isForward) break;
fast = getNextIndex(fast);
if (fast === -1 || (nums[fast] > 0) !== isForward) break;
if (slow === fast) return true;
}
// Mark failed paths as 0 to avoid re-evaluating
let j = i;
let val = nums[i];
while (nums[j] !== 0 && (nums[j] > 0) === isForward) {
let nextJ = getNextIndex(j);
nums[j] = 0;
j = nextJ;
}
}
return false;
};Time Complexity: O(N)
Space Complexity: O(1)