Using Fast and Slow Pointers
1. Understanding Floyd's Cycle Detection
| Aspect | Description | Details |
|---|---|---|
| Algorithm Name | Used For | Detecting cycles in linked lists |
| Two Pointers | Approach | Slow pointer moves one step, fast pointer moves two steps |
| Cycle Detection | Logic | If there's a cycle, fast pointer will eventually catch up to slow pointer |
| Time Complexity | Best Case | O(n) |
| Space Complexity | Best Case | O(1) |
Example: Detecting a Cycle in a Linked List
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function hasCycle(head) {
if (!head || !head.next) return false;
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
// Example usage:
const node1 = new ListNode(3);
const node2 = new ListNode(2);
const node3 = new ListNode(0);
const node4 = new ListNode(-4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // Creates a cycle
console.log(hasCycle(node1)); // true
Note: Floyd's cycle detection is also known as the "tortoise and hare" algorithm.
2. Detecting Cycle in LinkedList
| Approach | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Fast and Slow Pointers | Use two pointers moving at different speeds. If there's a cycle, they will eventually meet. | O(n) |
O(1) |
Example: Detecting Cycle in a LinkedList
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
return true; // Cycle detected
}
}
return false; // No cycle
}
// Example usage:
const node1 = new ListNode(3);
const node2 = new ListNode(2);
const node3 = new ListNode(0);
const node4 = new ListNode(-4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // Creates a cycle
console.log(hasCycle(node1)); // true
Note: The fast pointer moves twice as fast as the slow pointer. If there is a cycle, they will meet at some point inside the cycle.
3. Finding Middle of LinkedList
| Property | Description | Usage |
|---|---|---|
| fastPointer | Traverses twice as fast as slow pointer | Used to detect end of list or find middle |
| slowPointer | Traverses one node at a time | Used to find middle element when fast pointer reaches end |
Example: Finding Middle Node
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function findMiddle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow.val;
}
// Example usage:
const list = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
console.log(findMiddle(list)); // Output: 3
Note: When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.
4. Checking Palindrome LinkedList
| Property | Description | Usage |
|---|---|---|
| isPalindrome(head) | Checks if a linked list is a palindrome using fast/slow pointers | Returns true if the list is a palindrome, otherwise false |
Example: isPalindrome
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function isPalindrome(head) {
if (!head || !head.next) return true;
let slow = head;
let fast = head;
// Find the middle of the list
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse the second half
let prev = null;
let current = slow;
while (current) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
// Compare first and second half
let left = head;
let right = prev;
while (right) {
if (left.val !== right.val) return false;
left = left.next;
right = right.next;
}
return true;
}
// Example usage:
const list1 = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(1))));
console.log(isPalindrome(list1)); // true
const list2 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
console.log(isPalindrome(list2)); // false
Note: This approach uses O(1) extra space and O(n) time complexity.
5. Finding Happy Number
A happy number is 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 which does not include 1.
- If the process ends in 1, the number is happy.
Use the fast and slow pointer technique to detect cycles in this process.
| Property | Description | Example |
|---|---|---|
| Input | Positive integer | 19 |
| Process | Sum of squares of digits | 1² + 9² = 1 + 81 = 82 |
| Cycle Detection | Use fast and slow pointers to detect loops | Same as in linked list cycle detection |
Example: Happy Number Check
function isHappy(n) {
function getSquareSum(num) {
let sum = 0;
while (num > 0) {
const digit = num % 10;
sum += digit * digit;
num = Math.floor(num / 10);
}
return sum;
}
let slow = n;
let fast = n;
do {
slow = getSquareSum(slow);
fast = getSquareSum(getSquareSum(fast));
} while (slow !== fast && slow !== 1);
return slow === 1;
}
// Example usage:
console.log(isHappy(19)); // true
console.log(isHappy(2)); // false
Note: The fast pointer moves two steps at a time, while the slow pointer moves one step. If there's a cycle, they will eventually meet.
6. Finding Cycle Start Node
When a cycle exists in a linked list, the fast and slow pointers will eventually meet. Once they meet, we can find the start of the cycle using a specific technique.
| Step | Description | Action |
|---|---|---|
| 1 | Move one pointer to the head of the list | Reset slow to the head, keep fast at the meeting point |
| 2 | Advance both pointers at same speed | Move slow and fast one step at a time until they meet again |
| 3 | Meeting point is the cycle start | The node where they meet is the beginning of the cycle |
Example: Finding the Start of a Cycle in a Linked List
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function findCycleStart(head) {
let slow = head;
let fast = head;
// Phase 1: Detect if there's a cycle
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
break;
}
}
// If no cycle exists, return null
if (!fast || !fast.next) {
return null;
}
// Phase 2: Find the start of the cycle
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // Start of the cycle
}
// Example usage:
const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
const node4 = new ListNode(4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // Creates a cycle
console.log(findCycleStart(node1).val); // Output: 2
Note: The algorithm works because when the two pointers meet inside the cycle, the distance from the head to the start of the cycle equals the distance from the meeting point to the start of the cycle, when traveling around the cycle once.
7. Rearranging LinkedList
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Reorder List | Reorders a singly linked list to alternate between first and last nodes. | O(n) |
O(1) |
| Reverse Sublist | Reverses a portion of the list between given positions. | O(n) |
O(1) |
| Remove Duplicates | Removes duplicates from a sorted list in-place. | O(n) |
O(1) |
Example: Reorder List
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function reorderList(head) {
if (!head || !head.next) return;
// Step 1: Find the middle of the list
let slow = head, fast = head;
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
// Step 2: Reverse the second half
let prev = null, curr = slow.next;
slow.next = null; // Break the list
while (curr) {
let next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// Step 3: Merge the two halves
let first = head, second = prev;
while (second) {
let next1 = first.next, next2 = second.next;
first.next = second;
second.next = next1;
first = next1;
second = next2;
}
}
// Example usage:
const list = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
reorderList(list);
// Result: [1, 4, 2, 3]Example: Remove Duplicates
function removeDuplicates(head) {
if (!head) return null;
let current = head;
while (current && current.next) {
if (current.val === current.next.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
// Example usage:
const list = new ListNode(1, new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(3)))));
const result = removeDuplicates(list);
// Result: [1, 2, 3]8. Finding Duplicate Number
| Approach | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Floyd's Cycle Detection | Uses two pointers moving at different speeds to detect a cycle in the array, treating it as a linked list where each value points to an index. | O(n) |
O(1) |
Example: Finding Duplicate Number Using Floyd's Cycle Detection
function findDuplicate(nums) {
// Phase 1: Detect cycle
let slow = nums[0];
let fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow !== fast);
// Phase 2: Find entrance to cycle
slow = nums[0];
while (slow !== fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
// Example usage:
const nums = [1, 3, 4, 2, 2];
console.log(findDuplicate(nums)); // Output: 2
Note: This approach treats the array as a linked list where each value points to an index, and uses Floyd's cycle detection algorithm to find the duplicate.
9. Removing Nth Node from End
| Property | Description | Usage |
|---|---|---|
| fast/slow pointers | Two pointers moving at different speeds to traverse list | Use to find nth node from end |
| distance between pointers | Fixed gap to maintain between fast and slow pointer | Set to n steps ahead |
Example: Remove Nth Node from End
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function removeNthFromEnd(head, n) {
let fast = head;
let slow = head;
// Move fast pointer n steps ahead
for (let i = 0; i < n; i++) {
fast = fast.next;
}
// If fast is null, remove head node
if (!fast) {
return head.next;
}
// Move both pointers until fast reaches end
while (fast.next) {
fast = fast.next;
slow = slow.next;
}
// Remove the nth node from end
slow.next = slow.next.next;
return head;
}
// Example usage:
const list = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const result = removeNthFromEnd(list, 2); // Removes 4
Note: This approach uses two pointers to find the node before the target in one pass.
10. Detecting Intersection of Lists
| Property | Description | Usage |
|---|---|---|
| Intersection Detection | Detects if two linked lists intersect at a common node. | Used in list manipulation and memory management. |
Example: Detecting List Intersection
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
function getIntersectionNode(headA, headB) {
if (!headA || !headB) return null;
let pointerA = headA;
let pointerB = headB;
while (pointerA !== pointerB) {
pointerA = pointerA ? pointerA.next : headB;
pointerB = pointerB ? pointerB.next : headA;
}
return pointerA; // Intersection node or null
}
// Example usage:
const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
const node4 = new ListNode(4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
const node5 = new ListNode(5);
const node6 = new ListNode(6);
node5.next = node6;
node6.next = node3; // Intersection at node3
console.log(getIntersectionNode(node1, node5).val); // 3
Note: The fast and slow pointer technique is not directly used here, but the two-pointer approach efficiently detects intersections by traversing both lists.