蓝桥杯 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 -> nulllist.insertAtTail(4);list.insertAtTail(5);list.printList();  // 1 -> 2 -> 3 -> 4 -> 5 -> nulllist.deleteByValue(3);list.printList();  // 1 -> 2 -> 4 -> 5 -> nullSystem.out.println(list.search(4));  // trueSystem.out.println(list.search(6));  // falselist.update(4, 10);list.printList();  // 1 -> 2 -> 10 -> 5 -> null}}

三、链表反转（Reverse a Linked List）

1. 题目描述

给定一个单向链表，反转整个链表，使得原来的 头节点变为尾节点，尾节点变为头节点。

2. 思路分析

使用 三个指针：

1. prev（前驱）
2. current（当前）
3. 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;  // 更新 prevcurrent = 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 -> nulllist.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;}}