class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 创建哈希表
        unordered_map<int, int> hashtable;
        // 只用遍历一次数组
        for (int i = 0; i < nums.size(); ++i) {
            // 尝试寻找目标元素
            auto it = hashtable.find(target - nums[i]);
            // 找到了，返回答案
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            // 将x插入到哈希表中，保证不会与自己匹配
            hashtable[nums[i]] = i;
        }
        return {};
    }
};

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // string是每一组字母异位词排序后的结果，将其设置为哈希表的键
        unordered_map<string, vector<string>> mp;
        for (string& str: strs) {
            // 创建字符串key存放排序后的结果
            string key = str;
            sort(key.begin(), key.end());
            // 向哈希表的该键插入值，创建对应关系
            mp[key].push_back(str);
        }

        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); it++) {
            // 将哈希表的值压入vector
            ans.push_back(it->second);
        }
        return ans;
    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size() == 0) return 0; // 特判空数组
        int ans = 1; // 记录最终答案
        int tmp = 1; // 记录当前答案
        sort(nums.begin(), nums.end());

        int i = 0, j = i + 1; // 双指针
        while (j < nums.size()) { // 遍历数组
            // 若相差1，则当前答案++，指针往后移
            if (nums[j] - nums[i] == 1) {
                tmp++;
                i = j++;
            } else { // 若相差不为1，则需要判断是相等还是相差超过1
                // 先更新答案，再判断要不要将当前tmp归零
                if (tmp > ans) ans = tmp;
                // 若相等，则只用把两个指针往后挪
                if (nums[j] == nums[i]) {
                    i = j++;
                    continue;
                }
                // 否则将tmp归零，再将指针往后挪
                tmp = 1;
                i = j++;
            }
        }
        // 最后再更新一次答案
        if (tmp > ans) ans = tmp;
        return ans;
    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end());
        int res = 0;
        // 遍历哈希集合而不是 nums 
        // 如果测试用例为 [1,1,1,…,1,2,3,4,5,…]，遍历 nums 的做法会导致每一个 1 都跑一个 O(n) 的循环
        for (auto& x : st) {
            if (st.contains(x - 1)) {
                continue;
            }
            int y = x + 1;
            while (st.contains(y)) {
                ++y;
            }
            res = max(res, y - x);
        }
        return res;
    }
};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

class Solution {
public:
    int maxArea(vector<int>& height) {
        int len = height.size(); // 数组长度
        int i = 0, j = len - 1; // 定义双指针，指向起点与终点
        int ans = 0; // 记录答案

        while (i < j) {
            int tmp = min(height[i], height[j]) * (j - i);
            if (tmp > ans) ans = tmp;
            // 每次移动短板
            if (height[i] > height[j]) {
                j--;
            } else {
                i++;
            }
        }
        return ans;
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int len = nums.size();
        // 先对数组进行排序，避免后续枚举时计算重复三元组
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;

        // 第一重循环枚举a
        for (int first = 0; first < len; ++first) {
            // 先判断当前枚举到的元素是否与上一个元素相同，避免重复
            if (first > 0 && nums[first] == nums[first - 1]) continue;

            // 指向c的指针，开始初始化在最右端
            int third = len - 1;
            int target = -nums[first];

            // 第二重循环枚举b
            for (int second = first + 1; second < len; ++second) {
                // 先判断当前枚举到的元素是否与上一个元素相同，避免重复
                if (second > first + 1 && nums[second] == nums[second - 1]) continue;
                
                // 保证b始终在c左侧
                while (second < third && nums[second] + nums[third] > target)
                    --third;

                // 指针相遇就枚举完了
                if (second == third) break;
                
                // 找到一组解
                if (nums[second] + nums[third] == target)
                    ans.push_back({nums[first], nums[second], nums[third]});
            }
        }
        return ans;
    }
};

class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size(); // 记录数组长度
        int ans = 0;
        vector<int> left_max(len); // 左侧柱子最大值
        vector<int> right_max(len); // 右侧柱子最大值

        // 初始化dp数组
        left_max[0] = height[0];
        right_max[len - 1] = height[len - 1];

        for (int i = 1; i < len; i++) {
            left_max[i] = max(left_max[i - 1], height[i]);
        }
        for (int i = len - 2; i >= 0; i--) {
            right_max[i] = max(right_max[i + 1], height[i]);
        }

        for (int i = 0; i < len; i++) {
        	// 判断是否为负数，非负就累加到答案
            if (min(left_max[i], right_max[i]) - height[i] >= 0)
                ans += min(left_max[i], right_max[i]) - height[i];
        }
        return ans;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.length() == 0) return 0;
        int ans = 1;
        int len = s.length(); // 字符串长度
        int i = 0, j = 1; // 双指针滑动窗口

        while (i < len - 1) {
            // 每次都从当前窗口第一个字母遍历一遍，看是否有重复
            bool flag = true; // 判断是否有重复
            int k;
            for (k = i; k < j; ++k) {
                if (s[j] == s[k]) {
                    flag = false;
                    break;
                }
            }
            // 若无重复，则更新答案
            if (flag) {
                if (j - i + 1 > ans) ans = j - i + 1;
                j++; //快指针往后挪
            } else { // 若有重复，则移动慢指针
                i = k + 1;
            }
            if (j > len - 1) break;
        }
        return ans;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) return 0;
        int ans = 1;
        int len = s.length(); // 字符串长度
        int i = 0, j = 0; // 滑动窗口的左右指针
        unordered_set<char> charSet; // 存储窗口中的字符

        while (i < len && j < len) {
            if (charSet.find(s[j]) == charSet.end()) { // 当前字符不在窗口中
                charSet.insert(s[j++]); // 将当前字符加入窗口，并向右移动窗口
                ans = max(ans, j - i); // 更新最大长度
            } else { // 当前字符在窗口中
                charSet.erase(s[i++]); // 移除窗口左边界的字符，并向右移动左指针
            }
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        int len_s = s.length(); // s的长度
        int len_p = p.length(); // p的长度
        sort(p.begin(), p.end()); // 对p进行排序

        int i = 0, j = i + len_p - 1; // 滑动窗口
        while (j < len_s) {
            // 将滑动窗口中的字串取出，存放到tmp中
            string tmp = "";
            
            tmp.append(s.substr(i, len_p));
            
            sort(tmp.begin(), tmp.end());
            if (!tmp.compare(p)) { // 若两个字符串相等
                ans.push_back(i);
            }

            i++, j++; // 往后移动滑动窗口
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int len_s = s.length(); // s的长度
        int len_p = p.length(); // p的长度
        if (len_s < len_p) return vector<int>();

        vector<int> ans;
        vector<int> sCNT(26); // 记录s串中字母出现次数
        vector<int> pCNT(26); // 记录p串中字母出现次数
        for (int i = 0; i < len_p; ++i) {
            ++sCNT[s[i] - 'a'];
            ++pCNT[p[i] - 'a'];
        }

        // 0位置开始的滑动窗口中的字符串与目标字符串互为字母异位
        if (sCNT == pCNT) ans.push_back(0); 

        for (int i = 0; i < len_s - len_p; ++i) {
            // 移动窗口
            --sCNT[s[i] - 'a'];
            ++sCNT[s[i + len_p] - 'a'];

            if (sCNT == pCNT) {
                ans.push_back(i + 1);
            }
        }
        return ans;
    }
};

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1; // 和为0出现了1次
        int ans = 0, pre = 0;
        for (auto& x : nums) { // 遍历数组（移动i）
            pre += x; // 记录前缀和
            if (mp.find(pre - k) != mp.end()) {
                ans += mp[pre - k]; // 找到了一组[j, i]子数组
            }
            mp[pre]++; // 当前前缀和出现次数+1
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int len = nums.size();
        // 优先队列默认从大到小排序
        // 在pair中存放的是“值-index”的二元组
        priority_queue<pair<int, int>> q;
        
        // 先将前k个元素压入优先队列中
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }

        vector<int> ans = {q.top().first}; // 先存放当前队列的最大值
        for (int i = k; i < len; i++) {
            q.emplace(nums[i], i); // 向队列中添加新元素
            // 若当前最大值不在滑动窗口中，则弹出队列
            while (q.top().second <= i - k) {
                q.pop();
            }
            ans.push_back(q.top().first); // 向答案中添加当前窗口中的最大值
        }
        return ans;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        int dp[len + 5]; // dp[i]表示以nums[i]结尾的最大子数组和

        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < len; ++i) {
            if (nums[i] + dp[i - 1] > nums[i]) 
                dp[i] = nums[i] + dp[i - 1];
            else dp[i] = nums[i];
            if (dp[i] > max) max = dp[i];
        }
        return max;
    }
};

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return {};
        // 先按照左边界排序
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        for (int i = 0; i < intervals.size(); ++i) {
            int left = intervals[i][0], right = intervals[i][1];
            // 如果merged数组为空，或者与merged的最后一个数组没有重叠部分
            if (!merged.size() || merged.back()[1] < left) {
                merged.push_back({left, right});
            } else { // 有重叠部分，更新merged末尾的右边界（合并）
                merged.back()[1] = max(merged.back()[1], right);
            }
        }
        return merged;
    }
};

class Solution {
public:
    // ori记录t字符串，cnt记录s字符串
    unordered_map <char, int> ori, cnt; 

    // 判断是否包含子串
    bool check() {
        for (const auto &p: ori) {
            if (cnt[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        // 维护一个t串的哈希表
        for (const auto &c: t) {
            ++ori[c];
        }

        // 左右指针
        int l = 0, r = -1;
        // len为当前s中的长度，ansL与ansR记录答案子串的首尾索引
        int len = INT_MAX, ansL = -1, ansR = -1;

        while (r < int(s.size())) {
            // 扩展窗口
            if (ori.find(s[++r]) != ori.end()) {
                ++cnt[s[r]];
            }
            // 判断子串是否包含t字符串
            while (check() && l <= r) {
                // 长度更短则更新
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l; // 更新答案首部索引
                }
                // 尝试收缩滑动窗口
                if (ori.find(s[l]) != ori.end()) {
                    --cnt[s[l]];
                }
                ++l;
            }
        }
        return ansL == -1 ? "" : s.substr(ansL, len);
    }
};

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        while (k--) {
            for (int i = n - 1; i > 0; --i) {
                swap(nums[i], nums[i-1]);
            }
        }
    }
};

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if (k < n) {
            vector<int> res;
            for (int i = n - k; i < n; ++i) {
                res.push_back(nums[i]);
            }
            for (int i = 0; i < n - k; ++i) {
                res.push_back(nums[i]);
            }
            nums = res;
        } else {
            while (k--) {
                for (int i = n - 1; i > 0; --i) {
                    swap(nums[i], nums[i-1]);
                }
            }
        }
    }
};

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> newArr(n);
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        nums.assign(newArr.begin(), newArr.end());
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ans;
        vector<int> pre_front; // 前缀乘积
        vector<int> pre_back; // 后缀乘积
        int len = nums.size();

        int tmp = 1;
        // 计算前缀乘积
        for (int i = 0; i < len; ++i) {
            tmp *= nums[i];
            pre_front.push_back(tmp);
        }
        tmp = 1;
        // 计算后缀乘积
        for (int i = len - 1; i >= 0; --i) {
            tmp *= nums[i];
            pre_back.push_back(tmp);
        }

        for (int i = 0; i < len; ++i) {
            if (i == 0) {
                ans.push_back(pre_back[len - 2]);
            } else if (i == len - 1) {
                ans.push_back(pre_front[len - 2]);
            } else {
                ans.push_back(pre_front[i - 1] * pre_back[len - 2 - i]);
            }
        }
        return ans;
    }
};

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int len = nums.size();
        long long ans;
        sort(nums.begin(), nums.end());
        // 假设给定数组的正整数部分都连续，答案就是最后一个元素+1
        if (nums[len - 1] > 0) {
            // 有一个数据点是INT_MAX，这里先强转一下防溢出
            ans = (long long)nums[len - 1] + 1;
        } else { // 若数组中没有正整数，答案就为1
            ans = 1;
        }
        int min = 1;
        int flag; // 记录最小正整数的index
        for (int i = 0; i < len; ++i) {
            if (nums[i] > 0) {
                min = nums[i];
                flag = i;
                break;
            }
        }

        if (min != 1) {
            return 1;
        } else { // 寻找不连续的两个正整数
            for (int i = flag + 1; i < len; ++i) {
                if (nums[i] - nums[i - 1] != 1 && nums[i] - nums[i - 1] != 0) {
                    ans = nums[i - 1] + 1;
                    break;
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end());
        int mx = *max_element(nums.begin(), nums.end());
        for (int i = 1; i <= mx; ++i) {
            if (!st.contains(i)) {
                return i;
            }
        }
        return mx > 0 ? mx + 1 : 1;
    }
};

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(); // 行数
        int n = matrix[0].size(); // 列数
        bool isZero[205][205] = {false}; // 判断原来矩阵中哪些是0

        for (int i = 0; i < m; ++i) 
            for (int j = 0; j < n; ++j) 
                if (matrix[i][j] == 0) isZero[i][j] = true;

        for (int i = 0; i < m; ++i) 
            for (int j = 0; j < n; ++j)
                if (isZero[i][j]) {
                    for (int p = 0; p < m; ++p) 
                        matrix[p][j] = 0;
                    for (int q = 0; q < n; ++q) 
                        matrix[i][q] = 0;
                }
    }
};

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<pair<int, int>> zero;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    zero.push_back({i, j});
                }
            }
        }
        for (auto& [x, y]: zero) {
            for (int i = 0; i < m; ++i) matrix[i][y] = 0;
            for (int j = 0; j < n; ++j) matrix[x][j] = 0;
        }
    }
};

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int flag_col0 = false, flag_row0 = false;
        for (int i = 0; i < m; i++) {
            if (!matrix[i][0]) {
                flag_col0 = true;
            }
        }
        for (int j = 0; j < n; j++) {
            if (!matrix[0][j]) {
                flag_row0 = true;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][j]) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][0] || !matrix[0][j]) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (flag_col0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (flag_row0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }
};

#include<bits/stdc++.h>
using namespace std;

vector<int> solve(vector<vector<int>> matrix) {
	vector<vector<int>> DIRS;
    DIRS.push_back({0, 1});
    DIRS.push_back({1, 0});
    DIRS.push_back({0, -1});
    DIRS.push_back({-1, 0});
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<bool>> vis(m, vector<bool>(n, false));
    int i = 0, j = 0, dir = 0;
    vector<int> res;
    // 数字个数
    int cnt = m * n;
    while (cnt--) {
        res.push_back(matrix[i][j]);
        vis[i][j] = true;
        int x = i + DIRS[dir][0];
        int y = j + DIRS[dir][1];
        // 如果该方向下一个点出界或者已经访问过，那么就变换方向
        if (x < 0 || x >= m || y < 0 || y >= n || vis[x][y]) {
            dir = (dir + 1) % 4;
        }
        i += DIRS[dir][0];
        j += DIRS[dir][1];
    }
    return res;
}

void print(vector<int> res) {
    for (auto x : res) cout << x << " ";
    cout << endl;
}

int main() {
    // test cases
    return 0;
}

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> tmp(n);
        for (int i = 0; i < n; ++i) {
            for (int j = n - 1; j >= 0; --j) {
                tmp[i].push_back(matrix[j][i]);
            }
        }
        matrix = tmp;
    }
};

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(matrix[i][j], matrix[n - i - 1][j]);
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();

        for (int i = 0; i < m; ++i) {
            // 剪枝
            if (target > matrix[i][n - 1]) continue;
            for (int j = 0; j < n; ++j) {
                if (target == matrix[i][j]) return true;
            }
        }
        return false;
    }
};

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int j = n - 1;

        for (int i = 0; i < m; ++i) {
            if (target > matrix[i][j]) continue;
            while (target < matrix[i][j] && j > 0) j--;
            if (matrix[i][j] == target) return true;
        }
        return false;
    }
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL) return NULL;
        ListNode *pa = headA, *pb = headB;
        while (pa != pb) {
            pa = pa == NULL ? headB : pa->next;
            pb = pb == NULL ? headA : pb->next;
        }
        return pa;
    }
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prev = nullptr;
        ListNode *curr = head;
        while (curr) {
            ListNode *next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        stack<int> st;
        ListNode* p = head;
        while (p != nullptr) {
            st.push(p->val);
            p = p->next;
        }
        ListNode* dummy = new ListNode();
        p = dummy;
        while (!st.empty()) {
            ListNode *temp = new ListNode(st.top());
            p->next = temp;
            p = p->next;
            st.pop();
        }
        return dummy->next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> f;
        ListNode* p = head;
        while (p) {
            f.push_back(p->val);
            p = p->next;
        }
        int n = f.size();
        for (int i = 0; i < n / 2; ++i) {
            if (f[i] != f[n-1-i]) {
                return false;
            }
        }
        return true;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    // 找链表的中间结点
    ListNode* midNode(ListNode* head) {
        ListNode* slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 反转链表
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr, *cur = head;
        while (cur) {
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }

public:
    bool isPalindrome(ListNode* head) {
        ListNode* mid = midNode(head);
        ListNode* head2 = reverseList(mid);
        while (head2) {
            if (head->val != head2->val) {
                return false;
            }
            head = head->next;
            head2 = head2->next;
        }    
        return true;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> st;
        ListNode* p = head;
        while (p) {
            if (!st.count(p)) st.insert(p);
            else return true;
            p = p->next;
        }
        return false;
    }
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) return false;
        // 快慢指针
        ListNode *fast, *slow;
        fast = slow = head;
        do {
            if (fast == nullptr || fast->next == nullptr) return false;
            fast = fast->next->next;
            slow = slow->next;
        } while (fast != slow);
        return true;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> st;
        ListNode* p = head;
        while (p) {
            if (st.count(p)) return p;
            else st.insert(p); 
            p = p->next;
        }
        return nullptr;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) return nullptr;
        ListNode *fast = head, *slow = head;
        do {
            if (fast == nullptr || fast->next == nullptr) return nullptr;
            fast = fast->next->next;
            slow = slow->next;
        } while (fast != slow);
        ListNode *p = head;
        while (p != slow) {
            p = p->next;
            slow = slow->next;
        }
        return p;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *p1 = list1, *p2 = list2;
        ListNode *dummy = new ListNode(), *p = dummy;
        while (p1 && p2) {
            if (p1->val < p2->val) {
                p->next = p1;
                p1 = p1->next;
            } else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        if (!p1) p->next = p2;
        else p->next = p1;
        return dummy->next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) {
            return list2;
        } else if (list2 == nullptr) {
            return list1;
        } else if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = nullptr, *tail = nullptr;
        int carry = 0; // 进位值
        while (l1 || l2) {
            int n1 = l1 ? l1->val : 0;
            int n2 = l2 ? l2->val : 0;
            int sum = n1 + n2 + carry;
            if (!head) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            carry = sum / 10;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        // 处理最末尾的数据，若大于10，则创建一个新节点
        if (carry > 0) tail->next = new ListNode(carry);
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int len = 0;
        ListNode *p = head;
        // 获取链表长度
        while (p != nullptr) {
            len++;
            p = p->next;
        }
        if (len == 1)
            return nullptr;
        if (len == n) {
            head = head->next;
            return head;
        }

        int cnt = 0;
        p = head;
        while (p != nullptr) {
            cnt++;
            if (cnt == len - n) {
                p->next = p->next->next;
                break;
            }
            p = p->next;
        }
        return head;
    }
};

class Solution {
public:
    int getLength(ListNode* head) {
        int length = 0;
        while (head) {
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 添加哑节点指向链表头节点
        ListNode* dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode* cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur->next;
        }
        cur->next = cur->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (!head->next) return nullptr;
        ListNode *dummy = new ListNode(0, head);
        ListNode *slow = dummy, *fast = head;
        while (n--) {
            fast = fast->next;
        }
        while (fast) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        // 注意此处不能直接返回head，因为有可能删除的就是head节点
        return dummy->next;
    }
};