异常教程
Java 实例 – 链表修改（长文解析）
💡一则或许对你有用的小广告
欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论
- 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于
Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;演示链接： http://116.62.199.48:7070 ;- 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;
截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观
在 Java 编程中，链表作为动态数据结构的核心实现方式之一，其修改操作是算法与数据结构学习的重要环节。无论是实现缓存机制、解析表达式，还是构建复杂算法，链表的增删改查能力都至关重要。本文将以 “Java 实例 – 链表修改” 为主题，通过循序渐进的案例解析与代码示例，帮助读者掌握链表修改的核心逻辑，同时结合实际场景提升问题解决能力。
链表的基础概念与结构
什么是链表？
链表是一种通过节点（Node）组成的线性数据结构，每个节点包含 数据域 和 指针域（指向下一个节点的引用）。想象一个快递运输系统：每个快递包裹（节点）上都标注了下一个包裹的存放位置（指针），这种设计使得链表能够灵活地插入或删除元素，而无需像数组那样整体移动数据。
链表与数组的对比
通过表格对比链表与数组的特性：
| 特性 | 链表 | 数组 |
|---------------|-----------------------|-----------------------|
| 空间连续性 | 不需要连续内存空间 | 需要连续内存空间 |
| 插入/删除效率 | 高（仅修改指针） | 低（需移动元素） |
| 随机访问 | 低（需遍历） | 高（O(1) 时间访问） |
节点的 Java 实现
链表的基础是节点类，其代码结构如下：
class ListNode {
int data;
ListNode next; // 指向下一个节点的引用
public ListNode(int data) {
this.data = data;
this.next = null;
}
}
这里 next 是关键属性，它决定了链表的连接方式。
链表修改的核心操作
1. 插入节点
插入操作是链表修改的常见场景，包括 头插法、尾插法和中间插入。
头插法示例
假设现有链表为 1 -> 2 -> 3，插入节点 0 到头部：
public void insertAtHead(ListNode head, int newData) {
ListNode newNode = new ListNode(newData);
newNode.next = head;
head = newNode; // 更新头节点引用
}
比喻：如同在火车头部插入一节新车厢，只需调整头车的指向即可，无需移动其他车厢。
尾插法示例
插入节点到链表尾部时，需遍历链表找到尾节点：
public void insertAtTail(ListNode head, int newData) {
ListNode newNode = new ListNode(newData);
if (head == null) {
head = newNode;
return;
}
ListNode current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
关键点：遍历时需从头节点开始，逐个检查 next 是否为 null。
2. 删除节点
删除操作需找到目标节点的前驱节点，并调整指针。例如删除链表 1 -> 2 -> 3 中的 2：
public void deleteNode(ListNode head, int target) {
if (head == null) return;
if (head.data == target) { // 删除头节点
head = head.next;
return;
}
ListNode current = head;
while (current.next != null && current.next.data != target) {
current = current.next;
}
if (current.next != null) {
current.next = current.next.next;
}
}
注意事项：删除头节点时需直接修改头指针；若未找到目标节点，需避免空指针异常。
3. 反转链表
反转链表是经典算法题，通过调整指针方向实现：
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextTemp = current.next; // 保存下一节点
current.next = prev; // 反转指针
prev = current; // 移动指针向前
current = nextTemp;
}
return prev; // 新的头节点
}
比喻：如同将一串项链翻转，每一步都需将当前珠子的“方向”指向之前的部分。
实战案例与代码解析
案例 1：实现带头节点的链表
定义一个链表类 LinkedList，包含插入、删除和反转功能：
class LinkedList {
private ListNode head;
public void insert(int data) {
// 实现尾插法
}
public void delete(int data) {
// 实现删除操作
}
public ListNode reverse() {
// 实现反转逻辑
return reverseList(head);
}
}
通过封装，开发者可直接调用 insert() 或 reverse() 方法完成复杂操作。
案例 2：合并两个有序链表
假设两个链表分别为 1 -> 3 -> 5 和 2 -> 4 -> 6，合并后为 1 -> 2 -> 3 -> 4 -> 5 -> 6：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0); // 虚拟头节点
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.data < l2.data) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 != null ? l1 : l2;
return dummy.next;
}
技巧：使用“虚拟头节点”简化代码逻辑，避免单独处理头节点。
进阶技巧与优化
1. 时间与空间复杂度分析
- 插入操作：尾插法需遍历链表，时间复杂度为 O(n)；头插法为 O(1)。
- 删除操作：需遍历到目标节点的前驱，最坏情况下 O(n)。
- 反转链表：遍历所有节点，时间复杂度 O(n)。
2. 遍历技巧：迭代 vs 递归
迭代法：通过循环逐步调整指针，适合内存敏感场景。
递归法：例如反转链表的递归实现：
public ListNode reverseRecursively(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseRecursively(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
缺点：递归可能导致栈溢出，链表过长时需谨慎使用。
3. 避免常见错误
- 空指针异常：操作前需检查节点是否为
null。 - 指针循环：修改指针时需确保不形成闭环，例如删除节点时忘记断开原指针。
总结与延伸思考
本文通过 “Java 实例 – 链表修改” 的主题，系统讲解了链表的核心操作、代码实现与优化技巧。关键要点包括：
- 链表的节点结构与动态特性；
- 插入、删除、反转等操作的指针调整逻辑；
- 迭代与递归方法的权衡。
延伸思考：
- 双向链表（每个节点包含前驱和后继指针）如何实现修改操作？
- 如何使用链表实现 LRU 缓存算法？
掌握链表修改的底层逻辑，不仅能解决基础算法题，更能为后续学习更复杂的结构（如图、树）奠定基础。通过实践与案例分析，开发者可逐步提升对动态数据结构的掌控能力。