相交链表160. 相交链表 - 力扣LeetCode给你两个单链表的头节点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输出No intersection解释从各自的表头开始算起链表 A 为 [2,6,4]链表 B 为 [1,5]。 由于这两个链表不相交所以 intersectVal 必须为 0而 skipA 和 skipB 可以是任意值。 这两个链表不相交因此返回 null 。解法及思路双指针两个指针分别从 A 和 B 出发走完自己的链表后切换到对方的链表继续走。指针 pA走完 A切换到 B 指针 pB走完 B切换到 A关键两个指针走的总路程相同pA 走A B pB 走B A 总路程一样所以如果有交点一定同时到达图解情况1有交点A: a1 → a2 ↘ c1 → c2 → c3 B: b1 → b2 → b3 ↗ pA 路径a1 → a2 → c1 → c2 → c3 → b1 → b2 → b3 → c1 pB 路径b1 → b2 → b3 → c1 → c2 → c3 → a1 → a2 → c1 两个指针同时到达 c1 ✅情况2无交点A: a1 → a2 → a3 B: b1 → b2 pA 路径a1 → a2 → a3 → b1 → b2 → null pB 路径b1 → b2 → a1 → a2 → a3 → null 两个指针同时到达 null ✅public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA null || headB null) return null; ListNode pA headA; ListNode pB headB; while (pA ! pB) { // pA 走完 A 后切换到 B pA (pA null) ? headB : pA.next; // pB 走完 B 后切换到 A pB (pB null) ? headA : pB.next; } return pA; // 要么是交点要么是 null } }反转链表206. 反转链表 - 力扣LeetCode给你单链表的头节点head请你反转链表并返回反转后的链表。示例 1输入head [1,2,3,4,5]输出[5,4,3,2,1]示例 2输入head [1,2]输出[2,1]示例 3输入head []输出[]解法及思路双指针迭代用两个指针prev前一个节点curr当前节点每次循环1. 保存 curr.next因为要改 curr.next 2. 把 curr.next 指向 prev反转 3. prev 移到 curr 4. curr 移到 next输入1 → 2 → 3 → 4 → 5 → null初始prev null, curr 1 第1步 next 2 curr.next prev → 1 → null prev 1 curr 2 第2步 next 3 curr.next prev → 2 → 1 → null prev 2 curr 3 第3步 next 4 curr.next prev → 3 → 2 → 1 → null prev 3 curr 4 第4步 next 5 curr.next prev → 4 → 3 → 2 → 1 → null prev 4 curr 5 第5步 next null curr.next prev → 5 → 4 → 3 → 2 → 1 → null prev 5 curr null 循环结束curr null 返回 prev 5 结果5 → 4 → 3 → 2 → 1 → null ✅class Solution { public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; // 1. 保存下一个 curr.next prev; // 2. 反转指针 prev curr; // 3. prev 前移 curr next; // 4. curr 前移 } return prev; // prev 就是新头节点 } }回文链表234. 回文链表 - 力扣LeetCode给你一个单链表的头节点head请你判断该链表是否为回文链表。如果是返回true否则返回false。示例 1输入head [1,2,2,1]输出true示例 2输入head [1,2]输出false提示链表中节点数目在范围[1, 105]内0 Node.val 9解法及思路回文 前半部分和后半部分反转后相同。步骤1. 找到链表中间节点快慢指针 2. 反转后半部分 3. 比较前半部分和反转后的后半部分 4. 可选恢复链表输入1 → 2 → 2 → 1第1步找中间节点快慢指针 slow 每次走1步fast 每次走2步 1 → 2 → 2 → 1 s f 1 → 2 → 2 → 1 s f 1 → 2 → 2 → 1 s f fast到nullslow在中间第2步反转后半部分后半部分2 → 1 反转后1 → 2第3步比较前半部分1 → 2 后半部分1 → 2 相同 → 是回文 ✅/** * 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) { if(headnull||head.nextnull){ return true; } //快慢指针找中间节点 ListNode shead,fhead; while(f!nullf.next!null){ ss.next; ff.next.next; } //反转后半部分链表 ListNode prevnull; ListNode currs; while(curr!null){ ListNode nextcurr.next; curr.nextprev; prevcurr; currnext; } //比较前半部分和后半部分 ListNode p1head; ListNode p2prev; while(p2!null){ if(p1.val!p2.val){ return false; } p1p1.next; p2p2.next; } return true; } }环形链表141. 环形链表 - 力扣LeetCode给你一个链表的头节点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解释链表中没有环。解法及思路快慢指针用两个指针slow每次走 1 步fast每次走 2 步如果有环fast 一定会在环内追上 slow相遇。如果无环fast 会先走到 null。数学原理有环时 fast 进入环后每次比 slow 多走1步 环的长度有限fast 一定会在环内追上 slow 无环时 fast 先到达 null 循环结束返回 false环形链表||142. 环形链表 II - 力扣LeetCode给定一个链表的头节点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解释链表中没有环。解法及思路复制到B站【把环形链表讲清楚 如何判断环形链表如何找到环形链表的入口 LeetCode142.环形链表II】https://www.bilibili.com/video/BV1if4y1d7ob?vd_sourcef277644e2cb4e988bc39ab52a6327975算法思想使用快慢指针Floyd 判圈算法解决本题。设两个指针slow和fast起始都位于链表头部。随后slow每次向后移动1 个位置fast每次向后移动2 个位置如果链表中存在环则fast指针最终会再次与slow指针在环中相遇。如果fast走到链表末尾即fast或fast.next为空则说明链表中不存在环直接返回null。数学推导设链表中环外部分的长度为a从链表头部到入环点的距离。slow指针进入环后又走了b的距离与fast相遇。此时fast指针已经走完了环的n圈。因此slow走过的总距离为a bfast走过的总距离为a n(b c) b a (n 1)b nc其中c表示从相遇点继续向前走到入环点的距离环长L b c。根据题意任意时刻fast指针走过的距离都为slow指针的2 倍因此有a (n 1)b nc 2(a b)化简得a c (n - 1)(b c)结论有了a c (n - 1)(b c)的等量关系我们会发现从相遇点到入环点的距离加上n - 1圈的环长恰好等于从链表头部到入环点的距离。特别地当n 1时a c即从链表头部到入环点的距离等于从相遇点到入环点的距离。找入环点因此当发现slow与fast相遇时我们再额外使用一个指针ptrptr起始指向链表头部slow保持在相遇点随后ptr和slow每次同时向后移动一个位置由于a c (n - 1)(b c)ptr走完a步到达入环点时slow从相遇点出发也正好走完c (n - 1)(b c)步同样到达入环点。最终它们会在入环点相遇返回该节点即可。/** * 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) { if(headnull||head.nextnull){ return null; } ListNode slowhead,fasthead; while(fast!nullfast.next!null){ slowslow.next; fastfast.next.next; if(slowfast){ break;//相遇 } } // 无环 if (fast null || fast.next null) return null; // 第2步找入环点 slowhead; while(slow!fast){ slowslow.next; fastfast.next; } return slow; } }合并两个有序链表21. 合并两个有序链表 - 力扣LeetCode将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1输入l1 [1,2,4], l2 [1,3,4]输出[1,1,2,3,4,4]示例 2输入l1 [], l2 []输出[]示例 3输入l1 [], l2 [0]输出[0]解法及思路双指针 虚拟头节点。为什么用虚拟头节点合并时结果链表的第一个节点不确定是哪个 用 dummy 占位避免特殊处理第一个节点 最后返回 dummy.next步骤1. 创建虚拟头节点 dummycurr 指向 dummy 2. 双指针遍历两个链表 3. 每次选较小的节点接到 curr 后面 4. 一个链表遍历完把另一个剩下的接上 5. 返回 dummy.next输入1 → 2 → 4和1 → 3 → 4dummy → (-1) curr dummy p11, p21: 选p1 dummy → 1 p12 p12, p21: 选p2 dummy → 1 → 1 p23 p12, p23: 选p1 dummy → 1 → 1 → 2 p14 p14, p23: 选p2 dummy → 1 → 1 → 2 → 3 p24 p14, p24: 选p1 dummy → 1 → 1 → 2 → 3 → 4 p1null p1null把p2剩下的接上 dummy → 1 → 1 → 2 → 3 → 4 → 4 返回 dummy.next 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 mergeTwoLists(ListNode list1, ListNode list2) { //创建虚拟头结点 ListNode dummynew ListNode(0); ListNode currdummy; while(list1!nulllist2!null){ if(list1.vallist2.val){ curr.nextlist1; list1list1.next; }else{ curr.nextlist2; list2list2.next; } currcurr.next; } //把剩下的接上 curr.next(list1!null)?list1:list2; return dummy.next; } }两数相加2. 两数相加 - 力扣LeetCode给你两个非空的链表表示两个非负的整数。它们每位数字都是按照逆序的方式存储的并且每个节点只能存储一位数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 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]解法及思路模拟竖式加法和小学加法一样从最低位开始加处理进位。3 4 2 4 6 5 ------- 8 0 7链表是逆序的所以从头节点开始就是个位、十位、百位...2 → 4 → 3 个位2十位4百位3 5 → 6 → 4 个位5十位6百位4 257个位 4610十位进位1本位0 3418百位 结果7 → 0 → 8输入2 → 4 → 3和5 → 6 → 4dummy → null curr dummy carry 0 第1次 sum 2 5 0 7 carry 0 curr.next 7 l14, l26 第2次 sum 4 6 0 10 carry 1 curr.next 0 l13, l24 第3次 sum 3 4 1 8 carry 0 curr.next 8 l1null, l2null 第4次 l1null, l2null, carry0 退出循环 结果7 → 0 → 8class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy new ListNode(-1); ListNode curr dummy; 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; // 进位 curr.next new ListNode(sum % 10); // 本位 // 移动指针 curr curr.next; if (l1 ! null) l1 l1.next; if (l2 ! null) l2 l2.next; } return dummy.next; } }删除链表的倒数第N个结点19. 删除链表的倒数第 N 个结点 - 力扣LeetCode给你一个链表删除链表的倒数第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]解法及思路1. 反转链表 2. 删除正数第 n 个节点 3. 再反转头插回来为什么可行倒数第 n 个 反转后的正数第 n 个 反转 → 删除正数第 n 个 → 再反转 删除倒数第 n 个输入1 → 2 → 3 → 4 → 5n 2第1步反转 1 → 2 → 3 → 4 → 5 反转后5 → 4 → 3 → 2 → 1 第2步删除正数第2个即4 5 → 4 → 3 → 2 → 1 删除后5 → 3 → 2 → 1 第3步再反转 5 → 3 → 2 → 1 反转后1 → 2 → 3 → 5 ✅class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // 第1步反转 head reverse(head); // 第2步删除正数第 n 个 ListNode dummy new ListNode(0); dummy.next head; ListNode p dummy; for (int i 1; i n; i) { p p.next; } p.next p.next.next; // 第3步再反转 return reverse(dummy.next); } // 反转函数 private ListNode reverse(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; curr.next prev; prev curr; curr next; } return prev; } }两两交换链表中的节点24. 两两交换链表中的节点 - 力扣LeetCode给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。示例 1输入head [1,2,3,4]输出[2,1,4,3]示例 2输入head []输出[]示例 3输入head [1]输出[1]解法及思路核心用指针操作每两个节点交换一次。关键点1. 用 dummy 虚拟头节点简化头节点交换 2. 每次处理两个节点first 和 second 3. 交换后prev 指向交换后的第二个节点 4. 继续处理下一对输入1 → 2 → 3 → 4初始 dummy → 1 → 2 → 3 → 4 → null ↑ prev 第1次交换1和2 dummy → 2 → 1 → 3 → 4 → null ↑ prev 第2次交换3和4 dummy → 2 → 1 → 4 → 3 → null ↑ prev 结束返回 dummy.next 2class Solution { public ListNode swapPairs(ListNode head) { ListNode dummy new ListNode(0); dummy.next head; ListNode prev dummy; while (prev.next ! null prev.next.next ! null) { // 找到要交换的两个节点 ListNode first prev.next; ListNode second prev.next.next; // 交换 first.next second.next; second.next first; prev.next second; // prev 移动到交换后的第二个节点即原来的 first prev first; } return dummy.next; } }LRU缓存146. LRU 缓存 - 力扣LeetCode请你设计并实现一个满足 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解法及思路HashMap 双向链表为什么用这两个HashMapO(1) 查找 双向链表O(1) 插入删除维护访问顺序结构HashMap: key → Node 双向链表: 按访问顺序排列 头部最近访问的 尾部最久未访问的图解head ↔ 最近访问 ↔ ... ↔ 最久未访问 ↔ tail get(key)找到节点移到头部 put(key)插入/更新移到头部 容量满删除尾部节点class LRUCache { // 双向链表节点 class Node { int key, value; Node prev, next; Node(int key, int value) { this.key key; this.value value; } } private MapInteger, Node map; private Node head, tail; // 虚拟头尾节点 private int capacity; public LRUCache(int capacity) { this.capacity capacity; map new HashMap(); head new Node(-1, -1); tail new Node(-1, -1); head.next tail; tail.prev head; } public int get(int key) { if (!map.containsKey(key)) return -1; Node node map.get(key); moveToHead(node); // 移到头部最近使用 return node.value; } public void put(int key, int value) { if (map.containsKey(key)) { // 更新 Node node map.get(key); node.value value; moveToHead(node); } else { // 新增 if (map.size() capacity) { // 删除尾部最久未使用 Node last tail.prev; removeNode(last); map.remove(last.key); } Node node new Node(key, value); addToHead(node); map.put(key, node); } } // 移到头部 private void moveToHead(Node node) { removeNode(node); addToHead(node); } // 删除节点 private void removeNode(Node node) { node.prev.next node.next; node.next.prev node.prev; } // 添加到头部 private void addToHead(Node node) { node.next head.next; node.prev head; head.next.prev node; head.next node; } }
hot100——链表
相交链表160. 相交链表 - 力扣LeetCode给你两个单链表的头节点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输出No intersection解释从各自的表头开始算起链表 A 为 [2,6,4]链表 B 为 [1,5]。 由于这两个链表不相交所以 intersectVal 必须为 0而 skipA 和 skipB 可以是任意值。 这两个链表不相交因此返回 null 。解法及思路双指针两个指针分别从 A 和 B 出发走完自己的链表后切换到对方的链表继续走。指针 pA走完 A切换到 B 指针 pB走完 B切换到 A关键两个指针走的总路程相同pA 走A B pB 走B A 总路程一样所以如果有交点一定同时到达图解情况1有交点A: a1 → a2 ↘ c1 → c2 → c3 B: b1 → b2 → b3 ↗ pA 路径a1 → a2 → c1 → c2 → c3 → b1 → b2 → b3 → c1 pB 路径b1 → b2 → b3 → c1 → c2 → c3 → a1 → a2 → c1 两个指针同时到达 c1 ✅情况2无交点A: a1 → a2 → a3 B: b1 → b2 pA 路径a1 → a2 → a3 → b1 → b2 → null pB 路径b1 → b2 → a1 → a2 → a3 → null 两个指针同时到达 null ✅public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA null || headB null) return null; ListNode pA headA; ListNode pB headB; while (pA ! pB) { // pA 走完 A 后切换到 B pA (pA null) ? headB : pA.next; // pB 走完 B 后切换到 A pB (pB null) ? headA : pB.next; } return pA; // 要么是交点要么是 null } }反转链表206. 反转链表 - 力扣LeetCode给你单链表的头节点head请你反转链表并返回反转后的链表。示例 1输入head [1,2,3,4,5]输出[5,4,3,2,1]示例 2输入head [1,2]输出[2,1]示例 3输入head []输出[]解法及思路双指针迭代用两个指针prev前一个节点curr当前节点每次循环1. 保存 curr.next因为要改 curr.next 2. 把 curr.next 指向 prev反转 3. prev 移到 curr 4. curr 移到 next输入1 → 2 → 3 → 4 → 5 → null初始prev null, curr 1 第1步 next 2 curr.next prev → 1 → null prev 1 curr 2 第2步 next 3 curr.next prev → 2 → 1 → null prev 2 curr 3 第3步 next 4 curr.next prev → 3 → 2 → 1 → null prev 3 curr 4 第4步 next 5 curr.next prev → 4 → 3 → 2 → 1 → null prev 4 curr 5 第5步 next null curr.next prev → 5 → 4 → 3 → 2 → 1 → null prev 5 curr null 循环结束curr null 返回 prev 5 结果5 → 4 → 3 → 2 → 1 → null ✅class Solution { public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; // 1. 保存下一个 curr.next prev; // 2. 反转指针 prev curr; // 3. prev 前移 curr next; // 4. curr 前移 } return prev; // prev 就是新头节点 } }回文链表234. 回文链表 - 力扣LeetCode给你一个单链表的头节点head请你判断该链表是否为回文链表。如果是返回true否则返回false。示例 1输入head [1,2,2,1]输出true示例 2输入head [1,2]输出false提示链表中节点数目在范围[1, 105]内0 Node.val 9解法及思路回文 前半部分和后半部分反转后相同。步骤1. 找到链表中间节点快慢指针 2. 反转后半部分 3. 比较前半部分和反转后的后半部分 4. 可选恢复链表输入1 → 2 → 2 → 1第1步找中间节点快慢指针 slow 每次走1步fast 每次走2步 1 → 2 → 2 → 1 s f 1 → 2 → 2 → 1 s f 1 → 2 → 2 → 1 s f fast到nullslow在中间第2步反转后半部分后半部分2 → 1 反转后1 → 2第3步比较前半部分1 → 2 后半部分1 → 2 相同 → 是回文 ✅/** * 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) { if(headnull||head.nextnull){ return true; } //快慢指针找中间节点 ListNode shead,fhead; while(f!nullf.next!null){ ss.next; ff.next.next; } //反转后半部分链表 ListNode prevnull; ListNode currs; while(curr!null){ ListNode nextcurr.next; curr.nextprev; prevcurr; currnext; } //比较前半部分和后半部分 ListNode p1head; ListNode p2prev; while(p2!null){ if(p1.val!p2.val){ return false; } p1p1.next; p2p2.next; } return true; } }环形链表141. 环形链表 - 力扣LeetCode给你一个链表的头节点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解释链表中没有环。解法及思路快慢指针用两个指针slow每次走 1 步fast每次走 2 步如果有环fast 一定会在环内追上 slow相遇。如果无环fast 会先走到 null。数学原理有环时 fast 进入环后每次比 slow 多走1步 环的长度有限fast 一定会在环内追上 slow 无环时 fast 先到达 null 循环结束返回 false环形链表||142. 环形链表 II - 力扣LeetCode给定一个链表的头节点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解释链表中没有环。解法及思路复制到B站【把环形链表讲清楚 如何判断环形链表如何找到环形链表的入口 LeetCode142.环形链表II】https://www.bilibili.com/video/BV1if4y1d7ob?vd_sourcef277644e2cb4e988bc39ab52a6327975算法思想使用快慢指针Floyd 判圈算法解决本题。设两个指针slow和fast起始都位于链表头部。随后slow每次向后移动1 个位置fast每次向后移动2 个位置如果链表中存在环则fast指针最终会再次与slow指针在环中相遇。如果fast走到链表末尾即fast或fast.next为空则说明链表中不存在环直接返回null。数学推导设链表中环外部分的长度为a从链表头部到入环点的距离。slow指针进入环后又走了b的距离与fast相遇。此时fast指针已经走完了环的n圈。因此slow走过的总距离为a bfast走过的总距离为a n(b c) b a (n 1)b nc其中c表示从相遇点继续向前走到入环点的距离环长L b c。根据题意任意时刻fast指针走过的距离都为slow指针的2 倍因此有a (n 1)b nc 2(a b)化简得a c (n - 1)(b c)结论有了a c (n - 1)(b c)的等量关系我们会发现从相遇点到入环点的距离加上n - 1圈的环长恰好等于从链表头部到入环点的距离。特别地当n 1时a c即从链表头部到入环点的距离等于从相遇点到入环点的距离。找入环点因此当发现slow与fast相遇时我们再额外使用一个指针ptrptr起始指向链表头部slow保持在相遇点随后ptr和slow每次同时向后移动一个位置由于a c (n - 1)(b c)ptr走完a步到达入环点时slow从相遇点出发也正好走完c (n - 1)(b c)步同样到达入环点。最终它们会在入环点相遇返回该节点即可。/** * 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) { if(headnull||head.nextnull){ return null; } ListNode slowhead,fasthead; while(fast!nullfast.next!null){ slowslow.next; fastfast.next.next; if(slowfast){ break;//相遇 } } // 无环 if (fast null || fast.next null) return null; // 第2步找入环点 slowhead; while(slow!fast){ slowslow.next; fastfast.next; } return slow; } }合并两个有序链表21. 合并两个有序链表 - 力扣LeetCode将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1输入l1 [1,2,4], l2 [1,3,4]输出[1,1,2,3,4,4]示例 2输入l1 [], l2 []输出[]示例 3输入l1 [], l2 [0]输出[0]解法及思路双指针 虚拟头节点。为什么用虚拟头节点合并时结果链表的第一个节点不确定是哪个 用 dummy 占位避免特殊处理第一个节点 最后返回 dummy.next步骤1. 创建虚拟头节点 dummycurr 指向 dummy 2. 双指针遍历两个链表 3. 每次选较小的节点接到 curr 后面 4. 一个链表遍历完把另一个剩下的接上 5. 返回 dummy.next输入1 → 2 → 4和1 → 3 → 4dummy → (-1) curr dummy p11, p21: 选p1 dummy → 1 p12 p12, p21: 选p2 dummy → 1 → 1 p23 p12, p23: 选p1 dummy → 1 → 1 → 2 p14 p14, p23: 选p2 dummy → 1 → 1 → 2 → 3 p24 p14, p24: 选p1 dummy → 1 → 1 → 2 → 3 → 4 p1null p1null把p2剩下的接上 dummy → 1 → 1 → 2 → 3 → 4 → 4 返回 dummy.next 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 mergeTwoLists(ListNode list1, ListNode list2) { //创建虚拟头结点 ListNode dummynew ListNode(0); ListNode currdummy; while(list1!nulllist2!null){ if(list1.vallist2.val){ curr.nextlist1; list1list1.next; }else{ curr.nextlist2; list2list2.next; } currcurr.next; } //把剩下的接上 curr.next(list1!null)?list1:list2; return dummy.next; } }两数相加2. 两数相加 - 力扣LeetCode给你两个非空的链表表示两个非负的整数。它们每位数字都是按照逆序的方式存储的并且每个节点只能存储一位数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 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]解法及思路模拟竖式加法和小学加法一样从最低位开始加处理进位。3 4 2 4 6 5 ------- 8 0 7链表是逆序的所以从头节点开始就是个位、十位、百位...2 → 4 → 3 个位2十位4百位3 5 → 6 → 4 个位5十位6百位4 257个位 4610十位进位1本位0 3418百位 结果7 → 0 → 8输入2 → 4 → 3和5 → 6 → 4dummy → null curr dummy carry 0 第1次 sum 2 5 0 7 carry 0 curr.next 7 l14, l26 第2次 sum 4 6 0 10 carry 1 curr.next 0 l13, l24 第3次 sum 3 4 1 8 carry 0 curr.next 8 l1null, l2null 第4次 l1null, l2null, carry0 退出循环 结果7 → 0 → 8class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy new ListNode(-1); ListNode curr dummy; 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; // 进位 curr.next new ListNode(sum % 10); // 本位 // 移动指针 curr curr.next; if (l1 ! null) l1 l1.next; if (l2 ! null) l2 l2.next; } return dummy.next; } }删除链表的倒数第N个结点19. 删除链表的倒数第 N 个结点 - 力扣LeetCode给你一个链表删除链表的倒数第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]解法及思路1. 反转链表 2. 删除正数第 n 个节点 3. 再反转头插回来为什么可行倒数第 n 个 反转后的正数第 n 个 反转 → 删除正数第 n 个 → 再反转 删除倒数第 n 个输入1 → 2 → 3 → 4 → 5n 2第1步反转 1 → 2 → 3 → 4 → 5 反转后5 → 4 → 3 → 2 → 1 第2步删除正数第2个即4 5 → 4 → 3 → 2 → 1 删除后5 → 3 → 2 → 1 第3步再反转 5 → 3 → 2 → 1 反转后1 → 2 → 3 → 5 ✅class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // 第1步反转 head reverse(head); // 第2步删除正数第 n 个 ListNode dummy new ListNode(0); dummy.next head; ListNode p dummy; for (int i 1; i n; i) { p p.next; } p.next p.next.next; // 第3步再反转 return reverse(dummy.next); } // 反转函数 private ListNode reverse(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; curr.next prev; prev curr; curr next; } return prev; } }两两交换链表中的节点24. 两两交换链表中的节点 - 力扣LeetCode给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。示例 1输入head [1,2,3,4]输出[2,1,4,3]示例 2输入head []输出[]示例 3输入head [1]输出[1]解法及思路核心用指针操作每两个节点交换一次。关键点1. 用 dummy 虚拟头节点简化头节点交换 2. 每次处理两个节点first 和 second 3. 交换后prev 指向交换后的第二个节点 4. 继续处理下一对输入1 → 2 → 3 → 4初始 dummy → 1 → 2 → 3 → 4 → null ↑ prev 第1次交换1和2 dummy → 2 → 1 → 3 → 4 → null ↑ prev 第2次交换3和4 dummy → 2 → 1 → 4 → 3 → null ↑ prev 结束返回 dummy.next 2class Solution { public ListNode swapPairs(ListNode head) { ListNode dummy new ListNode(0); dummy.next head; ListNode prev dummy; while (prev.next ! null prev.next.next ! null) { // 找到要交换的两个节点 ListNode first prev.next; ListNode second prev.next.next; // 交换 first.next second.next; second.next first; prev.next second; // prev 移动到交换后的第二个节点即原来的 first prev first; } return dummy.next; } }LRU缓存146. LRU 缓存 - 力扣LeetCode请你设计并实现一个满足 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解法及思路HashMap 双向链表为什么用这两个HashMapO(1) 查找 双向链表O(1) 插入删除维护访问顺序结构HashMap: key → Node 双向链表: 按访问顺序排列 头部最近访问的 尾部最久未访问的图解head ↔ 最近访问 ↔ ... ↔ 最久未访问 ↔ tail get(key)找到节点移到头部 put(key)插入/更新移到头部 容量满删除尾部节点class LRUCache { // 双向链表节点 class Node { int key, value; Node prev, next; Node(int key, int value) { this.key key; this.value value; } } private MapInteger, Node map; private Node head, tail; // 虚拟头尾节点 private int capacity; public LRUCache(int capacity) { this.capacity capacity; map new HashMap(); head new Node(-1, -1); tail new Node(-1, -1); head.next tail; tail.prev head; } public int get(int key) { if (!map.containsKey(key)) return -1; Node node map.get(key); moveToHead(node); // 移到头部最近使用 return node.value; } public void put(int key, int value) { if (map.containsKey(key)) { // 更新 Node node map.get(key); node.value value; moveToHead(node); } else { // 新增 if (map.size() capacity) { // 删除尾部最久未使用 Node last tail.prev; removeNode(last); map.remove(last.key); } Node node new Node(key, value); addToHead(node); map.put(key, node); } } // 移到头部 private void moveToHead(Node node) { removeNode(node); addToHead(node); } // 删除节点 private void removeNode(Node node) { node.prev.next node.next; node.next.prev node.prev; } // 添加到头部 private void addToHead(Node node) { node.next head.next; node.prev head; head.next.prev node; head.next node; } }
