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),不使用额外存储,仅修改指针。