可以用LinkedHashMap的数据结构实现；要自己手写的话，就需要维护一个哈希+双向链表的数据结构，使用双链表来维护缓存项的访问顺序。最近访问的项位于链表的头部，而最久未访问的项位于链表的尾部。 Map<Integer,MyNodes>，底层就是数组+双向链表。put操作，找出来修改值，放到最前面，找不到就新增，节点放最前面get操作就把…

相交链表、反转链表、回文链表、环形链表、合并链表、删除链表某个节点、排序链表、LRU等。 总结的解题核心方式一般都是设置一个哑前置节点、双指针、快慢指针。

用哈希的方法比较简单，想想直接遍历的方法。 遍历链表，每次比较相邻两个节点，如果遇到了两个相邻节点相同，则新开内循环将这一段所有的相同都遍历过去。 在这一连串相同的节点前的节点，直接连上后续第一个不相同值的节点。 class Solution { public: ListNode* deleteDuplication(ListNode* pHead…

双指针算法 快慢指针，指针相遇的时候就是入口。证明如下： 设快指针的速度是慢指针的两倍，环之前有m个节点，环内有c个节点。当慢指针走了a步且两指针相遇时，快指针显然走了a+nc步（n表示快指针的绕环周期）。 再由先前的速度定义，有：2a = a+nc，即a = nc，说明慢指针此时，刚好走了n个环周期，只需要再走m步，就可以到达入口点了。再重置一个…

双指针算法 法1： 计算 List1 和 List2 的长度 len1 和 len2。 让较长的链表的指针先走 |len1 - len2| 步。 然后两个指针一起走，直到相遇或到达 NULL。 struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode*…

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求：空间复杂度O(1)（即在原树上操作），时间复杂度 O(n^2)要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继 二叉搜索树：左<根<右 法1：中序遍历将二叉搜索树进行中序遍历可以得到由小到大的…

涉及一个知识点，深拷贝与浅拷贝。 特性深拷贝 (Deep Copy)浅拷贝 (Shallow Copy)定义创建一个新对象，并递归复制所有成员及其指向的资源仅复制指针值，新旧对象共享同一块内存内存管理新旧对象完全独立，修改互不影响修改任一对象会影响另一个（可能导致双重释放或内存泄漏）性能较慢（需分配新内存并复制数据）极快（仅复制指针）使用场景需要完…

要求：空间复杂度 O(1) ，时间复杂度 O(n) 。 方法1：新链表合并，抄自牛客题解。比较直观。 class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { auto vhead=new ListNode(-1); //设置一个哨兵指针 ListN…