📕栈

1.有效的括号

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        map<char, char> mp;
        mp[')'] = '(';
        mp['}'] = '{';
        mp[']'] = '[';
        for(char x : s){
            if(x == '(' || x == '{' || x == '['){
                st.push(x);
            }else{
                if(!st.empty() && st.top() == mp[x]){
                    st.pop();
                }else{
                    return false;
                }
            }
        } 
        return st.empty();
    }
};

2.简化路径（🎈）

🎈法1:使用vector模拟

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> st;  // 用vector模拟栈来存储路径组件
        int i = 0;
        int n = path.size();
        
        // 遍历整个路径字符串
        while(i < n) {
            // 跳过连续的斜杠 '/'
            while(i < n && path[i] == '/') ++i;
            if(i == n) break;  // 如果已经到字符串末尾，退出循环
            
            // 找到下一个斜杠之前的内容
            int j = i;
            while(j < n && path[j] != '/') ++j;
            
            // 提取两个斜杠之间的字符串
            string str = path.substr(i, j - i);
            
            // 处理提取到的路径
            if(str != ".") { // 当前路径无需处理
                if(str == ".." && !st.empty()) 
                    st.pop_back();      // 遇到".."且栈不为空，返回上一级目录
                else if(str != "..") 
                    st.push_back(str);  // 普通目录名，入栈
            }
            
            i = j;  // 移动到下一个位置继续处理
        }
        
        // 构建结果字符串
        if(st.empty()) return "/";  // 如果栈为空，返回根目录
        
        string ans;
        for(string str: st) {
            ans = ans + ('/' + str);  // 在每个目录前添加斜杠
        }
        return ans;
    }
};

法2:vector

class Solution {
public:
    string simplifyPath(string path) {
        stack<string> st;
        int i = 0;
        int n = path.size();
        while(i < n){
            while(i < n && path[i] == '/') ++i;
            if(i == n) break;
            
            int j = i;
            while(j < n && path[j] != '/') ++j;
            string cur = path.substr(i, j - i);
            if(cur == ".."){
                if(!st.empty()){
                    st.pop();
                }
            }else if(cur != "."){
                st.push(cur);
            }

            i = j;
        }

        vector<string> vec;
        if(st.empty()) return "/";
        while(!st.empty()){
            vec.push_back(st.top());
            st.pop();
        }
        string ans = "";
        for(int i = vec.size() - 1; i >= 0; i--){
            ans = ans + ('/' + vec[i]);
        }
        return ans;

    }
};

3.最小栈(🍭)

法1:辅助栈
一个栈操作数，另一个保存最小值

/*
    时间复杂度： O(1)
    空间复杂度： O(n)
*/
class MinStack {
    stack<int> val_stack;
    stack<int> min_stack;

public:
    MinStack() {
        min_stack.push(INT_MAX);
    }
    
    void push(int val) {
        val_stack.push(val);
        min_stack.push(min(min_stack.top(), val));
    }
    
    void pop() {
        val_stack.pop();
        min_stack.pop();
    }
    
    int top() {
        return val_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

法2:栈+元祖（👍）
发现了一个更简洁的写法，虽然本质和法1是一样的

/*
    时间复杂度： O(1)
    空间复杂度： O(n)
*/
class MinStack {
    stack<pair<int, int>> st;

public:
    MinStack() {
        st.push({-1,INT_MAX});
    }
    
    void push(int val) {
        st.push({val, min(val, st.top().second)});
    }
    
    void pop() {
        st.pop();
    }
    
    int top() {
       return st.top().first;
    }
    
    int getMin() {
        return st.top().second;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

4.逆波兰表达式求值（🎈🎉）

法1:栈实现后缀表达式计算
主要就是从左到右遍历后缀表达式，遇到数就加入栈，遇到操作符就从栈中取出两个数字进行计算即可（需要注意取出来的数的运算顺序）

/*
    时间复杂度：O(n)
    空间复杂度：O(n)
*/
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        int n = tokens.size();
        for(int i = 0; i < n; i++){
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
                // 注意操作数顺序 是b op a先弹出来的是被操作数
                int b = st.top(); st.pop();
                int a = st.top(); st.pop(); 
                string op = tokens[i];
                int cur = 0;
                if(op == "+") cur = a + b;
                else if(op == "-") cur = a - b;
                else if(op == "*") cur = a * b;
                else cur = a / b;
                st.push(cur); 
            }else{
                // stoi：字符串转数字
                int num = stoi(tokens[i]);
                st.push(num);
            }
        }
        return st.top();
    }
};

法2:unorderedmap
看到一种更好维护的方法

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        unordered_map<string, function<int(int,int)>>map={
            {"+",[](int a,int b){return a + b;}},
            {"-",[](int a,int b){return a - b;}},
            {"*",[](int a,int b){return a*b;}},
            {"/",[](int a,int b){return a/b;}}
        };
        stack<int> st;
        for(string s : tokens){
            if(map.count(s)){
                int b = st.top(); st.pop();
                int a = st.top(); st.pop();
                st.push(map[s](a,b));
            }else{
                st.push(stoi(s));
            }
        }
        return st.top();
    }
};

5.基本计算器（💣❗️）

太难了qaq～
这个题只有加减法，其实就是去括号变号的过程，使用一个栈保存当前的符号

/*
    时间复杂度：O(n)
    空间复杂度：O(n)
*/
class Solution {
public:
    int calculate(string s) {
        stack<int> ops;
        ops.push(1);
        int sign = 1;
        int res = 0;
        int n = s.size();
        int i = 0;
        while(i < n){
            if(s[i] == ' '){
                i++;
            }else if(s[i] == '+'){
                sign = ops.top();
                i++;
            }else if(s[i] == '-'){
                sign = -ops.top();
                i++;
            }else if(s[i] == '('){
                ops.push(sign);
                i++;
            }else if(s[i] == ')'){
                ops.pop();
                i++;
            }else{
                long val = 0;
                while(i < n && s[i] >= '0' && s[i] <= '9'){
                    val = val * 10 + s[i] - '0';
                    i++;
                }
                res += sign*val;
            }
        }
        return res;
    }
};

📕链表

1.环形链表

法1:快慢指针法

/**
 * 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) {
        if(head == NULL || head->next==NULL) return false;
         ListNode *fast = head;
         ListNode *slow = head;
         while(fast->next !=NULL && fast->next->next != NULL){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) return true;
         }
         return false;
    }
};

2.两数相加

🚗法1:模拟
l1: 2 → 4 → 3 表示数字 342
l2: 5 → 6 → 4 表示数字 465
求它们的和（342 + 465 = 807），并以相同逆序返回：
输出: 7 → 0 → 8
链表的方向正好是低位到高位，因此可以从头开始一位一位加，非常方便。

🪜算法步骤
首先定义一个头节点head，存储结果
定义一个cur节点代表当前节点
carry代表当前进位
遍历l1和l2只要有有一个不为空或者进位不为空，就继续
计算当前位的和：sum = l1.val + l2.val + carry
更新进位：carry = sum / 10
当前位结果：sum % 10，用这个数创建新节点加入结果链表。
！！！如果最后 carry > 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) {}
 * };
 */

 /*
    时间复杂度：O(max(m, n))
    空间复杂度：O(max(m, n))
    在平时竖式计算的过程中，就是从低位到高位，这里链表存的每个数也是逆序存放的，所以直接遍历链表模拟竖式计算即可
    1.首先，定义一个head虚拟节点，方便返回答案
    2.定义cur代表当前操作的节点，carry代表当前进位
    3.通过 sum = l1.val+l2.val carry计算当前数位的和。 更新进位为sum/10 当前位数字为sum%10
    只要l1或者l2不是空的，或者进位数不为0，都需要存储这一位的答案
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* cur = head;
        
        int carry = 0;

        while(l1 != NULL || l2 != NULL || carry != 0){
            int x = (l1 != NULL) ? l1->val : 0;
            int y = (l2 != NULL) ? l2->val : 0;
            int sum = x + y + carry;
            carry = sum / 10;
            int digit = sum % 10;
            
            cur->next = new ListNode(digit);
            cur = cur->next;

            if(l1) l1 = l1->next;
            if(l2) l2 = l2->next;
        }
        return head->next;

    }
};

3.合并两个有序链表

法1：归并排序的思想

/**
 * 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* l1, ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* cur = head;
        while(l1 != NULL && l2 != NULL){
            int x = l1->val;
            int y = l2->val;
            if(x <= y){
                cur->next = new ListNode(x);
                cur = cur->next;
                l1 = l1->next;
            }else{
                cur->next = new ListNode(y);
                cur = cur->next;
                l2 = l2->next;
            }
        } 
        while(l1 != NULL){
            int x = l1->val;
            cur->next = new ListNode(x);
            cur = cur->next;
            l1 = l1 ->next;
        }
        while(l2 != NULL){
            int y = l2->val;
            cur->next = new ListNode(y);
            cur = cur->next;
            l2 = l2->next;
        }
        return head->next;
    }
};

法2：递归大法

/**
 * 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) {}
 * };
 */

 /*
    递归
    太妙了
    递归方法：判断l1和l2那个节点更小，然后将较小的节点next指针指向其余节点的合并结果（调用递归）
    递归出口：当两个链表都为空时，即合并完成
    时间复杂度：O(m+n)
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) return l2;
        if (l2 == NULL) return l1;
        if(l1->val <= l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;  //返回我这一层的工作
        }else{
            l2->next = mergeTwoLists(l2->next, l1);
            return l2;
        }
    }
};

一些递归题目

反转字符串

/*
    344.反转字符串
    编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
    不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
    解法：每次交换首尾进行递归
*/

class Solution {
public:
    void dfs(vector<char>& s,int l,int r){
        if(l >= r) return;
        char t = s[l];
        s[l] = s[r];
        s[r] = t;
        dfs(s, l+1,r-1);
    }
    void reverseString(vector<char>& s) {
       dfs(s,0,s.size()-1); 
    }
};

汉诺塔

/*
    在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。
*/
class Solution {
public:
    void move(int n, vector<int>& A, vector<int>& B, vector<int>& C){
        if(n == 1){
            C.push_back(A.back());
            A.pop_back();
            return;
        }
        move(n-1,A,C,B); // 将A上面n-1个通过C移到B
        C.push_back(A.back());
        A.pop_back();
        move(n-1,B,A,C);
    }
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        int n = A.size();
        move(n,A,B,C);
        
    }
};

两两交换链表中的节点

/**
 * 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 == nullptr || head->next == nullptr) return head;
        ListNode* one = head;
        ListNode* two = one->next;
        ListNode* three = two->next;

        // 交换
        two->next = one;
        one->next = swapPairs(three); // 递归交换后续部分

        return two;
    }
};

二叉树的最大深度
这个后面再写

4.随机链表的复制（🍭💣链表+哈希）

刚开始题都没看懂，看了题解才知道，非常🐱
法1:哈希表
因为每个节点除了 next 之外还有一个可以指向任意节点（或空）的 random 指针，不能只按顺序一边遍历一边连 random，否则random 指向的那个节点可能还没被新建，使用哈希表解决这个问题：
1.先把“所有旧节点 → 对应新节点”的映射建好（仅拷贝数值，不连指针）。
2.利用这个映射，把每个新节点的 next 和 random 指针写上

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

/*
    哈希表
    时间复杂度 O(N)，遍历链表
    空间复杂度 O(N)，哈希表
    这道题的难点在于和普通的链表不同，多了个random，所以遍历复制无法构建random
    利用哈希表，构建原链表节点和新链表节点对应的键值对映射关系，再遍历构建next和random即可

*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        Node* cur = head;
        unordered_map<Node*, Node*> map;
        // 复制节点，构建映射关系
        while(cur != nullptr){
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;

        while(cur != nullptr){
        		 // 有点绕
        		 // map[A] = A'
        		 // A'->next = map[B] = B'
            map[cur]->next = map[cur->next]; 
            map[cur]->random = map[cur->random];
            cur = cur->next;
            
        }

        return map[head];
    }
};

法2:拓展：O(1) 额外空间的“穿插法”
太难了

/*
// 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) {
        if(head == nullptr) return nullptr;

        Node* cur = head;

        // 复制节点并插入到原节点后
        while(cur != nullptr){
            Node* t = new Node(cur->val);
            t->next = cur->next;
            cur->next = t;
            cur = t->next;
        }

        // 复制random指针
        cur = head;
        while(cur != nullptr){
            if(cur->random != nullptr){
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }

        // 拆分链表
        cur = head;
        Node* newHead = head->next;
        Node* t = newHead;
        while(cur != nullptr){
            cur->next = t->next;
            cur = cur->next;
            if(cur != nullptr){
                t->next = cur->next;
                t = t->next;
            }
        }
        return newHead;
    }
};

5.反转链表II（！）

/**
 * 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:
    void reverseLinkedList(ListNode* head){
        ListNode* pre = nullptr;
        ListNode *cur = head;

        while(cur != nullptr){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
    }
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // 虚拟头节点
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* pre = dummy;
        // 先找到left前面的一个节点
        for(int i = 0; i < left - 1; i++){
            pre = pre->next;
        }
        // 在找到right 节点
        ListNode* rNode = pre;
        for(int i = 0; i < right - left + 1; i++){
            rNode = rNode->next;
        }
        // 截取子链表
        ListNode* lNode = pre->next;
        ListNode* cur = rNode->next;

        pre->next = nullptr;
        rNode->next = nullptr;

        reverseLinkedList(lNode);
        
        pre->next = rNode;
        lNode->next = cur;
        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) {}
 * };
 */

 /*
    给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
    思路：本质就是改变链表的指向
    就是要把本来指向next的指向pre,所以需要存一下next和pre，否则next就被覆盖了，或者找不到pre
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur != nullptr){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;

    }
};

6.k个一组翻转链表

/**
 * 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) {}
 * };
 */
 /*
    时间复杂度：O(N)
    空间复杂度：O(N)
 */
class Solution {
public:
    //翻转子链表
    pair<ListNode*, ListNode*> Reverse(ListNode* head, ListNode* tail){
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* end = tail->next; 
        while(cur != end){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return {tail, head};
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 虚拟节点
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;

        while(head){
            ListNode* last = pre;
            // 不足k个不用反转
            for(int i = 0; i < k; i++){
                last = last->next;
                if(last==nullptr){
                    return dummy->next;
                }
            }
            ListNode* next = last->next;

            pair<ListNode*, ListNode*> res = Reverse(head, last);
            head = res.first;
            last = res.second;

            pre->next = head;
            last->next = next;
            pre = last;
            head = last->next;
        }
        return dummy->next;
    }
};

7.删除链表的倒数第N个结点

法1：快慢指针法

/**
 * 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) {}
 * };
 */
 /*
    快慢指针：先让快指针走n步，再让快慢指针一起走，直到快指针到尾，慢指针就会到达第倒数第n个，
    但是为了需要修改我们需要找到第n-1个，可以所以让慢指针从虚拟节点开始走
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* fast = head;
        ListNode* slow = dummy; //为了找到第n-1个
        // n = n + 1;
        while(n--){
            fast = fast->next;
        }
        while(fast != nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        ListNode*pre = slow;
        pre->next = slow->next->next;
        // return pre;
        return dummy->next;
        
    }
};

8 删除排序链表的重复元素II

/**
 * 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* deleteDuplicates(ListNode* head) {
        if(head == nullptr) return head;

        ListNode* dummy = new ListNode(0);
        dummy->next = head;

        ListNode* cur = dummy;
        // 判断是否为空节点
        while(cur->next && cur->next->next){
            if(cur->next->val == cur->next->next->val){
                int val = cur->next->val;
                while(cur->next && cur->next->val == val){
                    cur->next = cur->next->next;
                }
            }else{
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};

9. 旋转链表

/**
 * 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) {}
 * };
 */
/*

把倒数k个拿到前面不就好了（k好像要对链长取模）
首先找到倒数第k个数：快慢指针
*/
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head == nullptr || head->next==nullptr) return head;

        ListNode* fast = head;
        ListNode* slow = head;
        int ct = 0;
        while(fast){
            ct++;
            fast = fast->next;
        }
        k = k % ct;
        fast = head;
        // 快指针先走k步
        while(k--){
            fast = fast->next;
        }
        // 快指针走到尾，慢指针即到了倒数第k个
        while(fast->next){
            fast = fast->next;
            slow = slow->next;
        }
        fast->next = head; //拿到前面
        ListNode* t = slow->next;
        slow->next=nullptr;
        return t;
    }
};

10.分隔链表

/**
 * 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) {}
 * };
 */
/*
    注意：保留 两个分区中每个节点的初始相对位置
    其实就是一个链表存小于x的节点，一个存大于等于x的节点，
    最后把小于x节点的尾节点的next设为大于等于x链表即可
*/


class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* dummyl = new ListNode(-1);
        ListNode* headl = dummyl;
        dummyl->next = headl;
        ListNode* dummym = new ListNode(-1);
        ListNode* headm = dummym;
        dummym->next = headm;
        while(head){
            int val = head->val;
            if(val < x){
                headl->next = head;
                headl=headl->next;
            }else{
                headm->next = head;
                headm = headm->next;
            }
            head = head->next;
        }
        headm->next = nullptr;
        headl->next = dummym->next;
        return dummyl->next;
    }
};

11.LRU缓存（💣 🎉🏁哈希表+双向链表）

struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;

public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (!cache.count(key)) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode* node = new DLinkedNode(key, value);
            // 添加进哈希表
            cache[key] = node;
            // 添加至双向链表的头部
            addToHead(node);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode* removed = removeTail();
                // 删除哈希表中对应的项
                cache.erase(removed->key);
                // 防止内存泄漏
                delete removed;
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

    DLinkedNode* removeTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};