蓝桥杯 Java B 组之链表操作（单向链表增删查改）
Day 3：链表操作（单向链表增删查改）
一、链表（Linked List）基础
1. 什么是链表？
链表（Linked List）是一种动态数据结构，它由一系列节点（Node） 组成，每个节点包含：
- 数据域（value）：存储数据
- 指针域（next）：指向下一个节点的引用
链表与数组的主要区别：
| 特性 | 数组（Array） | 链表（Linked List） |
| 存储方式 | 连续存储 | 离散存储 |
| 插入/删除 | 慢（O(n)），需移动元素 | 快（O(1)），直接调整指针 |
| 随机访问 | 快（O(1)），直接通过索引访问 | 慢（O(n)），需遍历 |
| 扩展性 | 固定大小，扩展需新建数组 | 动态增长，无需预分配 |
二、单向链表的实现
1. 单向链表的基本操作
我们来手写一个 单向链表（Singly Linked List），支持以下操作：
- 插入（Insert）
- 删除（Delete）
- 查找（Search）
- 更新（Update）
- 遍历（Traversal）
// 定义链表节点类
class ListNode {
int value; // 数据域
ListNode next; // 指针域，指向下一个节点
public ListNode(int value) {
this.value = value;
this.next = null;
}
}
// 定义单向链表
class LinkedList {
private ListNode head; // 头指针
// 1. 头部插入（Insert at Head）
public void insertAtHead(int value) {
ListNode newNode = new ListNode(value);
newNode.next = head; // 新节点指向当前头节点
head = newNode; // 更新头指针
}
// 2. 末尾插入（Insert at Tail）
public void insertAtTail(int value) {
ListNode newNode = new ListNode(value);
if (head == null) {
head = newNode;
return;
}
ListNode current = head;
while (current.next != null) { // 遍历到尾节点
current = current.next;
}
current.next = newNode; // 尾节点指向新节点
}
// 3. 删除节点（Delete by Value）
public void deleteByValue(int value) {
if (head == null) return; // 链表为空
if (head.value == value) { // 头节点就是目标值
head = head.next;
return;
}
ListNode current = head;
while (current.next != null && current.next.value != value) {
current = current.next; // 寻找待删除节点的前一个节点
}
if (current.next != null) {
current.next = current.next.next; // 跳过待删除节点
}
}
// 4. 查找节点（Search）
public boolean search(int value) {
ListNode current = head;
while (current != null) {
if (current.value == value) {
return true;
}
current = current.next;
}
return false;
}
// 5. 更新节点（Update）
public void update(int oldValue, int newValue) {
ListNode current = head;
while (current != null) {
if (current.value == oldValue) {
current.value = newValue;
return;
}
current = current.next;
}
}
// 6. 遍历链表（Print List）
public void printList() {
ListNode current = head;
while (current != null) {
System.out.print(current.value + " -> ");
current = current.next;
}
System.out.println("null");
}
}
// 测试链表功能
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtHead(3);
list.insertAtHead(2);
list.insertAtHead(1);
list.printList(); // 1 -> 2 -> 3 -> null
list.insertAtTail(4);
list.insertAtTail(5);
list.printList(); // 1 -> 2 -> 3 -> 4 -> 5 -> null
list.deleteByValue(3);
list.printList(); // 1 -> 2 -> 4 -> 5 -> null
System.out.println(list.search(4)); // true
System.out.println(list.search(6)); // false
list.update(4, 10);
list.printList(); // 1 -> 2 -> 10 -> 5 -> null
}
}三、链表反转（Reverse a Linked List）
1. 题目描述
给定一个单向链表，反转整个链表，使得原来的 头节点变为尾节点，尾节点变为头节点。
2. 思路分析
使用 三个指针：
-
- prev（前驱）
- current（当前）
- next（后继）
逐个遍历链表，并 反转指针方向：
1 -> 2 -> 3 -> null
变成：
null <- 1 <- 2 <- 3
3. 代码实现
public class ReverseLinkedList {
public static ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode next = current.next; // 记录后继节点
current.next = prev; // 反转指针
prev = current; // 更新 prev
current = next; // 移动 current
}
return prev; // 返回新的头节点
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtHead(3);
list.insertAtHead(2);
list.insertAtHead(1);
list.printList(); // 1 -> 2 -> 3 -> null
list.head = reverse(list.head);
list.printList(); // 3 -> 2 -> 1 -> null
}
}- 时间复杂度：O(n)，需要遍历整个链表一次。
- 空间复杂度：O(1)，仅使用了额外的指针变量。
四、合并两个有序链表
1. 题目描述
给定两个递增排序的链表，合并它们成一个新的有序链表。
示例：
输入：
L1: 1 -> 3 -> 5
L2: 2 -> 4 -> 6
输出：
1 -> 2 -> 3 -> 4 -> 5 -> 6
2. 代码实现
public class MergeSortedLinkedList {
public static ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.value < l2.value) {
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;
}
}- 时间复杂度：O(n + m)，遍历两个链表一次。
- 空间复杂度：O(1)，不使用额外存储，仅修改指针。