在哪买网站链接学校建设评建工作网站

当前位置： 首页 > news >正文

在哪买网站链接,学校建设评建工作网站,网赌网站怎么做,wordpress手机版app导航LeetCode HOT 100题解之链表篇 160 相交链表题目分析代码 206 反转链表方法一#xff1a;迭代 234 回文链表方法一#xff1a;将值复制到数组中方法二#xff1a;快慢指针 141 环形链表方法一#xff1a;哈希表方法二#xff1a;快慢指针 142 环形链表II方法一#xff1a… LeetCode HOT 100题解之链表篇 160 相交链表题目分析代码 206 反转链表方法一迭代 234 回文链表方法一将值复制到数组中方法二快慢指针 141 环形链表方法一哈希表方法二快慢指针 142 环形链表II方法一哈希表方法二快慢指针 21 合并两个有序链表方法一递归方法二迭代 2 两数相加方法一模拟 19 删除链表的倒数第N个结点方法一计算链表长度方法二栈方法三快慢指针 24 两两交换链表中的节点方法一迭代方法二递归 25 K个一组反转链表方法一模拟 138 随机链表的复制方法一哈希表 148 排序列表方法一归并排序递归法 23 合并K个升序链表方法一分治法 146 LRU缓存方法一哈希表双向链表 160 相交链表

1. 相交链表 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 图示两个链表在节点 c1 开始相交**** 题目数据 保证 整个链式结构中不存在环。 注意函数返回结果后链表必须 保持其原始结构 。 自定义评测 评测系统 的输入如下你设计的程序 不适用 此输入 intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0listA - 第一个链表listB - 第二个链表skipA - 在 listA 中从头节点开始跳到交叉节点的节点数skipB - 在 listB 中从头节点开始跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点那么你的解决方案将被 视作正确答案 。 示例 1 输入intersectVal 8, listA [4,1,8,4,5], listB [5,6,1,8,4,5], skipA 2, skipB 3 输出Intersected at 8 解释相交节点的值为 8 注意如果两个链表相交则不能为 0。 从各自的表头开始算起链表 A 为 [4,1,8,4,5]链表 B 为 [5,6,1,8,4,5]。 在 A 中相交节点前有 2 个节点在 B 中相交节点前有 3 个节点。 — 请注意相交节点的值不为 1因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说它们在内存中指向两个不同的位置而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点B 中第四个节点) 在内存中指向相同的位置。示例 2 输入intersectVal 2, listA [1,9,1,2,4], listB [3,2,4], skipA 3, skipB 1 输出Intersected at 2 解释相交节点的值为 2 注意如果两个链表相交则不能为 0。 从各自的表头开始算起链表 A 为 [1,9,1,2,4]链表 B 为 [3,2,4]。 在 A 中相交节点前有 3 个节点在 B 中相交节点前有 1 个节点。示例 3 输入intersectVal 0, listA [2,6,4], listB [1,5], skipA 3, skipB 2 输出null 解释从各自的表头开始算起链表 A 为 [2,6,4]链表 B 为 [1,5]。 由于这两个链表不相交所以 intersectVal 必须为 0而 skipA 和 skipB 可以是任意值。 这两个链表不相交因此返回 null 。提示 listA 中节点数目为 mlistB 中节点数目为 n1 m, n 3 * 1041 Node.val 1050 skipA m0 skipB n如果 listA 和 listB 没有交点intersectVal 为 0如果 listA 和 listB 有交点intersectVal listA[skipA] listB[skipB] 进阶你能否设计一个时间复杂度 O(m n) 、仅用 O(1) 内存的解决方案 题目分析 //只能说题目思想nb//现在假设有A,B两个链表A长度为5B长度为3//那么假如我用一个指针pa先遍历A再遍历B另一个指针pb先遍历B再遍历A//这样pa和pb遍历的长度最终都会是53 3 5 8//那么最终pa和pb一定会在A和B相交的节点相遇 //可以简单证明一下假设A,B相交的节点数为cA的总结点数为mcB的为nc//那么当A,B通过这样的方式相遇时pa走过来mcnpb走过了ncm此时正好pa和pb会在相交点相遇对于AB而言剩下c代码 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/ public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//只能说题目思想nb//现在假设有A,B两个链表A长度为5B长度为3//那么假如我用一个指针pa先遍历A再遍历B另一个指针pb先遍历B再遍历A//这样pa和pb遍历的长度最终都会是53 3 5 8//那么最终pa和pb一定会在A和B相交的节点相遇 //可以简单证明一下假设A,B相交的节点数为cA的总结点数为mcB的为nc//那么当A,B通过这样的方式相遇时pa走过来mcnpb走过了ncm此时正好pa和pb会在相交点相遇对于AB而言剩下cListNode pA headA,pB headB;if(pA null || pB null){return null;}while(pA ! pB){pA pA null? headB : pA.next;pB pB null? headA : pB.next;}return pA;} }206 反转链表
2. 反转链表 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 示例 1
   输入head [1,2,3,4,5] 输出[5,4,3,2,1]示例 2
   输入head [1,2] 输出[2,1]示例 3 输入head [] 输出[]提示 链表中节点的数目范围是 [0, 5000]-5000 Node.val 5000 进阶链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题 方法一迭代 假设链表为 1→2→3→∅我们想要把它改成 ∅←1←2←3。 在遍历链表时将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点因此必须事先存储其前一个节点。在更改引用之前还需要存储后一个节点。最后返回新的头引用。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/ class Solution {public ListNode reverseList(ListNode head) {//迭代的话需要将链表节点的指针反向//在这里我们考虑三个节点prevcurrnext 分别代表上一个当前和下一个节点//需要将curr.next指向prev所以next需要记录原本的curr下一个节点//并且由于节点没有引用前一个节点因此需要事先存储前一个节点。在更改引用之前还需要存储后一个节点//比较巧妙的是另prev null这样可以直接从头开始遍历不用考虑头节点的特殊情况ListNode prev null;ListNode curr head;while(curr ! null){ListNode next curr.next;//更改引用之前需要存储后一个节点curr.next prev;//更改引用prev curr;//更新前一个节点curr next;//更新当前节点}return prev;//因为curr此时会指向null} }234 回文链表
3. 回文链表 给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。 示例 1 输入head [1,2,2,1] 输出true示例 2 输入head [1,2] 输出false提示 链表中节点数目在范围[1, 105] 内0 Node.val 9 进阶你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题 方法一将值复制到数组中 很直观判断一个数组是否是回文很简单但是判断链表存在难度。想要判断数组是否回文可以直接使用双指针的方法。因此方法一是简单的将链表中的值复制到数组中。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/ class Solution {public boolean isPalindrome(ListNode head) {/方法一将值复制到数组中后用双指针法 */ListInteger list new ArrayListInteger ();ListNode temphead;while(temp!null){list.add(temp.val);temp temp.next;}int front 0,end list.size()-1;while(front end){if(list.get(front)!list.get(end)){return false;}front;end–;}return true;} }方法二快慢指针 避免O(n)额外空间的方法就是改变输入。 可以考虑反转链表的后半部分之后判断后半部分反转后的链表与前半部分是否相同。最后恢复链表返回结果1.找到前半部分链表的尾节点 (使用快慢指针)2.反转后半部分链表3.判断是否回文4.恢复链表5.返回结果/* Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }/ class Solution {public boolean isPalindrome(ListNode head) {/**方法三快慢指针可以考虑反转链表的后半部分之后判断后半部分反转后的链表与前半部分是否相同。最后恢复链表返回结果1.找到前半部分链表的尾节点 (使用快慢指针)2.反转后半部分链表3.判断是否回文4.恢复链表5.返回结果/ListNode firstHalfEnd endOfFirstHalf(head);ListNode secondHalfStart reverseList(firstHalfEnd.next);//反转后半部分的链表ListNode p1 head;ListNode p2 secondHalfStart;boolean flag true;while(flag p2!null){if(p1.val ! p2.val){flag false;}p1 p1.next;p2 p2.next;}firstHalfEnd.next reverseList(secondHalfStart);return flag;}private ListNode reverseList(ListNode head){ListNode curr head;ListNode prev null;while(curr ! null){ListNode next curr.next;curr.next prev;prev curr; //更新前一个节点curr next; //更新后一个节点}return prev; //注意到最后curr是null因此要返回prev}//使用快慢指针找到前面链表的最后一个节点当链表长度为奇数时将中间的奇数节点认为是前半部分。举个例子//1,2,3,4,5 ://fast:1,3,5//slow:1,2,3//1,2,3,4//fast:1,3,//slow:1,2,private ListNode endOfFirstHalf(ListNode head){ListNode slow head;ListNode fast head;while(fast.next ! null fast.next.next !null){slow slow.next;fast fast.next.next;}return slow;} }141 环形链表
4. 环形链表 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。 示例 1 输入head [3,2,0,-4], pos 1 输出true 解释链表中有一个环其尾部连接到第二个节点。示例 2 输入head [1,2], pos 0 输出true 解释链表中有一个环其尾部连接到第一个节点。示例 3 输入head [1], pos -1 输出false 解释链表中没有环。提示 链表中节点的数目范围是 [0, 104]-105 Node.val 105pos 为 -1 或者链表中的一个 有效索引 。 进阶你能用 O(1)即常量内存解决此问题吗 方法一哈希表 判断是否存在环就是遍历所有节点每次遍历到一个节点就判断该节点此前是否被访问过。 用哈希表存储所有已经访问过的节点每次到达一个界定啊如果该节点已经存在于哈希表中则说明该链表是环形链表否则就将该节点加入哈希表中。重复直至遍历完所有链表。 复杂度分析 时间复杂度O(N)其中 N 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。空间复杂度O(N)其中 N 是链表中的节点数。主要为哈希表的开销最坏情况下我们需要将每个节点插入到哈希表中一次。
   /*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }/ public class Solution {public boolean hasCycle(ListNode head) {//最简单的hash表SetListNode set new HashSetListNode();ListNode temp head;while(temp ! null){if(!set.add(temp)){return true;}temp temp.next;}return false;} }方法二快慢指针 方法二快慢指针Floyd判圈算法龟兔赛跑算法假设乌龟和兔子在链表上移动假如链表中没有环那么兔子会一直在乌龟的前方。但是如果存在环那么兔子会先于乌龟进入环之后一直在环中移动。等乌龟进入环后由于兔子速度快兔子一定会在某一时刻与乌龟相遇。若不存在环那么直接当兔子跑到终点的时候结束实现起来也是一个while循环判断slow是否等于fast如果能跳出while循环说明slot fast存在环同时在while内部还要设置终止条件即fast.next null或者fast.next.next null/** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }/ public class Solution {public boolean hasCycle(ListNode head) {/**方法二快慢指针Floyd判圈算法龟兔赛跑算法假设乌龟和兔子在链表上移动假如链表中没有环那么兔子会一直在乌龟的前方。但是如果存在环那么兔子会先于乌龟进入环之后一直在环中移动。等乌龟进入环后由于兔子速度快兔子一定会在某一时刻与乌龟相遇。若不存在环那么直接当兔子跑到终点的时候结束实现起来也是一个while循环判断slow是否等于fast如果能跳出while循环说明slot fast存在环同时在while内部还要设置终止条件即fast.next null或者fast.next.next null/if(head null || head.next null){return false;} ListNode slow head;ListNode fast head.next;while(slow ! fast ){ //能跳出循环说明slow fast所以if(fast.nextnull || fast.next.next null){return false;}slow slow.next;fast fast.next.next;}return true;} }142 环形链表II
5. 环形链表 II 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 不允许修改 链表。 示例 1 输入head [3,2,0,-4], pos 1 输出返回索引为 1 的链表节点 解释链表中有一个环其尾部连接到第二个节点。示例 2 输入head [1,2], pos 0 输出返回索引为 0 的链表节点 解释链表中有一个环其尾部连接到第一个节点。示例 3 输入head [1], pos -1 输出返回 null 解释链表中没有环。提示 链表中节点的数目范围在范围 [0, 104] 内-105 Node.val 105pos 的值为 -1 或者链表中的一个有效索引 进阶你是否可以使用 O(1) 空间解决此题 方法一哈希表 哈希表的实现思路同上题此处不再过多赘述 /*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }/ public class Solution {public ListNode detectCycle(ListNode head) {SetListNode set new HashSetListNode();ListNode temp head;while(temp ! null){if(!set.add(temp)){return temp;}temp temp.next;}return null;} }方法二快慢指针 重画链表如下所示线上有若干个节点。记蓝色慢指针为 slow红色快指针为 fast。初始时 slow 和 fast 均在头节点处。使 slow 和 fast 同时前进fast 的速度是 slow 的两倍。当 slow 抵达环的入口处时fast 一定在环上如下所示。其中 head 和 A 的距离为 z弧 AB (沿箭头方向) 的长度为 x同理弧 BA 的长度为 y 可得 slow 走过的步数为 z设 fast 已经走过了 k 个环k≥0对应的步数为 zk(xy)x 以上两个步数中后者为前者的两倍即 2zzk(xy)x 化简可得 zxk(xy)替换如下所示。 此时因为 fast 比 slow 快 1 个单位的速度且y 为整数所以再经过 y 个单位的时间即可追上 slow。 即 slow 再走 y 步fast 再走 2y 步。设相遇在 C 点位置如下所示可得弧 AC 长度为 y。因为此前xy 为环长所以弧 CA 的长度为 x。 此时我们另用一橙色指针 ptr (pointer) 指向 head如下所示。并使 ptr 和 slow 保持 1 个单位的速度前进在经过 zxk(xy) 步后可在 A 处相遇。再考虑链表无环的情况fast 在追到 slow 之前就会指向空节点退出循环即可。 /** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }/ public class Solution {public ListNode detectCycle(ListNode head) {/**方法二快慢指针。这里需要具体原理需要参考题解。在这里就简单说一下做法。同样设置快慢指针fast和slow均位于list的头部。我们设链表中环外的长度为z当slow指针位于环的入口时fast指针距离环的入口长度为x圆的总周长为xy那么此时slow走的长度为zfast走的长度为zk(xy)x2z zk(xy)x,解出可得z k(xy)x此时若slow想与fast相遇,假如slow静止fast相对于slow的速度为1此时fast还需要经过y步才能与slow相遇。即slow与fast相遇时slow距离环的入口长度为y若slow需要再回到入口需要走xy-y x 步这时假如我们另一个额外指针ptr从head处开始遍历那么ptr会和slow在环的入口处相遇。因为ptr需要走z k(xy)x 到达入口slow 会走xk(xy)到达入口/if(head null || head.next null){return null;}ListNode slow head;ListNode fast head;do{if(fast.next null || fast.next.next null){return null;}slow slow.next;fast fast.next.next;}while(slow ! fast);ListNode ptr head;while(ptr ! slow){ptr ptr.next;slow slow.next;}return ptr;} }21 合并两个有序链表
6. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1 输入l1 [1,2,4], l2 [1,3,4] 输出[1,1,2,3,4,4]示例 2 输入l1 [], l2 [] 输出[]示例 3 输入l1 [], l2 [0] 输出[0]提示 两个链表的节点数目范围是 [0, 50]-100 Node.val 100l1 和 l2 均按 非递减顺序 排列 方法一递归 本来以为递归解法会很难后面发现只要写出了递归表达式并且清楚边界条件递归解法会比其他解法更加容易。 在这里我们已知有两个链表l1l2。可以给出如下的递归定义。两个链表头部值较小的一个节点与剩下元素的merge操作结果合并。 { l i s t 1 [ 0 ] m e r g e ( l i s t 1 [ 1 : ] , l i s t 2 ) l i s t 1 [ 0 ] l i s t 2 [ 0 ] l i s t 2 [ 0 ] m e r g e ( l i s t 1 , l i s t 2 [ 1 : ] ) o t h e r w i s e \left.\left{\begin{array}{ll}list1[0]merge(list1[1:],list2)list1[0]list2[0]\list2[0]merge(list1,list2[1:])otherwise\end{array}\right.\right. {list1[0]merge(list1[1:],list2)list2[0]merge(list1,list2[1:])​list1[0]list2[0]otherwise​ 所以思路就是如果l1或者l2为空不需要合并直接返回非空链表即可。若l1.vall2.val那么l1需要被添加到结果里然后继续合并l1.next merge(l1.next,l2). 如果两个链表钟有一个为空递归结束。 其实核心思想都是需要将较小值添加到结果中之后再去决定下一个要添加到结果里的节点。 代码如下 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }/ class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {/**方法一递归递归定义两个链表中的merge操作list1[0]list2[0],list1[0]merge(list[1:],list2)otherwise,list2[0]merge(list1,list2[1:])/if(list1 null){return list2;}else if(list2 null){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;}} }方法二迭代 当l1l2都不是空链表的时候判断l1和l2哪一个链表的头节点值更小将较小值的节点添加到结果中当一个节点被添加到结果里后将对应链表里的节点后移一位 一开始没想到的是对结果链表最好初始化一个头节点和遍历的节点不然直接在list1和list2上操作会有点乱 想到需要结果链表之后就容易了。 定义一个prevHead作为结果链表的哨兵节点维护curr指针指向当前遍历的元素。 需要不停的修改curr的next直到l1或者l2为null 如果当前l1.vall2.val那么curr.next l1,l1 l1.next; 否则curr.next l2,l2l2.next; 不管哪个元素接在了结果链表的后面都需要将curr指针后移 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }/ class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {/**方法二迭代当l1l2都不是空链表的时候判断l1和l2哪一个链表的头节点值更小将较小值的节点添加到结果中当一个节点被添加到结果里后将对应链表里的节点后移一位一开始没想到的是对结果链表最好初始化一个头节点和遍历的节点不然直接在list1和list2上操作会有点乱想到需要结果链表之后就容易了。定义一个prevHead作为结果链表的哨兵节点维护curr指针指向当前遍历的元素。需要不停的修改curr的next直到l1或者l2为null如果当前l1.vall2.val那么curr.next l1,l1 l1.next;否则curr.next l2,l2l2.next;不管哪个元素接在了结果链表的后面都需要将curr指针后移。/ListNode prevHead new ListNode();ListNode curr prevHead;while(list1 ! null list2 ! null){ListNode temp;if(list1.val list2.val){//将list1的当前节点添加到结果中temp list1.next;curr.next list1;list1 list1.next;}else{temp list2.next;curr.next list2;list2 list2.next;}curr curr.next;//移动结果指针}curr.next list1null?list2 : list1;return prevHead.next;} }2 两数相加
7. 两数相加 给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。 请你将两个数相加并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外这两个数都不会以 0 开头。 示例 1 输入l1 [2,4,3], l2 [5,6,4] 输出[7,0,8] 解释342 465 807.示例 2 输入l1 [0], l2 [0] 输出[0]示例 3 输入l1 [9,9,9,9,9,9,9], l2 [9,9,9,9] 输出[8,9,9,9,0,0,0,1]提示 每个链表中的节点数在范围 [1, 100] 内0 Node.val 9题目数据保证列表表示的数字不含前导零 方法一模拟 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/ class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dummpy new ListNode();//定义哑节点ListNode curr dummpy;int carry 0;while(l1!null || l2!null ){int a l1!null ?l1.val :0;int b l2!null ?l2.val : 0;int sum abcarry;curr.next new ListNode(sum%10);curr curr.next;carry sum /10;if(l1 ! null) l1 l1.next;if(l2 ! null ) l2 l2.next;}if(carry 0){curr.next new ListNode(carry);}return dummpy.next;} }19 删除链表的倒数第N个结点
8. 删除链表的倒数第 N 个结点 提示 给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。 示例 1 输入head [1,2,3,4,5], n 2 输出[1,2,3,5]示例 2 输入head [1], n 1 输出[]示例 3 输入head [1,2], n 1 输出[1]提示 链表中结点的数目为 sz1 sz 300 Node.val 1001 n sz 进阶你能尝试使用一趟扫描实现吗 方法一计算链表长度 关于这种删除第几个节点的题我总是有点不明白应该如何写循环才能遍历到第n个节点。需要手动模拟 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }/ class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//思路很直接先遍历一遍链表获得链表长度L,之后再从头节点开始对链表进行一次遍历当遍历到第L-n1个节点时它就是我们需要删除的节点。链表长度为5时要删除倒数第2个节点等价于要删除第4个节点//为了方便删除引入一个dummpyNode此时遍历到的第L-n1个节点时下一个节点就是我们要是删除的节点。int L getLength(head);//引入dummpyNodeListNode dummpy new ListNode(0,head);//遍历到第L-n1个节点//现在length5n2我们想要删除的是第L-n1 4个节点//因此需要循环执行3次让指针指向想要删除的节点的前一个节点//所以另i1ListNode curr dummpy;for(int i 1;iL-n1;i){curr curr.next;}//删除节点curr.next curr.next.next;return dummpy.next;}public int getLength(ListNode head){int n 0;while(head ! null){head head.next;n;}return n;} }方法二栈 我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则我们弹出栈的第 n 个节点就是需要删除的节点并且目前栈顶的节点就是待删除节点的前驱节点。这样一来删除操作就变得十分方便了。 复杂度分析 时间复杂度O(L)其中 L 是链表的长度。空间复杂度O(L)其中 L 是链表的长度。主要为栈的开销。 /** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }/ class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//方法二栈/**先把List中的结点都push到栈中。之后再往外弹弹n次后第n次出栈的就是要删除的第n个结点栈顶元素即为要删除的结点的前一个结点.在之前先加一个哑结点不然需要额外处理要删除头结点的情况熟悉一下Java中栈的定义和使用Deque LinkedListpush(),pop(),peek()/DequeListNode stack new LinkedListListNode ();ListNode dummpy new ListNode(0,head);ListNode cur dummpy;while(cur ! null){stack.push(cur);curcur.next;}for(int i 0;in;i){stack.pop();}cur stack.peek();cur.next cur.next.next;return dummpy.next;}}方法三快慢指针 由于我们需要找到倒数第 n 个节点因此我们可以使用两个指针 first 和 second 同时对链表进行遍历并且 first 比 second 超前 n 个节点。当 first 遍历到链表的末尾时second 就恰好处于倒数第 n 个节点。 具体地初始时 first 和 second 均指向头节点。我们首先使用 first 对链表进行遍历遍历的次数为 n。此时first 和 second 之间间隔了 n−1 个节点即 first 比 second 超前了 n 个节点。 在这之后我们同时使用 first 和 second 对链表进行遍历。当 first 遍历到链表的末尾即 first 为空指针时second 恰好指向倒数第 n 个节点。 根据方法一和方法二如果我们能够得到的是倒数第 n 个节点的前驱节点而不是倒数第 n 个节点的话删除操作会更加方便。因此我们可以考虑在初始时将 second 指向哑节点其余的操作步骤不变。这样一来当 first 遍历到链表的末尾时second 的下一个节点就是我们需要删除的节点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }/ class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//方法二先后指针/**当一个指针遍历到末尾空指针时需要另一个指针刚好指在倒数第n个的结点的位置。fast,slowfast比slow要先走n步之后同时前进就可以满足这个条件为什么要先走n步呢假设现在有5个节点12345需要删除倒数第2个节点也就是4fast先走2步走到3之后slow和fast开始同时遍历slow :2 fast :4slow:3 fast 5slow:4 fast null 停止遍历但是我们先走想要指针能指向要删除结点的前一个结点因此这里先引入dummpyNode/ListNode dummpy new ListNode(0,head);ListNode fast head;ListNode slow dummpy;//先走n步for(int i 0;in;i){fast fast.next;}//同时遍历while(fast ! null){fast fast.next;slow slow.next;}slow.next slow.next.next;return dummpy.next;}}24 两两交换链表中的节点
9. 两两交换链表中的节点 给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。 示例 1 输入head [1,2,3,4] 输出[2,1,4,3]示例 2 输入head [] 输出[]示例 3 输入head [1] 输出[1]提示 链表中节点的数目在范围 [0, 100] 内0 Node.val 100 方法一迭代 创建哑结点dummpyHead,另dummpyHead.next head另curr代表当前到达的节点 算法思路 初始化创建一个哑节点 dummy它的 next 指向头节点 head。哑节点用于简化对头节点交换的处理。遍历链表使用两个指针 prev 和 curr 分别指向当前正在处理的节点的前一个节点和当前节点。初始时prev 指向哑节点curr 指向头节点。交换节点 检查 curr 和 curr.next 是否为 null如果任一为 null则表示没有更多的节点可以交换算法结束。保存 curr.next.next即下一对需要交换的节点的起始节点。执行交换(prev-curr-curr.next-next) 将 prev.next 指向 curr.next即把第二节点b设置为新的前一个节点的下一个节点。将 curr.next.next 指向 curr即把第二节点b的下一个节点指向第一节点a。将 curr.next 指向 next即把第一节点a的下一个节点指向下一对节点的起始节点。 更新指针更新 prev 和 curr 以指向下一对需要交换的节点。返回结果返回哑节点的下一个节点即交换后的链表的头节点。 代码实现 class Solution {public ListNode swapPairs(ListNode head) {if (head null) {return null;}ListNode dummy new ListNode(-1, head);ListNode prev dummy;ListNode curr dummy.next;while (curr ! null curr.next ! null) {ListNode next curr.next.next;prev.next curr.next; // 第一步将前一个节点指向当前节点的下一个节点curr.next.next curr; // 第二步将当前节点的下一个节点的下一个节点指向当前节点curr.next next; // 第三步将当前节点的下一个节点指向下一对节点的起始节点prev curr; // 更新 prev 为当前节点curr next; // 更新 curr 为下一对节点的起始节点}return dummy.next;} }确保在断开节点连接之前正确设置所有指针以避免丢失节点。使用哑节点可以简化对头节点交换的处理避免特殊情况的判断。 这个算法的时间复杂度是 O(n)其中 n 是链表的长度因为我们需要遍历整个链表一次。空间复杂度是 O(1)除了输入的链表外我们只使用了有限的额外空间。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }/ class Solution {public ListNode swapPairs(ListNode head) {if(head null){return null;}ListNode dummpy new ListNode(-1,head);ListNode prev dummpy;ListNode curr dummpy.next;//现在有List abcde//我们需要两两一组进行交换先引入一个哑节点dummpy//假设需要对ab交换此时需要记录ab前的指针以及ab后的节点c//prev dummpy,curr a ,next curr.next.next ©//开始交换//重点是第一步一定要在第三步之前。就是在断掉a-b的指针需要将a指向c时一定要先将prev.next b,不然会找不到b//当然也可以再声明一个Node指向b不用全在curr上操作。//第一步应该是将prev.next curr.next (头节点的下一个是b)//第二步 curr.next.next curr (b的指针指向a)//第三步 curr.next next (a的指针指向c) //最后开始更新prev和curr//prev curr (curr始终指的是a)现在a已经被我们交换到后面去变成b,a了所以prev curr//curr next; curr现在应当指向下一组需要被两两交换的节点也就是cwhile(curr ! null curr.next ! null){ListNode next curr.next.next;prev.next curr.next; // 第一步将前一个节点指向当前节点的下一个节点curr.next.next curr; // 第二步将当前节点的下一个节点的下一个节点指向当前节点curr.next next;// 第三步将当前节点的下一个节点指向下一对节点的起始节点prev curr;// 更新 prev 为当前节点curr next;// 更新 curr 为下一对节点的起始节点}return dummpy.next;} }方法二递归 思路与算法 可以通过递归的方式实现两两交换链表中的节点。 递归的终止条件是链表中没有节点或者链表中只有一个节点此时无法进行交换。 如果链表中至少有两个节点则在两两交换链表中的节点之后原始链表的头节点变成新的链表的第二个节点原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后更新节点之间的指针关系即可完成整个链表的两两交换。 用 head 表示原始链表的头节点新的链表的第二个节点用 newHead 表示新的链表的头节点原始链表的第二个节点则原始链表中的其余节点的头节点是 newHead.next。令 head.next swapPairs(newHead.next)表示将其余节点进行两两交换交换后的新的头节点为 head 的下一个节点。然后令 newHead.next head即完成了所有节点的交换。最后返回新的链表的头节点 newHead。 /** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }/ class Solution {public ListNode swapPairs(ListNode head) {/**方法二递归///1.判断递归结束的条件,当当前节点为空或者当前节点只有一个时无需交换递归结束if(head null || head.next null){return head;}//2.开始递归现在链表为head,head.next,…ListNode newHead head.next;head.next swapPairs(newHead.next);newHead.next head;return newHead;} }25 K个一组反转链表
10. K 个一组翻转链表 给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。 k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。 示例 1 输入head [1,2,3,4,5], k 2 输出[2,1,4,3,5]示例 2 输入head [1,2,3,4,5], k 3 输出[3,2,1,4,5]提示 链表中的节点数目为 n1 k n 50000 Node.val 1000 进阶你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗 方法一模拟 我们需要将链表节点按照k个一组进行分组。对于每个分组要判断长度是否大于k是则翻转这部分链表否则则不需要翻转。 1.如何按k个一组进行分组用head指向每组的头结点指针向前移动k次到达尾结点。 2.翻转之后子链表的头部需要与上一个子链表相连接子链表的尾部也要连接下一个子链表。因此在翻转时需要子链表的头结点head以及head的上一个结点pre 3.如何翻转子链表。这里参考206 翻转链表题目的解法。 复杂度分析 时间复杂度O(n)其中 n 为链表的长度。head 指针会在 O(⌊n/k ⌋) 个节点上停留每次停留需要进行一次 O(k) 的翻转操作。 空间复杂度O(1)我们只需要建立常数个变量。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/ class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode dummpy new ListNode(-1,head);ListNode pre dummpy; //记录该小组前的最后一个节点while(head ! null){ListNode tail pre;//for(int i 0;ik;i){tail tail.next;if(tail null){ //如果该组节点小于k返回return dummpy.next;}}ListNode nex tail.next; //记录该小组后的第一个节点ListNode[] reverse myReverse(head,tail);pre.next reverse[0]; //reverse[0]是反转后的headreverse[1]是反转链表后的的tailreverse[1].next nex; //将反转链表后的节点连上反转的链表pre reverse[1];//更新prehead pre.next;//更新head}return dummpy.next;}public ListNode[] myReverse(ListNode head, ListNode tail) {//反转head -tail之间的链表// ListNode dummpy new ListNode(-1,head);ListNode prev null;ListNode curr head;tail.next null;while(curr ! null){ListNode next curr.next;curr.next prev;prev curr;curr next;}return new ListNode[] {tail,head};} }138 随机链表的复制
11. 随机链表的复制 给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如如果原链表中有 X 和 Y 两个节点其中 X.random – Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random – y 。 返回复制链表的头节点。 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示 val一个表示 Node.val 的整数。random_index随机指针指向的节点索引范围从 0 到 n-1如果不指向任何节点则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。 示例 1 输入head [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出[[7,null],[13,0],[11,4],[10,2],[1,0]]示例 2 输入head [[1,1],[2,1]] 输出[[1,1],[2,1]]示例 3 输入head [[3,null],[3,0],[3,null]] 输出[[3,null],[3,0],[3,null]]提示 0 n 1000-104 Node.val 104Node.random 为 null 或指向链表中的节点。 方法一哈希表 直接复制。用hashmap存储oldnode和newnodeoldnode,newnode,之后遍历原先的链表为新链表的next和random赋值。 ​ map.get(cur).next map.get(cur.next); //新节点的next 原先节点next的 复制节点 ​ map.get(cur).random map.get(cur.random); //新节点的random 原先节点random的复制节点 /* // Definition for a Node. class Node {int val;Node next;Node random;public Node(int val) {this.val val;this.next null;this.random null;} } */class Solution {public Node copyRandomList(Node head) {MapNode,Node map new HashMap();Node cur head;while(cur ! null){map.put(cur,new Node(cur.val));cur cur.next;}cur head;while(cur ! null){map.get(cur).next map.get(cur.next); //新节点的next 原先节点next的 复制节点map.get(cur).random map.get(cur.random);cur cur.next;}return map.get(head);} }148 排序列表
12. 排序链表 给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。 示例 1
    输入head [4,2,1,3] 输出[1,2,3,4]示例 2
    输入head [-1,5,3,4,0] 输出[-1,0,3,4,5]示例 3 输入head [] 输出[]提示 链表中节点的数目在范围 [0, 5 * 104] 内-105 Node.val 105 进阶你可以在 O(n log n) 时间复杂度和常数级空间复杂度下对链表进行排序吗 方法一归并排序递归法 其实没有想到归并排序。这里就相当于重新复习一遍。归并排序是一种分而治之的算法。将大问题分解成小问题再解决小问题将小问题的解合并成大问题的解。 具体到这个题目中就是将链表一分为二之后再排序合并。 数组额外空间链表可以通过修改引用来更改节点顺序无需像数组一样开辟额外空间 递归额外空间递归调用函数将带来 O(logn) 的空间复杂度因此若希望达到 O(1) 空间复杂度则不能使用递归。 通过递归实现链表归并排序有以下两个环节 分割 cut 环节 找到当前链表 中点并从 中点 将链表断开以便在下次递归 cut 时链表片段拥有正确边界 我们使用 fast,slow 快慢双指针法奇数个节点找到中点偶数个节点找到中心左边的节点。 找到中点 slow 后执行 slow.next None 将链表切断。 递归分割时输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。 cut 递归终止条件 当 head.next None 时说明只有一个节点了直接返回此节点。 合并 merge 环节 将两个排序链表合并转化为一个排序链表。 双指针法合并建立辅助 ListNode h 作为头部。设置两指针 left, right 分别指向两链表头部比较两指针处节点值大小由小到大加入合并链表头部指针交替前进直至添加完两个链表。返回辅助ListNode h 作为头部的下个节点 h.next。
    时间复杂度 O(l r)l, r 分别代表两个链表长度。 当题目输入的 head None 时直接返回 None。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/ class Solution {public ListNode sortList(ListNode head) {//归并排序对单链表进行排序。//归并排序分治算法将大问题分解成小问题递归解决之后将小问题的解合并为大问题的解。//本题中将链表分成两半对每段进行排序之后将排序后的链表合成一个。//1.递归结束条件当前为空或者当前只有1个元素if(head null || head.next null){return head;}//2.通过快慢指针找到中点ListNode fast head;ListNode slow head;while(fast.next!null fast.next.next ! null){fast fast.next.next;slow slow.next;}//找到第二段list的起点并将第一段链表的终点设为nullListNode mid slow.next;slow.next null;//递归ListNode list1 sortList(head);ListNode list2 sortList(mid);//合并排序ListNode sorted merge(list1,list2);return sorted;}public ListNode merge(ListNode head1,ListNode head2){ListNode dummpy new ListNode(0);ListNode temp dummpy,temp1 head1,temp2 head2;while(temp1 ! null temp2 ! null){if(temp1.val temp2.val){temp.next temp1;temp1 temp1.next;}else{temp.next temp2;temp2 temp2.next;}temp temp.next;//一定要更新}if(temp1!null){temp.next temp1;}else if(temp2!null){temp.next temp2;}return dummpy.next;} }23 合并K个升序链表
13. 合并 K 个升序链表 给你一个链表数组每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中返回合并后的链表。 示例 1 输入lists [[1,4,5],[1,3,4],[2,6]] 输出[1,1,2,3,4,4,5,6] 解释链表数组如下 [1-4-5,1-3-4,2-6 ] 将它们合并到一个有序链表中得到。 1-1-2-3-4-4-5-6示例 2 输入lists [] 输出[]示例 3 输入lists [[]] 输出[]提示 k lists.length0 k 10^40 lists[i].length 500-10^4 lists[i][j] 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4 方法一分治法 分治法 1.将k个链表两两配对并将同一对中的链表合并。 2.第一轮合并后k个链表被合并为k/2个链表 3.重复12 就能得到最终的有序链表 写递归的话注意写递归结束的条件当递归中只有一个链表要处理时直接返回该链表否则递归合并。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/ class Solution {public ListNode mergeKLists(ListNode[] lists) {//分治法K个一组合并return merge(lists,0,lists.length-1);}public ListNode merge(ListNode[] lists,int start,int end){if(start end){ //当前递归中只有1个链表要处理所以直接返回return lists[start];//说明排序完毕}if(start end){return null;}int mid (start end) 1;return mergeTwoLists(merge(lists,start,mid),merge(lists,mid1,end));}public ListNode mergeTwoLists(ListNode head1,ListNode head2){ListNode dumpy new ListNode(0);ListNode temp dumpy,temp1 head1,temp2 head2;while(temp1!null temp2 !null){if(temp1.val temp2.val){temp.next temp1;temp1 temp1.next;}else{temp.next temp2;temp2 temp2.next;}temp temp.next;}if(temp1 ! null){temp.next temp1;}else{temp.next temp2;}return dumpy.next;} }146 LRU缓存
14. LRU 缓存 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类 LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity 则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。 示例 输入 [LRUCache, put, put, get, put, get, put, get, get, get] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4]解释 LRUCache lRUCache new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {11} lRUCache.put(2, 2); // 缓存是 {11, 22} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4提示 1 capacity 30000 key 100000 value 105最多调用 2 * 105 次 get 和 put 方法一哈希表双向链表 这个题目以前没有做过是个比较新颖有趣的题。用自定义的双向链表结构实现这一点。 哈希表存储key,DLinkedNode(value)键值对通过key来映射到DLinkedNode的位置。 之后就可以判断最近使用了只要使用过就将该值动DLinkedNode中移动到头部。 LRU 缓存机制可以通过哈希表辅以双向链表实现我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。 双向链表按照被使用的顺序存储了这些键值对靠近头部的键值对是最近使用的而靠近尾部的键值对是最久未使用的。哈希表即为普通的哈希映射HashMap通过缓存数据的key映射到其在双向链表中的位置。因此为key,DLinkedNode 这样以来我们首先使用哈希表进行定位找出缓存项在双向链表中的位置随后将其移动到双向链表的头部即可在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下 对于 get 操作首先判断 key 是否存在 如果 key 不存在则返回 −1如果 key 存在则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置并将其移动到双向链表的头部最后返回该节点的值。 对于 put 操作首先判断 key 是否存在 如果 key 不存在使用 key 和 value 创建一个新的节点在双向链表的头部添加该节点并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量如果超出容量则删除双向链表的尾部节点并删除哈希表中对应的项 如果 key 存在则与 get 操作类似先通过哈希表定位再将对应的节点的值更新为 value并将该节点移到双向链表的头部。
    上述各项操作中访问哈希表的时间复杂度为 O(1)在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。而将一个节点移到双向链表的头部可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作都可以在 O(1) 时间内完成。 小贴士 在双向链表的实现中使用一个伪头部dummy head和伪尾部dummy tail标记界限这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。 class LRUCache {/使用一个哈希表双向链表实现这个操作。因为get和put要以O(1)的复杂度说明get需要用hashmapput的话需要逐出最久未使用的关键字删除操作平均时间复杂度也是O(1),因此需要用双向链表来实现。HashMapkey,DLinkNode(value),通过这种方式来实现LRU*///定义一个双向节点class DLinkedNode{int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode(){}public DLinkedNode(int _key,int _value){ key _key;value _value;}}//定义cache 的map结构当前容量size和最大容量capacityprivate MapInteger,DLinkedNode map new HashMap();private int size ;private int capacity;private DLinkedNode head,tail; //定义伪头结点和伪尾结点//LRUCache初始化public LRUCache(int capacity) {this.size 0;this.capacity capacity;//初始化伪头结点和伪尾结点head new DLinkedNode();tail new DLinkedNode();head.next tail;tail.prev head;}//get操作先判断key是否存在不存在则返回-1//存在key应当是最近被使用的结点将key移动到双向链表的头部返回该结点的值public int get(int key) {DLinkedNode node map.get(key);if(node!null){//将该结点移动到双向链表的头部moveToHead(node);return node.value;}else{return -1;}}//先判断key是否存在不存在则创建新节点在双链表的头部添加该结点后往map中插入//并且判断双向链表中的节点数是否超出容量//超出容量则删除双向链表的尾部结点删除map中对应的项//存在则通过哈希表定位值更新为value并将该结点移动到双向链表的头部public void put(int key, int value) {DLinkedNode node map.get(key);if(node!null){//存在需要更新值移动头部node.value value;moveToHead(node);}else{DLinkedNode newnode new DLinkedNode(key,value);//添加进hashmapmap.put(key,newnode);//向双向链表头部插入结点addToHead(newnode);size; //大小//判断当前是否超过最大容量if(sizecapacity){ DLinkedNode tail removeTail();//删除hashmap中的对应项map.remove(tail.key); –size;}}}//从中可以抽象出,将结点添加到头部private void addToHead(DLinkedNode node){node.prev head;node.next head.next;head.next.prev node;head.next node;}//从双向链表中移除结点private void removeNode(DLinkedNode node){node.prev.next node.next; //前一个结点的next应当指向后一个node.next.prev node.prev; //后一个结点的prev应当指向前一个结点}//移动到头部private void moveToHead(DLinkedNode node){removeNode(node);addToHead(node);}//尾部元素删除private DLinkedNode removeTail(){DLinkedNode res tail.prev;removeNode(res);return res;} }/* 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);*/