Code snippets for my permanent memory

class TrieNode {
public:
    bool isEnd;
    TrieNode* children[26];
 
    TrieNode() {
        isEnd = false;
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};
 
class Trie {
private:
    TrieNode* root;
 
public:
    Trie() {
        root = new TrieNode();
    }
 
    // Insert a word into the trie.
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (node->children[idx] == nullptr) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->isEnd = true;
    }
 
    // Search a word in the trie.
    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (node->children[idx] == nullptr) {
                return false;
            }
            node = node->children[idx];
        }
        return node->isEnd;
    }
 
    // Check if there exists any word that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (node->children[idx] == nullptr) {
                return false;
            }
            node = node->children[idx];
        }
        return true;
    }
};

ListNode* reverseList(ListNode* head) {
    ListNode* previous = nullptr;
    ListNode* current = head;
 
    while (current != nullptr) {
        ListNode* nextNode = current->next;
        current->next = previous;
        previous = current;
        current = nextNode;
    }
 
    return previous;
}

ListNode* findMiddle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
 
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
 
    return slow;
}

ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
 
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            // Cycle detected
            return slow;
        }
    }
 
    return nullptr; // No cycle
}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy;
    ListNode* tail = &dummy;
 
    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
 
    if (l1 != nullptr) tail->next = l1;
    if (l2 != nullptr) tail->next = l2;
 
    return dummy.next;
}

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
 
    while (left <= right) {
        int mid = left + (right - left) / 2;
 
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
 
    return -1; // Not found
}

class Solution {
private:
    void backtrack(/* input parameters */,
                   /* current state */,
                   /* result container */) {
        if (/* base case: final condition reached */) {
            // Save current valid result
            return;
        }
 
        for (/* all choices at this step */) {
            // Make a choice
            // Move forward (recursive call)
            // Undo the choice (backtrack)
        }
    }
 
public:
    vector<string> solveProblem(/* input */) {
        vector<string> results;
        string currentState; // or vector<int>, etc.
        backtrack(/* inputs */, /* initial state */, results);
        return results;
    }
};