class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow){
                return true;
            }

        }
        return false;
    }
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* A = headA;
        ListNode* B = headB;
        while(A != B){
            A = A != NULL ? A ->next : headB;
            B = B != NULL ? B->next : headA;

        }
        return A;
    }
};

class Solution {
private:
    int ans;   //全局变量
    int dfs(TreeNode* node){
        if(node == NULL){
            return 0;
        }

        int l_val = dfs(node->left);
        int r_val = dfs(node->right);
        ans = max(ans, l_val + r_val + node->val);
        return max(max(l_val, r_val) + node->val, 0);   //注意这里要用0截断负收益
    }
public:
    int maxPathSum(TreeNode* root) {
        ans = INT_MIN;
        dfs(root);
        return ans;
    }
};

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        int depth = 0;
        int l_depth = maxDepth(root->left);
        int r_depth = maxDepth(root->right);

        return max(l_depth, r_depth) + 1;
    }
};

class Solution {
public:
    int ans = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        auto dfs = [&](this auto&& dfs, TreeNode* node){
            if(node == nullptr){
                return -1;
            }
            int l_len = dfs(node->left) + 1;
            int r_len = dfs(node->right) + 1;
            ans = max(ans, l_len + r_len);
            return max(l_len, r_len);
        };
        dfs(root);
        return ans;
    }
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){
                while(slow != head){
                    slow = slow->next;
                    head = head->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0, pre_max = 0, suf_max = 0;
        int left = 0, right = height.size() - 1;
        while(left < right){
            pre_max = max(pre_max, height[left]);
            suf_max = max(suf_max, height[right]);
            ans += pre_max > suf_max ? suf_max-height[right--] : pre_max-height[left++];
        }
        return ans;
    }
};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i0 = 0;
        for(int& x : nums){
            if(x){
                swap{x, nums[i0]};
                i0++;
            }
        }
    }
};