void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[low];
    int i = low, j = high;
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        arr[i] = arr[j];
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = pivot;
    return i;
}

int main() {
    int arr[] = {3,6,8,2,4,1,9,5,7};
    int len = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, len - 1);
    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

#include <iostream>
#include <vector>

void heapSort(std::vector<int>& arr) {
    int n = arr.size();

    // build big heap
    for (int i = n/2 - 1; i >= 0; i--) {
        adjustDown(arr, i, n);
    }

    // sort from leaf
    for (int i = n - 1; i >= 0; i--) {
        std::swap(arr[0], arr[i]);
        adjustDown(arr, 0, n);
    }
}

void adjustDown(std::vector<int>& arr, int i, int n) {
    int temp = arr[i];

    for (int k = 2 * i + 1; k < n; k = 2 * k + 1) {
        // k是左节点，找左右较大的那个
        if (k + 1 < n && arr[k] < arr[k] + 1) {
            k++;
        }
        
        // 子节点大就交换
        if (arr[k] > temp) {
            arr[i] = arr[k];
            i = k;
        } else {
            break;
        }
    }

    arr[i] = temp;
}

int main() {
    std::vector<int> arr = {3,6,};
    heapSort(arr);
    for (int num:arr) std::cout<<num<<" ";
    return 0;
}

void mergeSort(std::vector<int>& arr, int l, int r) {
    if (l >= r) return ;
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
}

void merge(std::vector<int>& arr, int l, int m, int r) {
    std::vector<int> temp(r - l + 1);
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= m) {
        temp[k++] = arr[i++];
    }
    while (j <= r) {
        temp[k++] = arr[j++];
    }
    for (int p = 0; p < temp.size(); p++) {
        arr[l + p] = temp[p];
    }
}

int main() {
    std::vector<int> arr = {3, 6, 8, 2, 4, 1, 9, 5, 7};
    mergeSort(arr, 0, arr.size() - 1);
    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

/**
 * 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) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }

};

// 递归
ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode* new_head = reverseList(head->next);
    // 到最后，new_head是末尾节点，第一个head是倒数第二个
    head->next->next = head;
    head->next = nullptr;
    return new_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* reverseBetween(ListNode* head, int left, int right) {
        ListNode dummy(0, head);
        ListNode* p0 = &dummy;
        // p0挪到left-1
        for (int i = 0; i < left - 1; i++) {
            p0 = p0->next;
        }
        // 将以p0->next为头节点、到right的部分反转
        ListNode* pre = nullptr;
        ListNode* cur = p0->next;
        for (int i = 0; i < right - left + 1; i++) {
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        // 此时left处的节点指向nullptr，调整为right->next也就是cur
        p0->next->next = cur;
        // p0指向的是left，调整为right也就是pre
        p0->next = pre;
        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* reverseKGroup(ListNode* head, int k) {
        // 统计节点个数
        int n = 0;
        for (ListNode* cur = head; cur; cur = cur->next) {
            n++;
        }

        ListNode dummy(0, head);
        ListNode* p0 = &dummy;
        // 和92题一样，p0先放在left-1的位置
        ListNode* pre = nullptr;
        ListNode* cur = p0->next;

        for (; n >= k; n -= k) {
            for (int i = 0; i < k; i++) {
                // 反转
                ListNode* nxt = cur->next;
                cur->next = pre;
                pre = cur;
                cur = nxt;
            }
            // 这里不仅要使得k组的前后节点指针正确
            // 还要保证p0能够挪到下一个k组的之前一个节点
            // 而这个节点当前就是p0->next，因为反转了
            ListNode* next_p0 = p0->next;
            p0->next->next = cur;
            p0->next = pre;
            p0 = next_p0;
        } 
        return dummy.next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* a = headA;
        ListNode* b = headB;
        while (a != nullptr || b != nullptr) {
            if (a == nullptr) a = headB;
            if (b == nullptr) b = headA;
            if (a == b) return a;
            a = a->next;
            b = b->next;
        }
        return nullptr;
    }
};

/**
 * 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* getmid(ListNode* node) {
        ListNode* slow = node, *fast = node;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    bool isPalindrome(ListNode* head) {
        // 0/1个节点直接true
        if (!head || !head->next) return true;
        ListNode* mid = getmid(head);
        ListNode* new_head = mid->next;
        mid->next = nullptr;

        new_head = reverse(new_head);

        // 不用关奇数偶数，反转后从头往后比较，多的那个链表末尾的节点也不需要比较
        while (head && new_head) {
            if (head->val != new_head->val) return false;
            head = head->next;
            new_head = new_head->next;
        }
        return true;
    }
    ListNode* reverse(ListNode* node) {
        ListNode* prev = nullptr, *next = nullptr, *curr = node;
        while (curr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

/**
 * 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) {
        // 相对速度，fast每次比slow快一步，必定相遇
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

/**
 * 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) {
        // 相对速度，fast每次比slow快一步，必定相遇
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                // 让slow和head相遇
                while (slow != head) {
                    slow = slow->next;
                    head = head->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

/**
 * 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 dummy(0);
        ListNode* cur = &dummy;
        while (list1 && list2) {
            if (list1->val < list2->val) {
                cur->next = list1;
                list1 = list1->next;
            } else {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = (list1) ? list1 : list2;
        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* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](const ListNode* a, const ListNode* b) {
            return a->val > b->val; // 最小堆
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq;
        for (auto head : lists) {
            if (head) pq.push(head);
        }
        
        ListNode dummy(0);
        ListNode* cur = &dummy;
        while (!pq.empty()) {
            auto node = pq.top(); // 最小的节点
            pq.pop();
            cur->next = node;
            cur = cur->next;
            if (node->next) {
                pq.push(node->next);
            }
        }
        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:
    // 分治合并，将k个链表两两分割，再合并
    // 和归并排序思路一样，这里由于每个链表本身是有序的，可以看作是数组的一个元素
    // 所以流程实际上是一模一样的
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return mergeSort(lists, 0, lists.size());
    }

    // 合并2个有序链表
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* cur = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = (l1) ? l1 : l2;
        return dummy.next;
    }

    // 合并从i到j-1的链表
    ListNode* mergeSort(vector<ListNode*>& lists, int i, int j) {
        int m = j - i;
        if (m == 0) return nullptr;
        if (m == 1) return lists[i];
        auto left = mergeSort(lists, i, i + m/2);
        auto right = mergeSort(lists, i + m/2, j);
        return mergeTwoLists(left, right);
    }
};

/**
 * 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 dummy(0);
        ListNode* cur = &dummy;

        int enter = 0;

        while (l1 || l2 || enter) {
            int curr = enter;
            if (l1) {
                curr += l1->val;
                l1 = l1->next;
            }
            if (l2) {
                curr += l2->val;
                l2 = l2->next;
            }
            cur = cur->next = new ListNode(curr % 10);
            enter = curr / 10;
        }
        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* swapPairs(ListNode* head) {
        // 边界条件
        if (!head) return nullptr;
        if (head && !head->next) return head;
        // 和反转链表递归差不多，都是先递进到末尾
        ListNode* new_head = swapPairs(head->next->next);
        // 现在new_head和以后的已经交换完成了
        // 需要对当前的head和head->next进行交换
        // 然后返回的是head->next作为上一层的new_head
        ListNode* nxt = head->next;
        head->next = new_head;
        nxt->next = head;
        return nxt;
    }
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> mp;
        for (Node* p = head; p; p = p->next) {
            mp[p] = new Node(p->val);
        }
        for (Node* p = head; p; p = p->next) {
            mp[p]->next = mp[p->next];
            mp[p]->random = mp[p->random];
        }
        return mp[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* getmid(ListNode* node) {
        ListNode* slow = node, *fast = node;
        // 偏向左侧的中点
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    ListNode* merge(ListNode* l, ListNode* r) {
        ListNode dummy(-1);
        ListNode* curr = &dummy;
        while (l && r) {
            if (l->val < r->val) {
                curr->next = l;
                l = l->next;
            } else {
                curr->next = r;
                r = r->next;
            }
            curr = curr->next;
        }
        curr->next = (l)?l:r;
        return dummy.next;
    }

    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* mid = getmid(head);
        ListNode* new_head = mid->next;
        mid->next = nullptr;

        ListNode* l = sortList(head);
        ListNode* r = sortList(new_head);
        return merge(l, r);

    }
};

struct Node {
    int key;
    int val;
    Node* prev;
    Node* next;

    Node(int k = 0, int v = 0) : key(k), val(v) {};
};

class LRUCache {
public:
    int capacity;
    Node* dummy;
    unordered_map<int, Node*> key_to_node;

    void push_front(Node* x) {
        x->prev = dummy;
        x->next = dummy->next;
        x->prev->next = x;
        x->next->prev = x;
    }

    void remove(Node* x) {
        x->prev->next = x->next;
        x->next->prev = x->prev;
    }

    Node* get_node(int key) {
        auto it = key_to_node.find(key);
        if (it == key_to_node.end()) {
            return nullptr;
        }
        Node* node = it->second;
        remove(node);
        push_front(node);
        return node;
    }

    LRUCache(int capacity) : capacity(capacity) {
        dummy = new Node();
        dummy->prev = dummy;
        dummy->next = dummy;
    }
    
    int get(int key) {
        Node* node = get_node(key);
        if (node) {
            return node->val;
        } else {
            return -1;
        }
    }
    
    void put(int key, int value) {
        Node* node = get_node(key);
        if (node) {
            node->val = value;
            // push_front(node); 在get_node里面已经push了
        } else {
            node = new Node(key, value);
            key_to_node[key] = node;
            if (key_to_node.size() > capacity) {
                // 去掉最后一个节点
                Node* back = dummy->prev;
                key_to_node.erase(back->key);
                remove(back);
                delete back;
            }
            push_front(node);
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inorder_dfs(TreeNode* root, vector<int>& ans) {
        if (!root) return;
        if (root->left) inorder_dfs(root->left, ans);
        ans.push_back(root->val);
        if (root->right) inorder_dfs(root->right, ans);
    }

    void inorder_color(TreeNode* root, vector<int>& ans) {
        stack<pair<int, TreeNode*>> stk;
        stk.push(make_pair(0, root));
        while (!stk.empty()) {
            auto p = stk.top();
            stk.pop();
            auto color = p.first;
            auto node = p.second;

            if (node == nullptr) continue;
            if (color == 0) {
                stk.push(make_pair(0, node->right));
                stk.push(make_pair(1, node));
                stk.push(make_pair(0, node->left));
            } else {
                ans.push_back(node->val);
            }
        }
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        inorder_color(root, ans);
        return ans;
    }
};

void preorder_color(TreeNode* node, vector<int>& ans) {
    stack<pair<int, TreeNode*>> stk;
    stk.push(make_pair(0, node));
    while (!stk.empty()) {
        auto p = stk.top();
        stk.pop();
        auto color = p.first;
        auto node = p.second;

        if (node == nullptr) continue;
        if (color == 0) {
            stk.push(make_pair(0, node->right));
            stk.push(make_pair(0, node->left));
            stk.push(make_pair(1, node));
        } else {
            ans.push_back(node->val);
        }
    }
}

void inorder_color(TreeNode* node, vector<int>& ans) {
    stack<pair<int, TreeNode*>> stk;
    stk.push(make_pair(0, node));
    while (!stk.empty()) {
        auto p = stk.top();
        stk.pop();
        auto color = p.first;
        auto node = p.second;

        if (node == nullptr) continue;
        if (color == 0) {
            stk.push(make_pair(0, node->right));
            stk.push(make_pair(1, node));
            stk.push(make_pair(0, node->left));
        } else {
            ans.push_back(node->val);
        }
    }
}

void postorder_color(TreeNode* node, vector<int>& ans) {
    stack<pair<int, TreeNode*>> stk;
    stk.push(make_pair(0, node));
    while (!stk.empty()) {
        auto p = stk.top();
        stk.pop();
        auto color = p.first;
        auto node = p.second;

        if (node == nullptr) continue;
        if (color == 0) {
            stk.push(make_pair(1, node));
            stk.push(make_pair(0, node->right));
            stk.push(make_pair(0, node->left));
        } else {
            ans.push_back(node->val);
        }
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        if (root->left || root->right) {
            TreeNode* l = invertTree(root->left);
            TreeNode* r = invertTree(root->right);
            root->left = r;
            root->right = l;
        } 
        return root;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isMirrored(TreeNode* l, TreeNode* r) {
        if (l || r) {
            return l && r && (l->val == r->val) 
                    && isMirrored(l->left, r->right)
                    && isMirrored(l->right, r->left);
        } else {
            return true;
        }
    }
    bool isMirrored_iter(TreeNode* l, TreeNode* r) {
        stack<TreeNode*> stk;
        stk.push(l);
        stk.push(r);
        while (!stk.empty()) {
            l = stk.top(); stk.pop();
            r = stk.top(); stk.pop();
            if (!l && !r) continue;
            if ((!l || !r) || (l->val != r->val)) return false;

            stk.push(l->left);
            stk.push(r->right);
            stk.push(l->right);
            stk.push(r->left);
        }
        return true;
    }
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return isMirrored(root, root);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // int height(TreeNode* node) {
    //     if (!node) return 0;
    //     return max(height(node->left), height(node->right)) + 1; 
    // }
    int ans = 0;
    // 在求树的高度的递归过程中更新答案，O(n)
    int height(TreeNode* node) {
        if (!node) return 0;
        // 左右递归的值其实是线段的长度，就是length
        int l_len = height(node->left);
        int r_len = height(node->right);
        ans = max(ans, l_len + r_len); // l_len+r_len是一条直径
        return max(l_len, r_len) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        height(root);
        return ans;
    }

};