当前位置: 首页 > news >正文

【算法学习之路】7.链表算法

链表算法

  • 前言
  • 一.原地逆置
    • 思路一:头插法
    • 思路二:双指针法
    • 思路3:递归
  • 例题:
    • 1.头插法
    • 2.双指针法
    • 3,递归
  • 二.双指针
    • 快慢指针:一个指针快一个指针慢
      • 例题1
      • 例题2

前言

我会将一些常用的算法以及对应的题单给写完,形成一套完整的算法体系,以及大量的各个难度的题目,目前算法也写了几篇,题单正在更新,其他的也会陆陆续续的更新,希望大家点赞收藏我会尽快更新的!!!

一.原地逆置

思路一:头插法

若带头节点,先将头节点摘下来
然后从第一个节点开始,挨个插入每一个节点
摘下来后用头插法建立新的链表

思路二:双指针法

定义两个指针pre和cur,pre在前cur在后
每次让pre的next指向cur,实现一次局部反转
局部反转之后。pre和cur同时往后移动一个位置,循环上述过程,直至pre到达链表尾部(在循环过程中需要记录pre->next)

思路3:递归

递归出口:传进来的节点p的next = NULL
递归体:递归调用,把p之后的先反转

例题:

力扣206. 反转链表
在这里插入图片描述

1.头插法

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///头插法
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* p = head;if(head == NULL){//先判断是否为空return NULL;}struct ListNode* q = p->next;head = NULL;//将节点从链表拿下来while(q != NULL){p->next = head;head = p;p = q;q = q->next;}p->next = head;return p;
}

2.双指针法

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///双指针法
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* p = head;//指向头节点struct ListNode* q = NULL;//指向头节点的上一个节点while(p != NULL){//struct ListNode* t = p->next;//保存p->nextp->next = q;q = p;p = t;}return q;
}

3,递归

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///递归
struct ListNode* reverse (struct ListNode* cur, struct ListNode* pre);struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head;struct ListNode* pre = NULL;return reverse (cur, pre);
}struct ListNode* reverse (struct ListNode* cur, struct ListNode* pre){if (cur == NULL) {return pre;}else {struct ListNode* tmp = cur -> next;cur -> next = pre;return reverse (tmp, cur);}
}

二.双指针

快慢指针:一个指针快一个指针慢

例题1

力扣LCR 140. 训练计划 II

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* trainingPlan(struct ListNode* head, int cnt) {struct ListNode* cur = head;struct ListNode* next = head;for(int i = 0; i < cnt; i++){next = next->next;}while(next){cur = cur->next;next = next->next;}return cur;
}

例题2

力扣142. 环形链表 II
在这里插入图片描述
找环开始节点慢指针每次走一个节点,快指针每次走两个节点,当相遇时,再来一个指针从头一个一个走。当与慢指针相遇的时候为开始节点

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {if(head == NULL || head->next == NULL || head->next->next == NULL){return NULL;}struct ListNode* s = head;struct ListNode* f = head;while(f != NULL){s = s->next;if(f->next == NULL){return NULL;}f = f->next->next;if(f == s){struct ListNode* t = head;while(t != s){t = t->next;s = s->next;}return t;}}return NULL;}

未完待续……

相关文章:

【算法学习之路】7.链表算法

链表算法 前言一.原地逆置思路一&#xff1a;头插法思路二&#xff1a;双指针法思路3&#xff1a;递归 例题&#xff1a;1.头插法2.双指针法3&#xff0c;递归 二.双指针快慢指针&#xff1a;一个指针快一个指针慢例题1例题2 前言 我会将一些常用的算法以及对应的题单给写完&am…...

IDEA Commit 模态提交界面关闭VS开启对比

IDEA Commit 模态提交界面关闭VS开启对比 前言开启模态提交界面优点快捷且灵活的选择需要commit文件显示文件修改内容多(主观) 缺点在模态提交界面选择文件&#xff0c;临时关闭模态框重新打开会重置选择的commit文件 关闭模态提交界面优点允许在commit选择文件时查看其它没有修…...

【AI赋能】AI 工具生成视频教材:从创意到成品的全流程指南

AI 工具生成视频教材&#xff1a;从创意到成品的全流程指南 目标 通过本教材&#xff0c;您将学会如何利用 AI 工具&#xff08;Grok、Sora、Speechify 和 CapCut&#xff09;生成一个完整的视频&#xff0c;包括脚本生成、视频片段制作、字幕添加、音频生成以及最终剪辑合成…...

qt 操作多个sqlite文件

qt 操作多个sqlite文件 Chapter1 qt 操作多个sqlite文件1. 引入必要的头文件2. 创建并连接多个SQLite数据库3. 代码说明4. 注意事项 Chapter2 qt 多线程操作sqlite多文件1. 引入必要的头文件2. 创建数据库操作的工作线程类3. 在主线程中创建并启动多个工作线程4. 代码说明5. 运…...

WSL with NVIDIA Container Toolkit

一、wsl 下安装 docker 会提示安装 docekr 桌面版&#xff0c;所以直接安装 docker 桌面版本即可 二、安装 NVIDIA Container Toolkit NVIDIA Container Toolkit仓库 https://github.com/NVIDIA/nvidia-container-toolkit​github.com/NVIDIA/nvidia-container-toolkit 安装…...

Vue 系列之:组件通讯

子组件调用父组件方法 1、直接在子组件中通过 this.$parent.event 来调用父组件的方法 父组件&#xff1a; <template><p><child></child></p> </template> <script>import child from ./child;export default {components: {chi…...

【Linux实践系列】:用c语言实现一个shell外壳程序

&#x1f525;本文专栏&#xff1a;Linux Linux实践项目 &#x1f338;博主主页&#xff1a;努力努力再努力wz 那么今天我们就要进入Linux的实践环节&#xff0c;那么我们之前学习了进程控制相关的几个知识点&#xff0c;比如进程的终止以及进程的等待和进程的替换&#xff0c;…...

STL map 的 lower_bound(x)、upper_bound(x) 等常用函数

【STL map 简介】 ● STL map 是一种关联容器&#xff0c;存储键值对&#xff0c;每个键&#xff08;key value&#xff09;是唯一的&#xff0c;而值&#xff08;mapped value&#xff09;可以重复。构建 STL map 时&#xff0c;无论元素插入顺序如何&#xff0c;STL map 中的…...

【A2DP】SBC 编解码器互操作性要求详解

目录 一、SBC编解码器互操作性概述 二、编解码器特定信息元素(Codec Specific Information Elements) 2.1 采样频率(Sampling Frequency) 2.2 声道模式(Channel Mode) 2.3 块长度(Block Length) 2.4 子带数量(Subbands) 2.5 分配方法(Allocation Method) 2…...

Computational Linguistics期刊全解析:领域顶刊的投稿指南与学术价值

在人工智能与语言学交叉融合的浪潮中&#xff0c;《Computational Linguistics》&#xff08;CL&#xff09;作为该领域的标杆期刊&#xff0c;始终是研究者发表前沿成果的首选平台。本文将从期刊影响力、投稿策略、收稿方向等角度&#xff0c;为学者提供一份全面的指南。 一、…...

【量化科普】Sharpe Ratio,夏普比率

【量化科普】Sharpe Ratio&#xff0c;夏普比率 &#x1f680;量化软件开通 &#x1f680;量化实战教程 在量化投资领域&#xff0c;夏普比率&#xff08;Sharpe Ratio&#xff09;是一个非常重要的风险调整后收益指标。它由诺贝尔经济学奖得主威廉F夏普&#xff08;William…...

运行OpenManus项目(使用Conda)

部署本项目需要具备一定的基础&#xff1a;Linux基础、需要安装好Anaconda/Miniforge&#xff08;Python可以不装好&#xff0c;直接新建虚拟环境的时候装好即可&#xff09;&#xff0c;如果不装Anaconda或者Miniforge&#xff0c;只装过Python&#xff0c;需要确保Python是3.…...

TikTok Shop欧洲市场爆发,欧洲TikTok 运营网络专线成运营关键

TikTok在欧洲的影响力还在持续攀升&#xff0c;日前&#xff0c;TikTok发布了最新的欧盟执行和使用数据报告&#xff0c;报告中提到&#xff1a; 2024年7~12月期间&#xff0c;TikTok在欧盟地区的月活用户达1.591亿&#xff0c;较上一报告期&#xff08;2024年10月发布&#xf…...

基于YOLO11深度学习的电瓶车进电梯检测与语音提示系统【python源码+Pyqt5界面+数据集+训练代码】

《------往期经典推荐------》 一、AI应用软件开发实战专栏【链接】 项目名称项目名称1.【人脸识别与管理系统开发】2.【车牌识别与自动收费管理系统开发】3.【手势识别系统开发】4.【人脸面部活体检测系统开发】5.【图片风格快速迁移软件开发】6.【人脸表表情识别系统】7.【…...

计算机毕业设计SpringBoot+Vue.js制造装备物联及生产管理ERP系统(源码+文档+PPT+讲解)

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…...

微服务保护:Sentinel

home | Sentinelhttps://sentinelguard.io/zh-cn/ 微服务保护的方案有很多&#xff0c;比如&#xff1a; 请求限流 线程隔离 服务熔断 服务故障最重要原因&#xff0c;就是并发太高&#xff01;解决了这个问题&#xff0c;就能避免大部分故障。当然&#xff0c;接口的并发…...

labelimg标注的xml标签转换为yolo格式标签

本文不生产技术&#xff0c;只做技术的搬运工&#xff01;&#xff01;&#xff01; 前言 在yolo训练时&#xff0c;我们需要对图像进行标注&#xff0c;而使用labelimg标注时如果直接选择输出yolo格式的数据集&#xff0c;则原始数据的很多信息无法被保存&#xff0c;因此一版…...

VUE3开发-9、axios前后端跨域问题解决方案

VUE前端解决跨域问题 前端页面需要改写 如果无效&#xff0c;记得重启服务器 后端c#解决跨域问题 前端js取值&#xff0c;后端c#跨域_c# js跨域-CSDN博客...

机试准备第12天

首先学习队列&#xff0c;队列有先进先出的特性。广度优先遍历需要基于队列实现&#xff0c;C中的stl引入了队列的实现方式。队列支持push()&#xff0c;进入队尾&#xff0c;pop()出队&#xff0c;队头出队&#xff0c;front()获取队首元素&#xff0c;back()获取队尾元素&…...

计算机二级MS之PPT

声明&#xff1a;跟着大猫和小黑学习随便记下一些笔记供大家参考&#xff0c;二级考试之前将持续更新&#xff0c;希望大家二级都能轻轻松松过啦&#xff0c;过了二级的大神也可以在评论区留言给点建议&#xff0c;感谢大家&#xff01;&#xff01; 文章目录 考题难点1cm25px…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...