leecodecode【反转链表+快慢指针】【2026.5.29打卡-java版本】

反转链表要点记录pre cur 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) { ListNode pre null; ListNode cur head; while(cur ! null){ ListNode next cur.next; cur.next pre; pre cur; cur next; } return pre; } }反转链表 II要点 哨兵 p0 反转链表【right-left1】 接上接来的/** * 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 reverseBetween(ListNode head, int left, int right) { //哨兵节点 ListNode dummy new ListNode(0,head); ListNode p0 dummy; for(int i 0; i left - 1; i){ p0 p0.next; } ListNode pre null; ListNode cur p0.next; for(int i 0; i right - left 1; i){ ListNode next cur.next; cur.next pre; pre cur; cur next; } p0.next.next cur; p0.next pre; return dummy.next; } }K 个一组翻转链表要点 记录链表长度哨兵 p0 反转链表【k】 接下面的/** * 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) { //记录长度 int n 0; for(ListNode cur head ; cur ! null; cur cur.next){ n; } ListNode dummy new ListNode(-1,head); ListNode p0 dummy; ListNode pre null; ListNode cur head; while(n k){ for(int i 0; ik; i){ ListNode next cur.next; cur.next pre; pre cur; cur next; } ListNode next p0.next; p0.next.next cur; p0.next pre; p0 next; nn-k; } return dummy.next; } }链表的中间结点要点 fast。 slow/** * 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 middleNode(ListNode head) { //快慢 ListNode slow head; ListNode fast head; while(fast ! null fast.next ! null){ slow slow.next; fast fast.next.next; } return slow; } }环形链表要点 fast slow 相等则有环/** * 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) { //套圈 ListNode slow head; ListNode fast head; while(fast ! null fast.next ! null){ slow slow.next; fast fast.next.next; if(slow fast){ return true; } } return false; } }环形链表 II要点slowfast 相等然后head和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) { //弗洛伊德圈 ListNode slow head; ListNode fast head; while(fast ! null fast.next ! null){ slow slow.next; fast fast.next.next; if(slow fast){ while(slow ! head){ slow slow.next; head head.next; } return slow; } } return null; } }重排链表要点 中间反转 nextnext2/** * 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 void reorderList(ListNode head) { //中间节点和反转链表 ListNode mid middle(head); ListNode head2 reverse(mid); while(head2.next ! null){ ListNode next head.next; ListNode next2 head2.next; // head2.next head.next; //head.next head2.next; head.next head2; head2.next next; head next; head2 next2; } } public ListNode middle(ListNode head){ ListNode slow head; ListNode fast head; while(fast ! null fast.next ! null){ slow slow.next; fast fast.next.next; } return slow; } public ListNode reverse(ListNode head){ ListNode pre null; ListNode cur head; while(cur ! null){ ListNode next cur.next; cur.next pre; pre cur; cur next; } return pre; } }随机知识String1.String 为什么被设计成不可变的String 的不可变体现在两个层面。第一个层面是底层存储JDK8 及之前用的是private final char[]JDK9 之后优化成了private final byte[]加上一个coder字段标识编码格式。这个数组被final修饰一旦在构造方法里赋值就不能再指向别的数组而且 String 类也没有提供任何能修改这个数组内容的方法substring、replace、trim这些看起来“修改”了字符串的方法其实全是返回一个new String。第二个层面是类本身被 final 修饰这意味着不能通过继承来覆盖它的方法也就不能从子类层面打破它的不可变性。为什么这么设计主要有四个好处。第一是线程安全。不可变对象天然就是线程安全的多个线程同时读同一个字符串不需要加锁不用担心内容被改掉。第二是字符串常量池。因为字符串不可变JVM 才能把内容相同的字符串在常量池里共享不同的引用可以指向在堆中的同一个字符串对象大幅节省内存。第三是作为 HashMap 的 key 更安全。因为内容不变hashCode 一旦计算出来就不会变可以被缓存下来。HashMap 在 put 和 get 时都要用 hashCode 来定位桶如果 key 的内容会变hashCode 跟着变那存进去就取不出来了甚至会造成内存泄漏。第四是安全性。类加载器、网络连接、文件路径这些系统核心功能很多都是把字符串当作参数传入的如果字符串可变就可能被篡改引发严重的安全问题。2.new String(hello) 创建了几个对象这个要分情况看。如果字符串常量池里已经有hello这个字符串了那么只会创建一个对象就是执行new String时在堆里新创建的那个 String 实例它底层的 value 数组也会指向常量池中hello的那个 char 数组不额外复制字符内容。如果常量池里还没有hello就会创建两个对象。第一个是在执行new String之前hello这个字面量本身会触发常量池的创建JVM 在常量池里放入一个hello字符串对象。第二个就是new String在堆上新创建的这个实例。所以总共两个对象一个在常量池一个在堆。这个区别的核心在于 JVM 对字符串字面量的处理机制所有双引号括起来的字面量在类加载的解析阶段就会被放入运行时常量池。3.String、StringBuilder、StringBuffer 区别这三者的核心区别可以归纳为两个维度可变性和线程安全性。String 不可变。每次对它做拼接、替换、截取这些操作实际上是创建了一个新的 String 对象原来的对象还在新对象被返回。所以在需要频繁拼接字符串的场景里比如循环里一直str abc每次循环都会在堆上产生一个新的字符串对象既浪费内存也给 GC 带来巨大压力。StringBuilder 可变线程不安全。它继承自AbstractStringBuilder内部是一个可扩容的 byte 数组append 的时候直接在原数组末尾追加容量不够了就扩容为原来两倍加二不会创建新对象。它的所有方法都没有同步关键字所以单线程下性能最高。StringBuffer 可变线程安全。它的方法和 StringBuilder 几乎一模一样只是每个公开方法都加了synchronized。所以多线程环境下用 StringBuffer 是安全的但单线程下不如 StringBuilder 快因为每次调用都有获取锁的开销。实际开发中的选择很简单如果字符串内容不需要变化用 String单线程下频繁拼接用 StringBuilder多线程下操作同一个字符串缓冲区用 StringBuffer。反转链表 前后指针算法笔记一、反转链表反转链表是链表操作的基础核心是改变节点的next指向。常见方法有迭代双指针、递归和头插法。1.1 迭代法双指针 临时指针思路维护三个指针prev已反转部分头节点、curr当前待反转节点、next保存原链下一个节点。每次将curr.next指向prev然后三个指针同步后移。伪代码textprev null curr head while curr ! null: next curr.next // 保存后继 curr.next prev // 反转指向 prev curr // 前移 curr next return prev // 新头复杂度时间 O(n)空间 O(1)关键点先保存next防止断链最终prev成为新头节点适用于单链表完全反转1.2 递归法思路假设reverse(head)返回反转后的新头节点。先递归反转head.next再将head.next的next指向head最后head.next null。伪代码textreverse(head): if head null or head.next null: return head newHead reverse(head.next) head.next.next head head.next null return newHead复杂度时间 O(n)空间 O(n)递归栈适用场景理解递归思想或面试要求实现递归版本实际工程中迭代更优。1.3 头插法虚拟头节点思路建立一个虚拟头节点dummy遍历原链表将每个节点插入到dummy之后最终dummy.next即为反转后链表。伪代码textdummy new ListNode(0) curr head while curr ! null: next curr.next curr.next dummy.next dummy.next curr curr next return dummy.next特点思想类似迭代法但明确使用辅助头节点便于理解。1.4 反转链表的常见变体问题核心方法关键点反转前 N 个节点递归 / 迭代 记录后继注意保存第 N1 个节点用于连接反转区间 [left, right]先定位到 left-1使用反转链表子函数切断并重连注意边界K 个一组反转分组 反转子链表 拼接需要记录上一组的尾和下一组的头回文链表判断快慢找中点 反转后半 比较可原地 O(1) 空间二、前后指针双指针双指针在链表中通常指快慢指针速度差或固定距离指针。这里“前后”涵盖两类一快一慢或一前一后保持固定步长。2.1 快慢指针速度差典型应用检测环、找中点、找环入口、找链表中某个特定位置。(1) 检测链表是否有环Floyd 判圈算法思路slow每次走 1 步fast每次走 2 步。若相遇则有环若fast走到 null 则无环。伪代码textslow fast head while fast ! null and fast.next ! null: slow slow.next fast fast.next.next if slow fast: return true return false(2) 找环的入口节点思路先找到相遇点然后slow从 head 开始fast从相遇点开始都以每次 1 步移动再次相遇点即为入口。原理设 head 到入口距离 a入口到相遇点 b相遇点回到入口 c满足 2(ab) a b c b ⇒ a c。(3) 找链表中点或中间节点思路slow每次 1 步fast每次 2 步。当fast到达末尾时slow恰好在中点偶数长度时偏左或偏右取决于需求。常用写法找中间偏左while fast ! null and fast.next ! null找中间偏右while fast ! null and fast.next ! null但初始fast head.next应用归并排序链表、回文链表断链。2.2 固定距离指针同速但有间距典型应用找倒数第 k 个节点、删除倒数第 k 个节点、链表中某个位置。删除/查找倒数第 k 个节点思路定义first和second初始都指向head。让first先走 k 步然后first和second同步走当first走到末尾时second指向倒数第 k 个节点或它的前驱。伪代码找倒数第 k 个textfirst second head for i in 1..k: first first.next while first ! null: first first.next second second.next return second注意若 k 等于链表长度需要特殊处理返回 head。2.3 双指针综合应用举例问题指针策略核心步骤回文链表快慢指针 反转后半链表1. 快慢找中点 2. 反转后半 3. 双指针比较相交链表找交点双指针交换路径pA, pB 分别遍历 AB相遇点即交点合并两个有序链表双指针分别遍历两个链表每次取较小节点尾插法连接删除排序链表中的重复元素 II快慢指针慢在待检查段前快扫描跳过重复段修改慢指针的 next旋转链表k 步右移双指针固定距离计算长度 → 成环 → 找新头的前驱 → 断开三、反转链表与前后指针的结合许多复杂链表问题需要同时使用反转链表和双指针典型如下回文链表判断力扣 234快慢指针找到中点反转后半部分链表双指针分别从头和后半头开始比较重排链表力扣 143快慢指针找中点分割成前后两半反转后半部分双指针交叉合并取一个前半取一个后半交替连接链表加法如逆序存储的两数相加若链表为正序存储可先反转两个链表再双指针逐位相加最后反转结果。四、常见易错点与技巧总结常见错误正确做法反转链表时忘记保存next进入循环立即next curr.next反转链表prev初始为null正确最后prev就是新头快慢指针处理空链表或单节点链表循环条件必须检查fast ! null fast.next ! null找倒数第 k 个节点时 k 可能大于链表长度先遍历统计长度或提前判断first是否越界断链操作后丢失尾节点使用临时指针或dummy节点辅助反转链表部分区间时边界节点未连接记录区间前驱和后继反转后重新连接五、思维框架速记表text反转链表 ├── 迭代双指针 → O(1)空间最常用 ├── 递归 → 理解思维实际少用 ├── 头插法 → 思路直观 └── 变体 → 前N个、区间、K组 双指针 ├── 快慢指针速度差 │ ├── 环检测 / 环入口 │ └── 找中点、分割链表 └── 固定距离指针同速差k步 ├── 倒数第k个节点 └── 旋转链表、删除节点 结合场景 ├── 回文链表 ├── 重排链表 ├── 正序加法 └── 有序链表合并总结反转链表的核心是改变指针方向双指针的核心是利用速度差或固定间隔在一次遍历中定位特殊节点。掌握这两类基础算法能够解决链表 80% 的常见问题。多画图模拟指针移动避免断链和死循环。碎碎念后续会更新每天学习的八股和算法 题开始准备秋招的第19天。努力连续更新100天以后每天就按秋招项目【javaagent】科研必做项目算法八股锻炼身体来总结。总结今天效率巨低还是算法题及时反馈感强不想学其他的不行以后要以程序员为职业首先就是要热爱代码呀加油加油加油1.算法要系统过一遍【灵神】7/27【早上加晚上】3h2.秋招项目【java】开始实际看业务2.9/10【agent】还在学决定把helloagent看一遍5/163.科研要跑一下无4.检测项目也得总结文档无5.训练项目看看先选择好4h6.背八股无7.锻炼身体无今天周五稍微休息一下下吃了点好吃的看浪姐【明天也争取正常起床】