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-left+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 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; i<k; 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; n=n-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
要点：slow，fast， 相等然后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; } }重排链表
要点： 中间+反转+ next，next2
/** * 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; } }随机知识
String
1.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，然后三个指针同步后移。
伪代码：
text
prev = 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。
伪代码：
text
reverse(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即为反转后链表。
伪代码：
text
dummy = 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 个节点 | 递归 / 迭代 + 记录后继 | 注意保存第 N+1 个节点用于连接 |
| 反转区间 [left, right] | 先定位到 left-1，使用反转链表子函数 | 切断并重连，注意边界 |
| K 个一组反转 | 分组 + 反转子链表 + 拼接 | 需要记录上一组的尾和下一组的头 |
| 回文链表判断 | 快慢找中点 + 反转后半 + 比较 | 可原地 O(1) 空间 |
二、前后指针（双指针）
双指针在链表中通常指快慢指针（速度差）或固定距离指针。这里“前后”涵盖两类：一快一慢，或一前一后保持固定步长。
2.1 快慢指针（速度差）
典型应用：检测环、找中点、找环入口、找链表中某个特定位置。
(1) 检测链表是否有环（Floyd 判圈算法）
思路：slow每次走 1 步，fast每次走 2 步。若相遇则有环；若fast走到 null 则无环。
伪代码：
text
slow = 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(a+b) = 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 个）：
text
first = 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 分别遍历 A+B，相遇点即交点 |
| 合并两个有序链表 | 双指针分别遍历两个链表 | 每次取较小节点，尾插法连接 |
| 删除排序链表中的重复元素 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天！以后每天就按，秋招项目【java+agent】，科研，必做项目，算法，八股，锻炼身体来总结。
总结：今天效率巨低，还是算法题及时反馈感强，不想学其他的，不行！以后要以程序员为职业，首先就是要热爱代码呀！！！！！加油加油加油
1.算法要系统过一遍【灵神】7/27【早上加晚上】3h
2.秋招项目，【java】开始实际看业务，2.9/10；
【agent】还在学，决定把helloagent看一遍，5/16；
3.科研要跑一下，无
4.检测项目也得总结文档，无，
5.训练项目看看先选择好，4h，
6.背八股，无
7.锻炼身体，无
今天周五稍微休息一下下，吃了点好吃的，看浪姐
【明天也争取正常起床】