当前位置: 首页 > 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…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

WebRTC调研

WebRTC是什么&#xff0c;为什么&#xff0c;如何使用 WebRTC有什么优势 WebRTC Architecture Amazon KVS WebRTC 其它厂商WebRTC 海康门禁WebRTC 海康门禁其他界面整理 威视通WebRTC 局域网 Google浏览器 Microsoft Edge 公网 RTSP RTMP NVR ONVIF SIP SRT WebRTC协…...