蓝桥杯 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;}}
  • 时间复杂度:O(n + m),遍历两个链表一次。
  • 空间复杂度:O(1),不使用额外存储,仅修改指针。


常考点:

链表反转:理解如何通过指针操作反转链表。

合并有序链表:理解如何合并两个有序链表。

链表的基本操作:插入、删除、查找、修改节点。

指针操作:理解指针的移动和修改。

易错点:

指针操作错误:容易在指针操作时忘记更新指针,导致链表断裂。

边界条件:容易忽略链表为空或只有一个节点的情况。

链表断裂:在删除或插入节点时,容易忘记更新前一个节点的指针。

合并链表时的剩余部分:容易忘记将剩余部分接到结果链表的末尾。 五、总结与易错点

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/19907.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

gitee SSH 公钥设置教程

Gitee 提供了基于 SSH 协议的 Git 服务,在使用 SSH 协议访问仓库仓库之前,需要先配置好账户 SSH 公钥。 1、生成秘钥 Windows 用户建议使用 Windows PowerShell 或者 Git Bash,在 命令提示符 下无 cat 和 ls 命令。 ssh-keygen -t ed25519 -C "Gitee SSH Key"中间…

jenkins war Windows安装

Windows安装Jenkins 需求1.下载jenkins.war2.编写快速运行脚本3.启动Jenkins4.Jenkins使用 需求 1.支持在Windows下便捷运行Jenkins&#xff1b; 2.支持自定义启动参数&#xff1b; 3.有快速运行的脚步样板。 1.下载jenkins.war Jenkins下载地址&#xff1a;https://get.j…

string类详解(上)

文章目录 目录1. STL简介1.1 什么是STL1.2 STL的版本1.3 STL的六大组件 2. 为什么学习string类3. 标准库中的string类3.1 string类3.2 string类的常用接口说明 目录 STL简介为什么学习string类标准库中的string类string类的模拟实现现代版写法的String类写时拷贝 1. STL简介 …

[数据结构]红黑树,详细图解插入

目录 一、红黑树的概念 二、红黑树的性质 三、红黑树节点的定义 四、红黑树的插入&#xff08;步骤&#xff09; 1.为什么新插入的节点必须给红色&#xff1f; 2、插入红色节点后&#xff0c;判定红黑树性质是否被破坏 五、插入出现连续红节点情况分析图解&#xff08;看…

java练习(28)

ps&#xff1a;练习来自力扣 给定一个二叉树&#xff0c;判断它是否是平衡二叉树 // 定义二叉树节点类 class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val val; }TreeNode(int val, TreeNode left, TreeNode right) {this.va…

Java并发编程6--重排序

重排序是指 编译 器和 处 理器 为 了 优 化程序性能而 对 指令序列 进 行重新排序的一种手段。 1.数据依赖性 如果两个操作 访问 同一个 变 量&#xff0c;且 这 两个操作中有一个 为 写操作&#xff0c;此 时这 两个操作之 间就存在数据 依赖性。 数据依赖的类型 上面 3 种情…

ElasticSearch映射分词

目录 弃用Type why 映射 查询 mapping of index 创建 index with mapping 添加 field with mapping 数据迁移 1.新建 一个 index with correct mapping 2.数据迁移 reindex data into that index 分词 POST _analyze 自定义词库 ik分词器 circuit_breaking_excep…

Python 面向对象的三大特征

前言&#xff1a;本篇讲解面向对象的三大特征&#xff08;封装&#xff0c;继承&#xff0c;多态&#xff09;&#xff0c;还有比较细致的&#xff08;类属性类方法&#xff0c;静态方法&#xff09;&#xff0c;分步骤讲解&#xff0c;比较适合理清楚三大特征的思路 面向对象的…

deepseek多列数据对比,联想到excel的高级筛选功能

目录 1 业务背景 ​2 deepseek提示词输入 ​3 联想分析 4 EXCEL高级搜索 1 业务背景 系统上线的时候经常会遇到一个问题&#xff0c;系统导入的数据和线下的EXCEL数据是否一致&#xff0c;如果不一致&#xff0c;如何快速找到差异值&#xff0c;原来脑海第一反应就是使用公…

俄罗斯方块游戏完整代码示例

以下是一个基于Cocos Creator引擎开发的俄罗斯方块游戏的完整代码示例。该游戏实现了俄罗斯方块的基本功能&#xff0c;并且代码整合在单个文件中&#xff0c;无需任何外部依赖&#xff0c;可以直接在浏览器中运行。 1. 创建Cocos Creator项目 首先&#xff0c;确保你已经安装了…

java后端开发day16--字符串(二)

&#xff08;以下内容全部来自上述课程&#xff09; 1.StringBuilder 因为StringBuilder是Java已经写好的类。 java在底层对他进行了一些特殊处理。 打印对象不是地址值而是属性值。 1.概述 StringBuilder可以看成是一个容器&#xff0c;创建之后里面的内容是可变的。 作用…

【AI实践】deepseek支持升级git

当前Windows 11 WSL的git是2.17&#xff0c;Android Studio提示需要升级到2.19版本 网上找到指导文章 安装git 2.19.2 cd /usr/src wget https://www.kernel.org/pub/software/scm/git/git-2.19.2.tar.gz tar xzf git-2.19.2.tar.gz cd git-2.19.2 make prefix/usr/l…

从零复现R1之路[3/3]:一文速览Open R1——对DeepSeek R1训练流程前两个阶段的复现(SFT和GRPO训练)

前言 根据R1的GitHub可知 类别开源内容未开源内容模型权重R1、R1-Zero 及蒸馏模型权重&#xff08;MIT 协议&#xff09;原始训练数据 未公开冷启动数据、RL 训练数据集或合成数据的具体内容&#xff0c;仅提供依赖的公开数据集名称&#xff08;如 AI-MO、NuminaMath-TIR&…

大语言模型简史:从Transformer(2017)到DeepSeek-R1(2025)的进化之路

2025年初&#xff0c;中国推出了具有开创性且高性价比的「大型语言模型」&#xff08;Large Language Model — LLM&#xff09;DeepSeek-R1&#xff0c;引发了AI的巨大变革。本文回顾了LLM的发展历程&#xff0c;起点是2017年革命性的Transformer架构&#xff0c;该架构通过「…

在线考试系统(代码+数据库+LW)

摘 要 使用旧方法对在线考试系统的信息进行系统化管理已经不再让人们信赖了&#xff0c;把现在的网络信息技术运用在在线考试系统的管理上面可以解决许多信息管理上面的难题&#xff0c;比如处理数据时间很长&#xff0c;数据存在错误不能及时纠正等问题。这次开发的在线考试…

2025百度快排技术分析:模拟点击与发包算法的背后原理

一晃做SEO已经15年了&#xff0c;2025年还有人问我如何做百度快速排名&#xff0c;我能给出的答案就是&#xff1a;做好内容的前提下&#xff0c;多刷刷吧&#xff01;百度的SEO排名算法一直是众多SEO从业者研究的重点&#xff0c;模拟算法、点击算法和发包算法是百度快速排名的…

【Spring+MyBatis】留言墙的实现

目录 1. 添加依赖 2. 配置数据库 2.1 创建数据库与数据表 2.2 创建与数据库对应的实体类 3. 后端代码 3.1 目录结构 3.2 MessageController类 3.3 MessageService类 3.4 MessageMapper接口 4. 前端代码 5. 单元测试 5.1 后端接口测试 5.2 使用前端页面测试 在Spri…

EtherNet/IP转Modbus TCP:新能源风电监控与分析实用案例

EtherNet/IP转Modbus TCP&#xff1a;新能源风电监控与分析实用案例 一、案例背景 在某新能源汽车电池生产线上&#xff0c;需要将采用EtherNet/IP协议的电池检测设备与采用ProfiNet协议的生产线控制系统进行集成&#xff0c;以实现对电池生产过程的全面监控和数据采集。 二、…

管理WSL实例 以及安装 Ubuntu 作为 WSL 子系统 流程

安装ubuntu wsl --install -d Ubuntu分类命令说明安装相关wsl --install在 Windows 10/11 上以管理员身份在 PowerShell 中运行此命令&#xff0c;可安装 WSLwsl --install -d <distribution name>在 PowerShell 中使用此命令安装特定版本的 Linux 发行版&#xff0c;如…

Spring框架中都用到了哪些设计模式?

大家好&#xff0c;我是锋哥。今天分享关于【Spring框架中都用到了哪些设计模式&#xff1f;】面试题。希望对大家有帮助&#xff1b; Spring框架中都用到了哪些设计模式&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 Spring框架中使用了大量的设计模…