单链表的应用
文章目录
- 目录
- 1. 单链表经典算法OJ题目
- 1.1 [移除链表元素](https://leetcode.cn/problems/remove-linked-list-elements/description/)
- 1.2 [链表的中间节点](https://leetcode.cn/problems/middle-of-the-linked-list/description/)
- 1.3 [反转链表](https://leetcode.cn/problems/reverse-linked-list/description/)
- 1.4 [合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists/description/)
- 1.5 [分割链表](https://leetcode.cn/problems/partition-list-lcci/description/)
- 1.6 [环形链表的约瑟夫问题](https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a)
- 2. 基于单链表再实现通讯录项目
目录
- 单链表经典算法OJ题目
- 基于单链表再实现通讯录项目
1. 单链表经典算法OJ题目
1.1 移除链表元素
#include <stdio.h>typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;struct ListNode* removeElements(struct ListNode* head, int val)
{//定义新链表的头尾指针ListNode* newHead, * newTail;newHead = newTail = NULL;ListNode* pcur = head;while (pcur){//不是val,尾插到新链表if (pcur->val != val){if (NULL == newHead){//链表为空newHead = newTail = pcur;}else{//链表不为空newTail->next = pcur;newTail = newTail->next;}pcur = pcur->next;}else{ListNode* del = pcur;pcur = pcur->next;free(del);del = NULL;}}if (newTail)//为了防止传过来的是空链表,newTail为空;或者链表中都是同一个值,而正好删除的是这个值,删完之后新链表中newTail依然是空{newTail->next = NULL;}return newHead;
}
1.2 链表的中间节点
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;struct ListNode* middleNode(struct ListNode* head)
{ListNode* slow, * fast;slow = fast = head;//满足任意一个条件就跳出循环while (fast && fast->next)//有一个为假都不应该进入循环{//慢指针每次走一步,快指针每次走两步slow = slow->next;fast = fast->next->next;}return slow;
}
1.3 反转链表
#include <stdio.h>typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;struct ListNode* reverseList(struct ListNode* head)
{//处理空链表if (NULL == head){return head;}//先创建三个指针ListNode* n1, * n2, * n3;n1 = NULL, n2 = head, n3 = head->next;//遍历原链表,修改节点指针的指向while (n2){//修改n2的指向n2->next = n1;//修改三个指针的位置n1 = n2;n2 = n3;if (n3){n3 = n3->next;}}return n1;
}
1.4 合并两个有序链表
#include <stdio.h>typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if (NULL == list1){return list2;}if (NULL == list2){return list1;}ListNode* l1, * l2;l1 = list1, l2 = list2;ListNode* newHead, * newTail;newHead = newTail = NULL;while (l1 && l2){if (l1->val < l2->val){//l1小,插入到新链表中if (NULL == newHead){//链表为空,头尾指针都指向该节点newHead = newTail = l1;}else{//链表不为空newTail->next = l1;newTail = newTail->next;}l1 = l1->next;}else{//l2小,插入到新链表中if (NULL == newHead){//链表为空newHead = newTail = l2;}else{//链表不为空newTail->next = l2;newTail = newTail->next;}l2 = l2->next;}}//跳出循环存在两种情况:要么l1走到空了l2不为空,要么l2走到空了l1不为空//不可能存在都为空的情况if (l1){newTail->next = l1;}if (l2){newTail->next = l2;}return newHead;
}
但是我们会发现以上代码在l1小或l2小时把数据插入到新链表中都要判断链表是否为空,出现了代码的重复,我们应该如何优化呢?
代码重复的根源在于链表可能会出现为空的情况,那么我们就创建一个头节点(这里的头就是带头链表中的头,是哨兵位,不存储有效的数值),让链表不可能存在为空的情况,就可以避免代码重复。
#include <stdio.h>
#include <stdlib.h>typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if (NULL == list1){return list2;}if (NULL == list2){return list1;}ListNode* l1, * l2;l1 = list1, l2 = list2;ListNode* newHead, * newTail;newHead = newTail = (ListNode*)malloc(sizeof(ListNode));while (l1 && l2){if (l1->val < l2->val){//l1小,插入到新链表中newTail->next = l1;newTail = newTail->next;l1 = l1->next;}else{//l2小,插入到新链表中newTail->next = l2;newTail = newTail->next;l2 = l2->next;}}//跳出循环存在两种情况:要么l1走到空了l2不为空,要么l2走到空了l1不为空//不可能存在都为空的情况if (l1){newTail->next = l1;}if (l2){newTail->next = l2;}//malloc了空间,但是这块空间实际用不了,应该将其释放掉ListNode* ret = newHead->next;free(newHead);newHead = newTail = NULL;return ret;
}
1.5 分割链表
#include <stdio.h>
#include <stdlib.h>typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;struct ListNode* partition(struct ListNode* head, int x)
{if (NULL == head){return head;}//创建带头的大小链表ListNode* lessHead, * lessTail;ListNode* greaterHead, * greaterTail;lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));//遍历原链表,将节点放到对应的新链表中ListNode* pcur = head;while (pcur){if (pcur->val < x){//放到小链表中lessTail->next = pcur;lessTail = lessTail->next;}else{//放到大链表中greaterTail->next = pcur;greaterTail = greaterTail->next;}pcur = pcur->next;}greaterTail->next = NULL;//大小链表进行首尾相连lessTail->next = greaterHead->next;ListNode* ret = lessHead->next;free(greaterHead);greaterHead = greaterTail = NULL;free(lessHead);lessHead = lessTail = NULL;return ret;
}
1.6 环形链表的约瑟夫问题
著名的Josephus问题:
据说著名犹太历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到⼀个洞中,39个犹太人决定宁愿死也不要被人抓到,于是决定了一个自杀方式,41个人排成⼀个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下⼀个重新报数,直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
#include <stdio.h>
#include <stdlib.h>typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;ListNode* BuyNode(int x)
{ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));if (NULL == newNode){perror("BuyNode");exit(1);}newNode->val = x;newNode->next = NULL;return newNode;
}ListNode* createList(int n)
{ListNode* phead = BuyNode(1);ListNode* ptail = phead;for (int i = 2; i <= n; i++){ptail->next = BuyNode(i);ptail = ptail->next;}//链表要首尾相连使其循环起来ptail->next = phead;return ptail;//返回ptail的目的是避免prev为空,解决m = 1时出现的问题;这样写既能知道第一个节点的前驱节点,也能够通过尾节点找到第一个节点
}int ysf(int n, int m)
{//创建不带头单向循环链表ListNode* prev = createList(n);//定义prev来接收尾节点指针//逢m删除节点ListNode* pcur = prev->next;int count = 1;while (pcur->next != pcur){if (m == count){//删除当前节点pcurprev->next = pcur->next;free(pcur);//删除pcur节点之后,要让pcur走到新的位置,count置为初始值pcur = prev->next;count = 1;}else{//pcur往后走prev = pcur;pcur = pcur->next;count++;}}//此时pcur节点就是幸存下来的唯一的一个节点return pcur->val;
}
2. 基于单链表再实现通讯录项目
这里基于单链表实现通讯录项目和之前基于顺序表实现通讯录项目的步骤大致相同,思路是相通的,因此可以参考之前顺序表的应用这篇文章。
相关文章:

单链表的应用
文章目录 目录1. 单链表经典算法OJ题目1.1 [移除链表元素](https://leetcode.cn/problems/remove-linked-list-elements/description/)1.2 [链表的中间节点](https://leetcode.cn/problems/middle-of-the-linked-list/description/)1.3 [反转链表](https://leetcode.cn/problem…...

手机副业赚钱秘籍:让你的手机变成赚钱利器
当今社会,智能手机已然成为我们生活不可或缺的一部分。随着技术的飞速进步,手机不再仅仅是通讯工具,而是化身为生活伴侣与工作助手。在这个信息爆炸的时代,我们时常会被一种焦虑感所困扰:如何能让手机超越消磨时光的定…...
(二十七)Flask之数据库连接池DBUtils库
目录: 每篇前言:DBUtils库模式一(底层使用threading.local实现):模式二:Flask中使用方式一:直接将DBUtils初始化放到settings.py文件中方式二:从utils文件夹中导入脚本使用DBUtils代码demo:每篇前言: 🏆🏆作者介绍:【孤寒者】—CSDN全栈领域优质创作者、HDZ核心…...
FewShotPromptTemplate和SemanticSimilarityExampleSelector的学习
FewShotPromptTemplate 和 SemanticSimilarityExampleSelector 是在少样本学习(FewShot Learning)场景中常用的两种技术,它们在提高模型泛化能力和减少对大量标注数据的依赖方面扮演着重要角色。 下面我会解释它们之间的关系: F…...

【保姆级】2024年OnlyFans订阅指南
OnlyFans是一个独特的社交媒体平台,它为创作者和粉丝提供了一个互动交流的空间。通过这个平台,创作者可以分享他们的独家内容,而粉丝则可以通过订阅来支持和享受这些内容。如果你对OnlyFans感兴趣,并希望成为其中的一员࿰…...

深入理解JVM中的G1垃圾收集器原理、过程和参数配置
码到三十五 : 个人主页 心中有诗画,指尖舞代码,目光览世界,步履越千山,人间尽值得 ! 在Java虚拟机(JVM)中,垃圾收集(GC)是一个自动管理内存的过程ÿ…...

VUE3 + Elementui-Plus 之 树形组件el-tree 一键展开(收起);一键全选(不全选)
需求: 产品要求权限树形结构添加外部复选框进行全部展开或收起;全选或不全选。 实现步骤: tree组件部分: <div class"role-handle"><div>权限选择(可多选)</div><div><el-checkbox v-mode…...

【Godot4自学手册】第三十七节钥匙控制开门
有些日子没有更新了,实在是琐事缠身啊,今天继续开始自学Godot4,继续完善地宫相关功能,在地宫中安装第二道门,只有主人公拿到钥匙才能开启这扇门,所以我们在合适位置放置一个宝箱,主人公开启宝箱…...

GitHub repository - Pulse - Contributors - Network
GitHub repository - Pulse - Contributors - Network 1. Pulse2. Contributors3. NetworkReferences 1. Pulse 显示该仓库最近的活动信息。该仓库中的软件是无人问津,还是在火热地开发之中,从这里可以一目了然。 2. Contributors 显示对该仓库进行过…...

RocketMQ 10 面试题FAQ
RocketMQ 面试FAQ 说说你们公司线上生产环境用的是什么消息中间件? 为什么要使用MQ? 因为项目比较大,做了分布式系统,所有远程服务调用请求都是同步执行经常出问题,所以引入了mq 解耦 系统耦合度降低,没有强依赖…...

【Spring进阶系列丨第十篇】基于注解的面向切面编程(AOP)详解
文章目录 一、基于注解的AOP1、配置Spring环境2、在beans.xml文件中定义AOP约束3、定义记录日志的类【切面】4、定义Bean5、在主配置文件中配置扫描的包6、在主配置文件中去开启AOP的注解支持7、测试8、优化改进9、总结 一、基于注解的AOP 1、配置Spring环境 <dependencie…...
Leetcode 152. 乘积最大子数组和Leetcode 162. 寻找峰值
文章目录 Leetcode 152. 乘积最大子数组题目描述C语言题解和思路解题思路 Leetcode 162. 寻找峰值题目描述C语言题解和思路解题思路 Leetcode 152. 乘积最大子数组 题目描述 给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中…...

项目实战之网络电话本之发送邮件名片和导出word版个人信息
1、项目介绍 1)项目功能 用户管理:分为管理员、和普通用户,设置不同用户的权限 电话本信息管理:支持管理员和普通用户对电话本的信息进行增删改操作,模糊查询(根据姓名、地址、单位) 文件批…...
前端面试问题汇总 - HTTP篇
1. 登录拦截如何实现? 在前端,可以拦截所有需要登录的请求,如果用户未登录或者登录过期,则跳转到登录页面。 2. http 缓存有哪些? 强缓存: 强缓存是指在客户端请求资源时,先检查本地是否存在缓存…...
Java的IO流
Day35 Java的IO流 概念 Java的IO流是用来处理输入和输出操作的机制,用于在程序和外部数据源(如文件、网络连接、内存等)之间进行数据传输。Java的IO流主要分为字节流和字符流两种类型,每种类型又分为输入流和输出流。 理解&#…...

Node.js 中的 RSA 加密、解密、签名与验证详解
引言 在现代的网络通信中,数据安全显得尤为重要。RSA加密算法因其非对称的特性,广泛应用于数据的加密、解密、签名和验证等安全领域。本文将详细介绍RSA算法的基本原理,并结合Node.js环境,展示如何使用内置的crypto模块和第三方库…...

vue+element作用域插槽
作用域插槽的样式由父组件决定,内容却由子组件控制。 在el-table使用作用域插槽 <el-table><el-table-column slot-scope" { row, column, $index }"></el-table-column> </el-table>在el-tree使用作用域插槽 <el-tree>…...
MUSA模型
MUSA模型在软件可靠性工程中起到的作用是估计软件的故障/失效数量和故障率。具体来说,MUSA模型包括基本模型和对数模型。 MUSA基本模型假设故障发生的时间间隔服从参数为lambda的指数分布。在这个模型中,当故障被检测到时,发生故障的部分会被…...

avicat连接异常,错误编号2059-authentication plugin…
错误原因为密码方式不对,具体可自行百度 首先管理员执行cmd进入 mysql安装目录 bin下边 我的是C:\Program Files\MySQL\MySQL Server 8.2\bin> 执行 mysql -u -root -p 然后输入密码 123456 进入mysql数据库 use mysql 执行 ALTER USER rootlocalhost IDE…...

阿里云云效CI/CD配置
1.NODEJS项目流水线配置(vue举例) nodejs构建配置 官方教程 注意:下图的dist是vue项目打包目录名称,根据实际名称配置 # input your command here cnpm cache clean --force cnpm install cnpm run build 主机部署配置 rm -rf /home/vipcardmall/frontend/ mkdir -p /home/…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...

大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...