反转链表

要点：记录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 步右移）	双指针（固定距离）	计算长度 → 成环 → 找新头的前驱 → 断开

---

三、反转链表与前后指针的结合

许多复杂链表问题需要同时使用 反转链表 和 双指针，典型如下：

1. 回文链表判断（力扣 234）

   • 快慢指针找到中点

   • 反转后半部分链表

   • 双指针分别从头和后半头开始比较

2. 重排链表（力扣 143）

   • 快慢指针找中点，分割成前后两半

   • 反转后半部分

   • 双指针交叉合并（取一个前半，取一个后半，交替连接）

3. 链表加法（如逆序存储的两数相加）
   若链表为正序存储，可先反转两个链表，再双指针逐位相加，最后反转结果。

---

四、常见易错点与技巧总结

常见错误	正确做法
反转链表时忘记保存 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.锻炼身体，无

今天周五稍微休息一下下，吃了点好吃的，看浪姐

【明天也争取正常起床】