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

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...