Fast and Slow Pointers, Coding Interview Pattern

Fast and Slow Pointers

The Fast and Slow Pointers technique, also known as the Tortoise and Hare algorithm, is a powerful method used to solve problems related to cycle detection in linked lists and arrays, as well as finding the middle of a linked list and other similar tasks. It involves two pointers that traverse the data structure at different speeds: the "fast" pointer typically moves two steps at a time, while the "slow" pointer moves one step at a time. This difference in speed allows the algorithm to efficiently detect cycles when the pointers meet and identify the middle element of a list.

Linked List Cycle

This question is part of Leetcode problems, question no. 141.

Here's the Solution class for the "Linked List Cycle" problem in C++:

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) {
            return false;
        }

        ListNode *slow = head;
        ListNode *fast = head->next;

        while (slow != fast) {
            if (!fast || !fast->next) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }

        return true;
    }
};

Middle of the Linked List

This question is part of Leetcode problems, question no. 876.

Here's the Solution class for the "Middle of the Linked List" problem in C++:

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};

Find the Duplicate Number

This question is part of Leetcode problems, question no. 287.

Here's the Solution class for the "Find the Duplicate Number" problem in C++:

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];

        // Phase 1: Finding the intersection point of the two runners.
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // Phase 2: Finding the entrance to the cycle.
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};

Palindrome Linked List

This question is part of Leetcode problems, question no. 234.

Here's the Solution class for the "Palindrome Linked List" problem in C++:

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head) return true;

        // Find the end of the first half and reverse the second half.
        ListNode* firstHalfEnd = endOfFirstHalf(head);
        ListNode* secondHalfStart = reverseList(firstHalfEnd->next);

        // Check whether or not there's a palindrome.
        ListNode* p1 = head;
        ListNode* p2 = secondHalfStart;
        bool result = true;
        while (result && p2) {
            if (p1->val != p2->val) {
                result = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }

        // Restore the list and return the result.
        firstHalfEnd->next = reverseList(secondHalfStart);
        return result;
    }

private:
    ListNode* endOfFirstHalf(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
};

Linked List Cycle II

This question is part of Leetcode problems, question no. 142.

Here's the Solution class for the "Linked List Cycle II" problem in C++:

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) {
            return nullptr;
        }

        ListNode *slow = head;
        ListNode *fast = head;

        // Detect if there's a cycle
        do {
            if (!fast || !fast->next) {
                return nullptr;
            }
            slow = slow->next;
            fast = fast->next->next;
        } while (slow != fast);

        // Find the start of the cycle
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};

Reorder List

This question is part of Leetcode problems, question no. 143.

Here's the Solution class for the "Reorder List" problem in C++:

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;

        // Find the middle of the list
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // Reverse the second half of the list
        ListNode* prev = nullptr;
        ListNode* curr = slow;
        while (curr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // Merge the two halves
        ListNode* first = head;
        ListNode* second = prev;
        while (second->next) {
            ListNode* temp1 = first->next;
            ListNode* temp2 = second->next;
            first->next = second;
            second->next = temp1;
            first = temp1;
            second = temp2;
        }
    }
};

Length of Linked List Loop

This question is part of Leetcode problems, question no. 141 (Linked List Cycle).

Here's the Solution class for finding the length of the linked list loop in C++:

class Solution {
public:
    int lengthOfCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) {
                return countCycleLength(slow);
            }
        }

        return 0; // No cycle
    }

private:
    int countCycleLength(ListNode *node) {
        ListNode *current = node;
        int length = 0;

        do {
            current = current->next;
            length++;
        } while (current != node);

        return length;
    }
};

Sort List

This question is part of Leetcode problems, question no. 148.

Here's the Solution class for the "Sort List" problem in C++:

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }

        // Split the list into two halves
        ListNode* mid = getMid(head);
        ListNode* left = sortList(head);
        ListNode* right = sortList(mid);

        // Merge the two sorted halves
        return merge(left, right);
    }

private:
    ListNode* getMid(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* prev = nullptr;

        while (fast && fast->next) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }

        if (prev) {
            prev->next = nullptr;
        }

        return slow;
    }

    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;

        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }

        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

Practice these questions diligently to enhance your problem-solving skills. Remember, consistent practice is key to mastering these concepts. If you find yourself stuck or in need of further clarification, be sure to check out video references and tutorials to clear up any doubts.