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. 思路分析
使用 三个指针：
-
- 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; // 更新 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;}}- 时间复杂度：O(n + m)，遍历两个链表一次。
- 空间复杂度：O(1)，不使用额外存储，仅修改指针。
