单链表经典算法题理解
目录
1. 前言:
2. 移除链表元素
3. 反转链表
4. 合并两个有序链表
5. 链表的中间节点
6. 环形链表的约瑟夫问题
7. 分割链表
1. 前言:
当我们学习了单链表之后,我能可以尝试的刷一下题了,以下分享一下几道题的解法
2. 移除链表元素
题目链接:. - 力扣(LeetCode)

思路:
我们这里可以通过创建一个新链表的形式,用来接收原链表里面不等于val的值,把他拿下来尾插,这里题目规定了原链表的值可能是0,就表示原链表是空链表,那我们进行判断,如果原链表为空,我们直接将原链表返回去,如果不为空,我们就进行遍历原链表,来判断原链表的值是否等于给定的val,然后拿下来在新链表中进行尾插操作,最后,判断一下新链表的尾是否是空的,如果不是空,我们需要将它手动置空,最后我们返回新链表的头即可。
代码
typedef struct ListNode sln;//类型重命名,简化写法
struct ListNode* removeElements(struct ListNode* head, int val) {if(head == NULL)//如果链表为空,我们直接将原链表返回去{return head;}else{//我们创建新链表sln* newnode = NULL;sln* ptail = NULL;//创建一个指针用来遍历原链表sln*pcur = head;while(pcur){//如果原链表里面的值不等于val,我们就拿下来尾插if(pcur->val != val){//如果新链表为空,此时,这个链表的头和尾就都是拿下来的数据if(newnode == NULL){newnode = pcur;ptail = pcur;}else{//链表不为空,进行尾插ptail->next = pcur;ptail = ptail->next;}}pcur = pcur->next;}if(ptail)//这里判断,ptail是否是空节点,如果不是,我们需要将它指向空ptail->next = NULL;//返回新链表的头return newnode;}
}
3. 反转链表
题目:. - 力扣(LeetCode)

思路:
其实这里我们看到这个题目的时候,首先肯定是想到的是创建一个新链表,将原链表的节点拿下来一个个头插,但是这个方法写起来有点麻烦,我们这里用到一个新的方法来解,就是定义三个p1,p2和p3指针,分别指向空,头节点,和头节点下一个节点,将p2指向p1之后,将他们3个指针都往后移动,最后p2走到空了的话,p1此时就是头节点了,直接返回p1.
代码
typedef struct ListNode sln;//类型重命名 简化写法
struct ListNode* reverseList(struct ListNode* head) {if(head == NULL)//判断链表是否为空{//如果为空直接返回原链表return head;}//定义三个指针,分别指向空,头节点和头节点下一个节点sln* p1 = NULL;sln* p2 = head;sln* p3 = head->next;while(p2)//当p2走到空了说明p1是头节点{p2->next = p1;p1 = p2;p2 = p3;if(p3 != NULL)//增加一个判断条件,如果p3走到空了,我们访问p3就会出错p3 = p3->next;}//直接返回p1return p1;
}
4. 合并两个有序链表
题目:. - 力扣(LeetCode)

思路:
这个题目,我能可以使用创建新链表的方式来解决,我们先创建一个新链表,然后再创建两个指针,分别用来遍历原链表里面的数据,如果1链表里的节点数据小于2链表里的节点数据,我们就把它拿下来尾插到新链表,反之将2链表里面的数据拿下来了尾插到新链表里面,
但是我们要考虑两种情况,就是如果1链表已经遍历完了,但是2链表里面还有数据,那么我们就将2链表里面的数据拿下来了尾插到新链表里面,反之将1链表里面的数据尾插到新链表中。
代码
typedef struct ListNode sln;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1 == NULL){//如果list1为空链表,直接返回list2return list2;}if(list2 == NULL){//如果list2为空链表,直接返回list1return list1;}//创建新链表sln* newnode = (sln*)malloc(sizeof(sln));sln* ptail = newnode;//定义两个指针,分别指向两个链表的头节点sln* p1 = list1;sln* p2 = list2;//循环遍历两个链表while(p1&&p2){//如果p1<p2if(p1->val<p2->val){//把p1拿下来尾插,p1向后走ptail->next = p1;ptail = ptail->next;p1 = p1->next;}else{//把p2拿下来尾插,p2往后走ptail->next =p2;ptail = ptail->next;p2 = p2->next;}}//可能p2走到空了,p1里面还有元素if(p1){//拿下来尾插ptail->next = p1;ptail = ptail->next;}if(p2)//可能p1走到空了,p2里面还有元素{//拿下来尾插ptail->next =p2;ptail = ptail->next;}sln* ret = newnode->next;free(newnode);//动态申请的空间,手动释放newnode = NULL;return ret;
}
5. 链表的中间节点
题目:. - 力扣(LeetCode)

思路:
我们要找到链表的中间节点,我们可以采取计数器的方法,先遍历一遍链表,然后取计数器的中间值,在遍历一遍链表,返回中间值时的节点,这样也可以解题,但是需要遍历两遍链表,比较麻烦。那么我们就采取另一种方法。
快慢指针的方法。
我们定义两个指针,让他们遍历链表,但是两个指针的移动速度不一样,快指针一次走两步,慢指针一次走1步,这样,当快指针遍历完链表或者走到链表的尾节点时,此时慢指针就刚好走到链表的中间节点位置,直接返回慢指针指向的节点,这样就可以找到链表的中间节点了
代码:
typedef struct ListNode sln;
struct ListNode* middleNode(struct ListNode* head) {//我们定义两个指针sln* slow = head;sln* fast = head;while(fast&&fast->next!=NULL){//让这两个直接按照不同的速度往后走//2*slow = fastslow = slow->next;fast = fast->next->next;}return slow;
}
6. 环形链表的约瑟夫问题
题目: 环形链表的约瑟夫问题_牛客题霸_牛客网

什么是约瑟夫问题呢?
来自百度:
思路:
这里,我们知道报到指定数目,指定数目的人就要离开,我们首先需要定义一个计数器,然后我们需要使用到两个指针,一个指针用来遍历链表,一个指针记录住遍历链表的指针的上一次节点,然后循环遍历链表,直到链表只剩最后一个节点,跳出循环,返回最后一个节点里面的值就可以了。
代码:
typedef struct ListNode sln;
//创建节点sln* BuyNode(int x){sln* newnode = (sln*)malloc(sizeof(sln));if(newnode == NULL){perror("malloc");exit(1);}newnode->val = x;newnode->next = NULL;return newnode;}//创建带环链表sln * CircleNode(int x){sln* newnode = BuyNode(1);sln* ptail = newnode;for(int i = 2;i <= x;i++){ptail->next = BuyNode(i);ptail = ptail->next;}ptail->next = newnode;return ptail;}int ysf(int n, int m ) {//创建一个指针指向头节点sln*prev = CircleNode(n);//创建一个指针指向头节点的前一个节点sln*phead = prev->next;// write code hereint count = 1;//定义计数器while(phead->next!= phead)//链表如果只有一个节点就跳出循环{if(count == m)//当计数器==给定数目时,需要删除节点{prev->next = phead->next;free(phead);phead = prev->next;count = 1;}else //不==,让两个指针都往后,计数器++{prev = phead;phead = phead->next;count++;} }//返回最后一个节点里面的数据return phead->val;
}
7. 分割链表
题目:. - 力扣(LeetCode)

思路:
这里我们可以采取创建两个新链表的形式,一个用来接收小于x的节点,另一个用来接收大于或等于x的节点。然后将两个链表首尾链接的方式,并且将用头节点连接的尾节点指向空。
代码:
typedef struct ListNode sln;
struct ListNode* partition(struct ListNode* head, int x){if(head == NULL)//判断原链表是否为空{return head;}//创建一个指针来遍历原链表sln*pcur = head;//这里创建一个大链表来就收原链表大于x的节点sln*large = (sln*)malloc(sizeof(sln));sln* ptail = large;//创建一个小链表来接收原链表小于x的节点sln* little = (sln*)malloc(sizeof(sln));sln*pend = little;while(pcur){if(pcur->val<x){pend->next = pcur;pend = pend->next;}else{ptail->next = pcur;ptail = ptail->next;}pcur = pcur->next;}//遍历完原链表//将大小链表连接,将大链表尾节点指向空ptail->next = NULL;pend->next =large->next;//释放申请的空间sln*ret = little->next;free(little);free(large);little = large = NULL;return ret;
}
相关文章:
单链表经典算法题理解
目录 1. 前言: 2. 移除链表元素 3. 反转链表 4. 合并两个有序链表 5. 链表的中间节点 6. 环形链表的约瑟夫问题 7. 分割链表 1. 前言: 当我们学习了单链表之后,我能可以尝试的刷一下题了,以下分享一下几道题的解法 2. 移…...
STM32的时钟介绍
目录 前言1. 简介1.1 时钟是用来做什么的1.2 时钟产生的方式 2. 时钟树的组成2.1 时钟源2.1.1 内部时钟2.1.2 外部时钟 2.2 PLL锁相环2.3 SYSCLK2.4 AHB和HCLK2.5 APB和PCLK2.6 总结 3. STM32时钟的如何进行工作4.我的疑问4.1 使用MSI和HSI有什么区别吗?4.2 MSI的频…...
FindBI学习总结
大数据分析BI工具:用户只需简单拖拽便能制作出丰富多样的数据可视化信息 关注点: 快速入门、数据加工、构建图表和分析数据、数据分析进阶 1、界面介绍 目录–仪表板–数据准备 仪表板目录–预览区域 快速上手: 1、数据准备2、制作仪表板3、分…...
k8s——Pod详解
一、Pod基础概念 1.1 Pod定义 Pod是kubernetes中最小的资源管理组件,Pod也是最小化运行容器化应用的资源对象。一个Pod代表着集群中运行的一个进程。kubernetes中其他大多数组件都是围绕着Pod来进行支撑和扩展Pod功能的,例如,用于管理Pod运行…...
Visual Studio 的调试
目录 引言 一、调试的基本功能 设置断点 启动调试 检查变量 逐步执行代码 调用堆栈 使用即时窗口 二、调试技巧 条件断点 日志断点 数据断点 异常调试 三、调试高级功能 远程调试 多线程调试 内存调试 性能调试 诊断工具 四、调试策略与最佳实践 系统化的…...
mysql语句大全及用法
MySQL是一种广泛使用的开源关系型数据库管理系统,它支持标准的SQL(Structured Query Language)语言,用于数据库的查询和操作。以下是一些基本的MySQL语句及其用法的概述: 连接MySQL数据库 mysql -h主机地址 -P端口号…...
如何找出真正的交易信号?Anzo Capital昂首资本总结7个
匕首是一种新兴的价格走势形态,虽然不常见,但具有较高的统计可靠性。它通常预示着趋势的持续发展。该模式涉及到同时参考两个不同的时间周期进行交易,一个是短期,另一个是长期,比如一周时间框架与一天时间框架、一天时…...
JavaScript-内存分配
内存空间 内存分为栈和堆 栈:由操作系统自动释放存放的变量值和函数值等。简单数据类型存放在栈中 栈会由低到高先入后出 堆:存储引用类型 (对象) 对象会先将数据存放在堆里面,堆的地址放在栈里面...
理论知识.质数打表
啊,哈喽,小伙伴们大家好。我是#张亿,今天呐,学的是理论知识.质数打表 为什么需要质数打表 我们已经学习了如何判断一个数是不是质数了,但是还不够。假设要判断很多很多个数是不是质数的时候,之前的学习的…...
FFMPEG+ANativeWinodow渲染播放视频
前言 学习音视频开发,入门基本都得学FFMPEG,按照目前互联网上流传的学习路线,FFMPEGANativeWinodow渲染播放视频属于是第一关卡的Boss,简单但是关键。这几天写了个简单的demo,可以比较稳定进行渲染播放,便…...
使用AXI MIG/Proc Sys Reset
使用AXI MIG/Proc Sys Reset 重要!仅当您的设计中包含AXI MIG时,才执行以下步骤。 AXI-MIG的连接接口 1.选择在/mig_7series_0/S_AXI上运行连接自动化。 2.选择/micblaze_0(缓存)或/micblaze _0(Periph)选项…...
Android基础-Kotlin语言的作用及优缺点
一、Kotlin语言的作用 Kotlin是一种由JetBrains公司开发的现代化静态类型编程语言,自其诞生以来,便在多个领域展现出了强大的应用潜力。其主要作用可以概括为以下几点: Android应用开发:Kotlin作为Android开发的官方推荐语言&am…...
手机投屏技巧:手机怎么投屏到电脑显示屏上?精选6招解决!
手机怎么投屏到电脑显示屏上?出于一些不同的原因,大多数人都希望能将手机投屏到电脑上。其中一个常见的原因是,大家经常会希望在笔记本电脑上共享图片,而无需上传或者登录微信进行文件传输。以及希望不依靠投影仪,就能…...
内存函数<C语言>
前言 前面两篇文章介绍了字符串函数,不过它们都只能用来处理字符串,C语言中也内置了一些内存函数来对不同类型的数据进行处理,本文将介绍:memcpy()使用以及模拟实现,memmove()使用以及模拟实现,memset()使用…...
华为校招机试 - LRU模拟(20240515)
题目描述 LRU(Least Recently Used)缓存算法是一种常用于管理缓存的策略,其目标是保留最近使用过的数据,而淘汰最久未被使用的数据。 实现简单的LRU缓存算法,支持查询、插入、删除操作。 最久未被使用定义:查询、插入和删除操作均为一次访问操作,每个元素均有一个最后…...
AI预测福彩3D采取888=3策略+和值012路一缩定乾坤测试5月29日预测第5弹
今天继续基于8883的大底,使用尽可能少的条件进行缩号,同时,同样准备两套方案,一套是我自己的条件进行缩号,另外一套是8883的大底结合2码不定位奖号预测二次缩水来杀号。好了,直接上结果吧~ 首先&…...
03_前端三大件CSS
文章目录 CSS用于页面元素美化1.CSS引入1.1style方式1.2写入head中,通过写style然后进行标签选择器加载样式1.3外部样式表 2.CSS样式选择器2.1 元素选择器2.2 id选择器2.3 class选择器 3.CSS布局相关3.1 CSS浮动背景:先设计一些盒子因此,引出…...
十种常用数据分析模型
1-线性回归(Linear Regression) 场景:预测商品销售额 优点:简单易用,结果易于解释缺点:假设线性关系,容易受到异常值影响概念:建立自变量和因变量之间线性关系的模型。公式&#x…...
salesforce 公式字段 判断一个字段是否在某个多选列表中
在 Salesforce 中,你可以使用公式字段来判断一个字段的值是否在一个多选列表中。这通常涉及使用包含特定值的函数和一些字符串操作。以下是一个常见的方法: 假设你有一个多选列表字段 Multi_Select_Field__c,你想检查这个字段是否包含某个值…...
C++STL容器系列(三)list的详细用法和底层实现
目录 一:介绍二:list的创建和方法创建list方法 三:list的具体用法3.1 push_back、pop_back、push_front、pop_front3.2 insert() 和 erase()3.3 splice 函数 四:list容器底层实现4.1 list 容器节点结构5.2 list容器迭代器的底层实…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...
水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关
在水泥厂的生产流程中,工业自动化网关起着至关重要的作用,尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关,为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多,其中不少设备采用Devicenet协议。Devicen…...






