链表类问题技巧：
【1】虚拟头节点dummyNode 的创建 往往都是为了能够方面操作 头节点 而来的;
【2】双指针 在多个情境下的使用;

一级类目	二级类型/题目	三级类目/题目
单链表	链表中的加法	2. 两数相加
		面试题 02.05. 链表求和
		445. 两数相加 II
	反转链表	206. 反转链表
		92. 反转链表 II
		剑指 Offer 06. 从尾到头打印链表
		143. 重排链表
		25. K 个一组翻转链表	高频
		234. 回文链表
	链表相交	160. 相交链表
	环形链表	141. 环形链表	重点
		142. 环形链表 II	重点
	倒数第K个节点	剑指 Offer 22. 链表中倒数第k个节点
	删除链表节点	237. 删除链表中的节点
		19. 删除链表的倒数第 N 个结点	高频
		83. 删除排序链表中的重复元素
		82. 删除排序链表中的重复元素 II	重点
		面试题 02.01. 移除重复节点
		203. 移除链表元素
	排序链表	147. 对链表进行插入排序
		148. 排序链表
	合并链表	剑指 Offer 25. 合并两个排序的链表
		21. 合并两个有序链表
		1669. 合并两个链表
		23. 合并K个升序链表	高频
双向链表		面试题 16.25. LRU 缓存
		460. LFU 缓存

单链表

链表中的加法

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) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head=nullptr,*tail=nullptr;
        int first=0,second=0;
        int carry=0;
        while(l1||l2){
            first=l1?l1->val:0;
            second=l2?l2->val:0;
            int sum=first+second+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;
        }
        if(carry){tail->next=new ListNode(carry);}
        return head;
    }
};

面试题 02.05. 链表求和

代码和上题一样

445. 两数相加 II

思路

先分别反转，相加，然后再反转输出;

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
  ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
      ListNode *ll1 = reverse(l1);
      ListNode *ll2 = reverse(l2);
      int sum = 0, carry = 0;
      ListNode *head = nullptr, *tail = nullptr;
      while (ll1 || ll2) {
          int left = ll1 ? ll1->val : 0;
          int right = ll2 ? ll2->val : 0;
          sum = left + right + carry;
          if (!head) {
              head = tail = new ListNode(sum % 10);
          } else {
              tail->next = new ListNode(sum % 10);
              tail = tail->next;
          }
          carry = sum / 10;
          if (ll1)ll1 = ll1->next;
          if (ll2)ll2 = ll2->next;
      }
      if (carry) {
          tail->next = new ListNode(carry);
      }
      return reverse(head);
  }
  ListNode *reverse(ListNode *l) {
      if (l == nullptr || l->next == nullptr) {
          return l;
      }
      // 1->2->3
      ListNode *prev = nullptr, *next = l;
      while (l) {
          next = l->next;
          l->next = prev;
          prev = l;
          l = next;
      }
      return prev;
  }
};

反转链表

206. 反转链表

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

92. 反转链表 II

这道很经典。（涉及链表的操作多，慢点做）

class Solution {
public:
  ListNode *reverse(ListNode *head) {
      if (head == nullptr) {
          return head;
      }
      ListNode *prev = nullptr, *next = nullptr;
      while (head != nullptr) {
          next = head->next;
          head->next = prev;
          prev = head;
          head = next;
      }
      return prev;
  }
  /**
   * 1->2->3->4->5
   *    [2,4]
   * 1->4->3->2->5
   * @param head
   * @param left
   * @param right
   * @return
   */
  ListNode *reverseBetween(ListNode *head, int left, int right) {
      ListNode *dummyNode = new ListNode(-1);
      dummyNode->next = head;
      ListNode *prev = dummyNode;
      for (int i = 0; i < left - 1; i++) {//left=2,left-1=1,
          prev = prev->next; // dummyNode 不变，prev 向后移动,移动left-1 步，到 left 前一个节点位置，即此时prev在1位置;
      }
      ListNode *rightNode = prev;
      for (int i = 0; i < right - left + 1; i++) {//right-left+1=3,rightNode从1开始移动三步，到4位置;
          rightNode = rightNode->next;
      }
      // 第三步： 切割子链表出来
      ListNode *leftNode = prev->next;// leftNode指向2,即目标片段的开始节点;
      ListNode *curr = rightNode->next;// 保存4 之后的链表片段;
      //切断链接
      prev->next = nullptr;// 1->nullptr
      rightNode->next = nullptr;//4->nullptr,此时产生了三个片段
      //反转2->3->4 成为 4->3->2
      reverse(leftNode);
      //接回原链表
      prev->next = rightNode;
      leftNode->next = curr;
      return dummyNode->next;
  }
};

剑指 Offer 06. 从尾到头打印链表

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
  vector<int> res;
  vector<int> reversePrint(ListNode *head) {
      while (head != nullptr) {
          res.push_back(head->val);
          head = head->next;
      }
      reverse(res.begin(), res.end());
      return res;
  }
};

143. 重排链表

方法一:

/**
* 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 reorderList(ListNode *head) {
      if (head == nullptr) {
          return;
      }
      vector<ListNode *> res;
      ListNode *node = head;
      while (node != nullptr) {
          res.emplace_back(node);
          node = node->next;
      }
      int i = 0, j = res.size() - 1;
      while (i < j) {
          res[i]->next = res[j];
          i++;
          if (i == j) { break; }
          res[j]->next = res[i];
          j--;
      }
      res[i]->next = nullptr;
  }
};

方法二：

class Solution {
public:
  ListNode *middleNode(ListNode *head) {
      ListNode *slow = head;
      ListNode *fast = head;
      while (fast->next != nullptr && fast->next->next != nullptr) {
          fast = fast->next->next;
          slow = slow->next;
      }
      return slow;
  }
  ListNode *reverse(ListNode *head) {
      if (head == nullptr) { return head; }
      ListNode *prev = nullptr, *next = nullptr;
      while (head) {
          next = head->next;
          head->next = prev;
          prev = head;
          head = next;
      }
      return prev;
  }
  //合并两个链表
  void mergeList(ListNode *l1, ListNode *l2) {
      ListNode *left=nullptr, *right=nullptr;
      while (l1 && l2) {
          left = l1->next;
          right = l2->next;
          l1->next = l2;
          l1 = left;
          l2->next = l1;
          l2 = right;
      }
  }
  void reorderList(ListNode *head) {
      if (head == nullptr) { return; }
      ListNode *mid = middleNode(head);
      ListNode *l1 = head;
      ListNode *l2 = mid->next;
      mid->next = nullptr;
      l2 = reverse(l2);
      mergeList(l1, l2);
  }
};

25. K 个一组翻转链表

class Solution {
public:
  /**
   * 不是很好理解; 要修改成自己的方式
   * @param head
   * @param tail
   * @return
   */
  pair<ListNode *, ListNode *> reverse(ListNode *head, ListNode *tail) {
      ListNode *prev = tail->next;
      ListNode *p = head;
      while (prev != tail) {
          ListNode *nex = p->next;
          p->next = prev;
          prev = p;
          p = nex;
      }
      return {tail, head};
  }
  ListNode *reverseKGroup(ListNode *head, int k) {
      //构建虚拟头结点
      ListNode *dummyNode = new ListNode(-1);
      dummyNode->next = head;
      ListNode *pre = dummyNode;
      while (head) {
          ListNode *tail = pre;
          // 每 k 个处理
          for (int i = 0; i < k; i++) {
              tail = tail->next;
              if (!tail) {
                  return dummyNode->next;
              }
          }
          ListNode *nex = tail->next;
          pair<ListNode *, ListNode *> result = reverse(head, tail);
          head = result.first;
          tail = result.second;
          //把子链表 链接回 原链表中;
          pre->next = head;
          tail->next = nex;
          //
          pre = tail;
          head = tail->next;
      }
      return dummyNode->next;
  }
};

234. 回文链表

方法一：

class Solution {
public:
     bool isPalindrome(ListNode *head) {
        vector<int> res;
        while (head) {
            res.emplace_back(head->val);
            head = head->next;
        }
        for (int i = 0; i < res.size() / 2; i++) {
            if (res[i] != res[res.size() - 1 - i]) {
                return false;
            }
        }
        return true;
    }
};

方法二:

    bool isPalindrome(ListNode *head) {
        if (!head || !head->next) {
            return true;
        }
        int size = 0;
        ListNode *p1 = head;
        while (p1) {
            size += 1;
            p1 = p1->next;
        }
        int mid = size >> 1;
        ListNode *p2 = head;
        while (mid > 0) {
            p2 = p2->next;
            mid--;
        }
        ListNode *prev = nullptr, *now = p2, *next = nullptr;
        while (now) {
            next = now->next;
            now->next = prev;
            prev = now;
            now = next;
        }
        int step = 0;
        while (step < (size >> 1)) {
            if (head->val != prev->val) {
                return false;
            }
            head = head->next;
            prev = prev->next;
            step += 1;
        }
        return true;
    }

链表相交

160. 相交链表

class Solution {
public:
    int getListLength(ListNode *head) {
        ListNode *tmp = head;
        int count = 0;
        while (tmp) {
            count += 1;
            tmp = tmp->next;
        }
        return count;
    }
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int len_a = getListLength(headA);
        int len_b = getListLength(headB);
        int dis = abs(len_a - len_b);
        if (len_a > len_b) {
            for (int i = 0; i < dis; i++) {
                headA = headA->next;
            }
        } else {
            for (int i = 0; i < dis; i++) {
                headB = headB->next;
            }
        }
        while (headA != nullptr && headB != nullptr) {
            if (headA == headB) {
                return headA;
            }
            headA = headA->next;
            headB = headB->next;
        }
        return nullptr;
    }
};

环形链表

141. 环形链表

//快慢指针，一个走一步，一个走两步，如果有环，那么必然相遇
//如果没还，在两指针走到头停止。
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr) {
            return false;
        }
        ListNode *res = head;
        while (head && res && res->next) {
            head = head->next;
            res = res->next->next;
            if (head == res) {
                return true;
            }
        }
        return false;
    }
};

142. 环形链表 II

题解

/**
 * 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) {
            return nullptr;
        }
        ListNode *slow = head, *fast = head;
        while (fast) {
            slow = slow->next;
            if(!fast->next){
                return nullptr;
            }
            fast = fast->next->next;
            if (fast == slow) {
                ListNode *res = head;
                while (res != slow) {
                    res = res->next;
                    slow = slow->next;
                }
                return res;
            }
        }
        return nullptr;
    }
};

倒数第K个节点

剑指 Offer 22. 链表中倒数第k个节点

class Solution {
public:
    ListNode *getKthFromEnd(ListNode *head, int k) {
        if (!head) {
            return head;
        }
        ListNode *fast = head;
        for (int i = 0; i < k; i++) {
            fast = fast->next;
        }
        while (fast) {
            fast = fast->next;
            head = head->next;
        }
        return head;
    }
};

删除链表节点

237. 删除链表中的节点

class Solution {
public:
    void deleteNode(ListNode *node) {
        //将node 的值 赋值为 node->next的值
        //将node ->next 跳过下一个指向 下下一个;
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

剑指 Offer 18. 删除链表的节点

class Solution {
public:
    ListNode *deleteNode(ListNode *head, int val) {
        if (!head) {
            return head;
        }
        ListNode *dummyHead = new ListNode(-1);
        dummyHead->next = head;
        ListNode *calc = dummyHead;
        while (calc->next) {
            if (calc->next->val == val) {
                if (calc->next) {
                    ListNode *node = calc->next;
                    calc->next = node->next;
                    node->next = nullptr;
                    return dummyHead->next;
                }
            }
            calc = calc->next;
        }
        return dummyHead->next;
    }
};

class Solution {
public:
      ListNode *deleteNode(ListNode *head, int val) {
        if (!head) {
            return head;
        }
        ListNode *dummyHead = new ListNode(-1);
        dummyHead->next = head;
        ListNode *calc = dummyHead;
        while (calc&&calc->next) {
            if (calc->next->val == val) {
                if (calc->next) {
                    ListNode *node = calc->next;
                    calc->next = node->next;
                    node->next = nullptr;
                    //return dummyHead->next;
                }
            }
            calc = calc->next;
        }
        return dummyHead->next;
    }
};

对比下上面两个代码的差异点;

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

    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode *a = dummyNode;
        ListNode *b = dummyNode;
        for (int i = 0; i < n; i++) {
            b = b->next;
        }
        while (b->next) {
            a = a->next;
            b = b->next;
        }
        a->next = a->next->next;
        return dummyNode->next;
    }

83. 删除排序链表中的重复元素

class Solution {
public:
    //删除重复元素
    // 1->1->2->2->2->3
    ListNode *deleteDuplicates(ListNode *head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode *res = head;
        while (res->next) {
            if (res->val == res->next->val) {
                res->next = res->next->next;
            } else {
                res = res->next;
            }
        }
        return head;
    }
};

82. 删除排序链表中的重复元素 II

    ListNode *deleteDuplicates(ListNode *head) {
        if (!head) {
            return head;
        }
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode *pre = dummyNode, *post = dummyNode->next;
        while (post) {
            if (post->next && post->val == post->next->val) {
                while (post->next && post->val == post->next->val) {
                    post = post->next;
                }
                pre->next = post->next;
                post = post->next;
            } else {
                pre = pre->next;
                post = post->next;
            }
        }
        return dummyNode->next;
    }

面试题 02.01. 移除重复节点

class Solution {
public:
   ListNode *removeDuplicateNodes(ListNode *head) {
        if (!head) {
            return head;
        }
        unordered_set<int> bucket;
        ListNode *pos = head;
        bucket.insert(head->val);
        while (pos->next) { // ->next的巧妙
            ListNode *cur = pos->next;
            if (!bucket.count(cur->val)) {
                bucket.insert(cur->val);
                pos = pos->next;
            } else {
                pos->next = pos->next->next;
            }
        }
        pos->next = nullptr;
        return head;
    }
};

203. 移除链表元素

class Solution {
public:
     ListNode *removeElements(ListNode *head, int val) {
        if (!head) {
            return head;
        }
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode *res = dummyNode;
        while (res->next) {
            if (res->next->val == val) {
                res->next = res->next->next;
            } else {
                res = res->next;
            }
        }
        return dummyNode->next;
    }
};

排序列表

147. 对链表进行插入排序

/**
 * 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 *insertionSortList(ListNode *head) {
        if (!head) {
            return head;
        }
        //-1---->4---->2---->1------>3
        //du    last  cur
        //-1---->2---->4---->1------>3
        //du         last   cur
        //-1---->2---->4---->1------>3
        //du         last   cur
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode *lastSorted = head, *cur = head->next;
        while (cur) {
            if (lastSorted->val <= cur->val) {
                lastSorted = lastSorted->next;
            } else {
                ListNode *prev = dummyNode;
                //使用prev指针 在last左侧 将所有比cur小的数 中给cur找合适的位置
                //[1]如果没有说明cur要被放到 链表头部了，因为他最小;
                while (prev->next->val <= cur->val) {
                    prev = prev->next;
                }
                lastSorted->next = cur->next;
                cur->next = prev->next;
                prev->next = cur;
            }
            cur = lastSorted->next;
        }
        return dummyNode->next;
    }
};

148. 排序链表

与上题解法一样
思考，如何获取降序的列表;

/**
 * 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* sortList(ListNode* head) {
        if (!head) {
            return head;
        }
        //-1---->4---->2---->1------>3
        //du    last  cur
        //-1---->2---->4---->1------>3
        //du         last   cur
        //-1---->2---->4---->1------>3
        //du         last   cur
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode *lastSorted = head, *cur = head->next;
        while (cur) {
            if (lastSorted->val <= cur->val) {
                lastSorted = lastSorted->next;
            } else {
                ListNode *prev = dummyNode;
                //使用prev指针 在last左侧 将所有比cur小的数 中给cur找合适的位置
                //[1]如果没有说明cur要被放到 链表头部了，因为他最小;
                while (prev->next->val <= cur->val) {
                    prev = prev->next;
                }
                lastSorted->next = cur->next;
                cur->next = prev->next;
                prev->next = cur;
            }
            cur = lastSorted->next;
        }
         return dummyNode->next;
    }
};

合并链表

剑指 Offer 25. 合并两个排序的链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
       ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if (!l1)return l2;
        if (!l2)return l1;
        ListNode *dummyNode = new ListNode(-1);
        ListNode *res = dummyNode;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                res->next = l1;
                l1 = l1->next;
            } else {
                res->next = l2;
                l2 = l2->next;
            }
            res = res->next;
        }
        while (l1) {
            res->next = l1;
            l1 = l1->next;
            res = res->next;
        }
        while (l2) {
            res->next = l2;
            l2 = l2->next;
            res = res->next;
        }
        return dummyNode->next;
    }
};

21. 合并两个有序链表

与上面一样;

    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if (!l1)return l2;
        if (!l2)return l1;
        ListNode *dummyNode = new ListNode(-1);
        ListNode *res = dummyNode;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                res->next = l1;
                l1 = l1->next;
            } else {
                res->next = l2;
                l2 = l2->next;
            }
            res = res->next;
        }
        while (l1) {
            res->next = l1;
            res = res->next;
            l1 = l1->next;
        }
        while (l2) {
            res->next = l2;
            res = res->next;
            l2 = l2->next;
        }
        return dummyNode->next;
    }

1669. 合并两个链表

    ListNode *mergeInBetween(ListNode *list1, int a, int b, ListNode *list2) {
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = list1;
        ListNode *head = dummyNode;
        ListNode *left = nullptr, *right = nullptr;
        while (a) {
            a--;
            b--;
            head = head->next;
        }
        left = head;
        while (b) {
            b--;
            head = head->next;
        }
        right = head->next;
        left->next = list2;
        while (list2->next) {
            list2 = list2->next;
        }
        list2->next = right;
        return dummyNode->next;
    }

23. 合并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) {}
 * };
 */
class Solution {
public:
       ListNode *mergeTwoList(ListNode *l1, ListNode *l2) {
        if (!l1)return l2;
        if (!l2)return l1;
        ListNode *dummyNode = new ListNode(-1);
        ListNode *res = dummyNode;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                res->next = l1;
                l1 = l1->next;
            } else {
                res->next = l2;
                l2 = l2->next;
            }
            res = res->next;
        }
        res->next = l1 ? l1 : l2;
        return dummyNode->next;
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *res = nullptr;
        for (int i = 0; i < lists.size(); i++) {
            res = mergeTwoList(res, lists[i]);
        }
        return res;
    }
};

解法二：归并合并

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if (!l1)return l2;
        if (!l2)return l1;
        ListNode *dummyNode = new ListNode(-1);
        ListNode *res = dummyNode;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                res->next = l1;
                l1 = l1->next;
            } else {
                res->next = l2;
                l2 = l2->next;
            }
            res = res->next;
        }
        res->next = l1 ? l1 : l2;
        return dummyNode->next;
    }
    ListNode *merge(vector<ListNode *> &lists, int l, int r) {
        if (l == r)return lists[l];
        if (l > r)return nullptr;
        int mid = l + ((r - l) >> 1);
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

双链表

面试题 16.25. LRU 缓存

最近最少使用，
基于访问时间，在被访问过的元素中去除最久未使用的元素，
保证热点数据的有效性
双链表 
head 一直是最近被使用过的
tail 代表最长未被使用的
超过阈值直接删除尾部节点

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;
        }
        DLinkedNode *node = cache[key];
        moveToHead(node);
        return node->value;
    }
    void put(int key, int value) {
        if (!cache.count(key)) {
            DLinkedNode *node = new DLinkedNode(key, value);
            cache[key] = node;
            addToHead(node);
            ++size;
            if (size > capacity) {
                DLinkedNode *tail = removeTail();
                cache.erase(tail->key);
                delete tail;
                size--;
            }
        } else {
            DLinkedNode *node = cache[key];
            node->value = value;
            // 将这个节点移动到头部位置;
            moveToHead(node);
        }
    }
    //移动到头部
    //1.先移除这个节点
    //2.在头部添加
    //时间复杂度O(1),空间复杂度O(1)
    void moveToHead(DLinkedNode *node) {
        removeNode(node);
        addToHead(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;
    }
    //移除尾部节点 并返回节点
    DLinkedNode *removeTail() {
        DLinkedNode *node = tail->prev;
        removeNode(node);
        return node;
    }
};

460. LFU 缓存


LFU最近最不常用，基于访问次数，去除命中次数最少的元素，保证高频数据有效性
struct Node {
    int cnt, time, key, value;
    Node() {}
    Node(int _cnt, int _time, int _key, int _value) : cnt(_cnt), time(_time), key(_key), value(_value) {}
    bool operator<(const Node &ht) const {
        return cnt == ht.cnt ? time < ht.time : cnt < ht.cnt;
    }
};
class LFUCache {
    int capacity; //缓存容量
    int time;//最新的时间点（用int大小代替）,全局
    unordered_map<int, Node> key_table;
    set<Node> sortTree;//用于做结构体内部自动排序
public:
    LFUCache(int _capacity) {
        this->capacity = _capacity;
        time = 0;
        key_table.clear();
        sortTree.clear();
    }
    int get(int key) {
        if (capacity == 0) return -1;
        auto it = key_table.find(key);
        if (it == key_table.end()) {
            return -1;
        }
        Node cache = it->second;
        sortTree.erase(cache);
        cache.cnt += 1;
        cache.time = ++time;
        sortTree.insert(cache);
        key_table[key] = cache;
        return cache.value;
    }
    void put(int key, int value) {
        if (capacity == 0)return;
        auto it = key_table.find(key);
        if (it == key_table.end()) {
            //达到容量阈值
            if (key_table.size() == capacity) {
                auto first = sortTree.begin();
                key_table.erase(first->key);
                sortTree.erase(first);
            }
            //如果没有到阈值，构建新缓存
            Node cache = Node(1, ++time, key, value);
            key_table.insert({key, cache});
            sortTree.insert(cache);
        } else {
            Node cache = it->second;
            sortTree.erase(cache);
            cache.cnt += 1;
            cache.time = ++time;
            cache.value = value;
            sortTree.insert(cache);
            key_table[key] = cache;
        }
    }
};

3.链表

单链表

链表中的加法

反转链表

方法一：

方法二:

链表相交

环形链表

倒数第K个节点

删除链表节点

排序列表

合并链表

解法一：循环两两合并

解法二：归并合并

双链表