数据结构算法题(力扣)——链表

以下题目建议大家先自己动手练习,再看题解代码。这里只提供一种做法,可能不是最优解。

1. 移除链表元素(OJ链接)

题目描述:给一个链表的头节点 head 和一个整数 val ,删除链表中所有满足值等于 val 的节点,并返回新的头节点

解法:遍历链表,依次比对结点的值和val是否相等,相等则删除,不相等则更新指针指向,继续遍历。

这里需要分两种情况来讨论,一是链表结点的值都等于val,二是链表结点的值不都等于val。

struct ListNode* removeElements(struct ListNode* head, int val) 
{//全部结点的值都等于val或前面部分结点相等while(head&&head->val==val){head=head->next;}//删除全部结点后head为空或者链表本身就为空链表if(!head){return NULL;}struct ListNode* cur=head;while(cur->next){//cur的下一个结点值等于val,则删除下一个if(cur->next->val==val){cur->next=cur->next->next;}//不相等则cur后移一步else{cur=cur->next;}}return head;
}

无论链表结点中是什么样的值,当进行完第一个while循环后,如果head不是NULL,那么我们定义的cur指针指向的结点的值一定不等于val。因此第二个while循环里if的判断条件为cur->next->val==val,这样不需要保留cur的前一个结点,因为cur本身就是前一个结点(可能删除的结点的前一个结点)。

2. 反转链表(OJ链接)

题目描述:给定单链表的头节点 head ,反转链表,并返回反转后的链表的头节点。

我们所要做的操作如下图
在这里插入图片描述
如果链表为NULL,直接返回空即可。链表不为空,则需要反转。

以上图链表为例本题解法如下图所示。
在这里插入图片描述

当n2为空时,循环结束。

题解代码如下

struct ListNode* reverseList(struct ListNode* head)
{if(head==NULL){return NULL;}struct ListNode* prev=NULL;struct ListNode* cur=head;struct ListNode* next=head->next;while(cur!=NULL){cur->next=prev;prev=cur;cur=next;if(next){next=next->next;}}return prev;
}

注意题解中的prev,cur和next指针分别对应图中的n1,n2,n3。最后一步时n3为NULL,所以需要加判断语句。

3. 链表的中间结点(OJ链接)

题目描述:给定单链表的头结点 head ,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

如果链表结点个数为奇数,返回中间结点,如果结点数为偶数,返回第二个结点。比如有六个结点,则返回第四个结点。

解法:快慢指针法。指的是一个指针走的步数多,一个指针走的步数少。此题快指针走两步,慢指针走一步。当快指针走到NULL或最后一个结点时(链表结点数为偶数或奇数),慢指针指向的结点即为中间结点。

题解代码如下

struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fast=head,*slow=head;while (fast!=NULL&&fast->next!=NULL){fast=fast->next->next;slow=slow->next;}return slow;
}

4. 合并两个有序链表(OJ链接)

题目描述:将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解法:创建两个指针变量分别指向两个链表的头,依次比较结点的值,值小的结点链接到新链表的尾,依次遍历链表,其中一个链表走完后,将剩余的链表链接到新链表的尾即可。

示例:
在这里插入图片描述
题解代码如下

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (!list1) {return list2;}if (!list2) {return list1;}//分别指向两个链表的头结点ListNode *p1 = list1, *p2 = list2;//phead为新链表的头,ptail为新链表的尾ListNode *phead = NULL, *ptail = NULL;//两个链表都没有遍历完while (p1 && p2) {if (p1->val < p2->val) {//链接的是第一个结点if (phead == NULL) {phead = ptail = p1;p1 = p1->next;} else {ptail->next = p1;ptail = ptail->next;p1 = p1->next;}} else {//链接的是第一个结点if (phead == NULL) {phead = ptail = p2;p2 = p2->next;} else {ptail->next = p2;p2 = p2->next;ptail = ptail->next;}}}//链表1没有走完if (p1) {ptail->next = p1;}//链表2没有走完if (p2) {ptail->next = p2;}return phead;
}

5. 返回倒数第k个结点(OJ链接)

题目描述:给定一个单链表的头结点(head),找出单向链表中倒数第 k 个节点。返回该节点的值。

此题和第三题类似。解法依旧是快慢指针法

解法:快指针先走k步,然后和慢指针一起走,快指针走到NULL时,慢指针指向的结点就是倒数第k个结点。
原理:快指针先走k步,使得两个指针间隔为k。再一起以相同速度走,最后两个指针间隔依旧是k

题解代码如下

int kthToLast(struct ListNode* head, int k)
{struct ListNode* fast=head,*slow=head;while(k--){fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow->val;
}

这里就先介绍这五个题的做法,大家可以试试用别的做法看是否可以做出来噢。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1323548.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

全面的Docker快速入门教程(详细)

前言&#xff1a; 都2024年了&#xff0c;你还在为了安装一个开发或者部署环境、软件而花费半天的时间吗&#xff1f;你还在解决开发环境能够正常访问&#xff0c;而发布测试环境无法正常访问的问题吗&#xff1f;你还在为持续集成和持续交付&#xff08;CI / CD&#xff09;工…

代码随想录第29天|491.递增子序列 46.全排列 47.全排列 II

目录&#xff1a; 491.递增子序列 46.全排列 47.全排列 II 491.递增子序列 491. 非递减子序列 - 力扣&#xff08;LeetCode&#xff09; 代码随想录 (programmercarl.com) 回溯算法精讲&#xff0c;树层去重与树枝去重 | LeetCode&#xff1a;491.递增子序列_哔哩哔哩_bili…

2023最新汽车网络安全报告汇总

2023最新汽车网络安全报告、安全参考架构及指南汇总&#xff0c;供大家学习参考。https://t.zsxq.com/18RkG260k 汽车信息安全法律法规及标准全景图V3.2.pdf 车载智能计算基础平台参考架构2.0.pdf 车载智能计算芯片白皮书(2023版).pdf 智能驾驶行为安全评价方法发布版.pdf 智能…

超细节小白教学Windows10系统 数据库MYSQL服务安装及验证

超细节小白教学Windows10系统 数据库MYSQL服务安装 一、MySQL下载及安装 官网下载地址&#xff1a;https://dev.mysql.com/downloads/mysql/ 进入官网页面如下图所示&#xff1a; 一般64-bit代表64位系统&#xff0c;如果需要32位系统可以在历史版本中寻找。 等待下载完成&a…

【协议篇:Http与Https】

1. Http 1.1 Http的定义 超文本传输协议&#xff08;Hypertext Transfer Protocol&#xff0c;HTTP&#xff09;是用于分布式、协作式和超媒体信息系统的应用层协议。它是互联网上最广泛应用的数据通信协议之一&#xff0c;尤其对于万维网&#xff08;WWW&#xff09;服务而言…

5.动态规划

1.背包问题 (1)0/1背包问题 01背包问题即每个物品只能选1个 考虑第i件物品&#xff0c;当j<w[i]时&#xff0c;f[i][j]f[i-1][j]&#xff0c;当j>w[i]时&#xff0c;此时有两种选择&#xff0c;选择第i件物品和不选第i件物品。此时f[i][j]max(f[i-1][j],f[i-1][j-w[i]]v…

【QingHub】QingHub Studio企业级应用作业编排

简介 QingHub作业编排中心是一个通过插件化方式&#xff0c;提供数据从采集&#xff0c;转化&#xff0c;计算&#xff0c;存储为一体的全流程数据处理方案&#xff0c;他一方面为前端应用提供数据源&#xff0c;同时也为前端应用与数据源头的通信搭建起桥梁&#xff0c;实现数…

【WebKit架构讲解】

&#x1f308;个人主页:程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…

C++:函数重载,引用

文章目录 1. 函数重载1.1 函数重载概念1.2 C支持函数重载的原理--名字修饰1.3 缺省参数与重载 2. 引用2.1引用概念2.2 引用特性2.3 常引用2.4 使用场景2.5 引用和指针的区别 1. 函数重载 1.1 函数重载概念 C允许在同一作用域中声明几个功能类似的同名函数&#xff0c;这些同名…

查看并设定【网络适配器】的优先级(跃点数)

目录 前言&#xff1a; 1.查看所有的适配器 2.修改优先级&#xff08;需要以管理员身份运行&#xff09; 跃点数&#xff08;InterfaceMetric &#xff09; DHCP 3.修改后的效果 pwoerShell 再次运行之前的程序 4.其他 参考 网络适配器1&#xff0c;8相关知识介绍1 …

回溯算法|47.全排列II

力扣题目链接 class Solution { private:vector<vector<int>> result;vector<int> path;void backtracking (vector<int>& nums, vector<bool>& used) {// 此时说明找到了一组if (path.size() nums.size()) {result.push_back(path);r…

【前端】CSS(引入方式+选择器+常用元素属性+盒模型)

文章目录 CSS一、什么是CSS二、语法规范三、引入方式1.内部样式表2.行内样式表3.外部样式 四、选择器1.选择器的种类1.基础选择器&#xff1a;单个选择器构成的1.标签选择器2.类选择器3.id 选择器4.通配符选择器 2.复合选择器1.后代选择器2.子选择器3.并集选择器4.伪类选择器 五…

python基于django协同算法的个性化音乐推荐系统的设计与实现

本个性化音乐推荐系统以Django作为框架&#xff0c;b/s模式以及MySql作为后台运行的数据库。本系统主要包括以下功能模块&#xff1a;首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;歌曲类型管理&#xff0c;明星歌手管理&#xff0c;歌曲音乐管理&#xff0c;歌曲…

Java基于微信小程序的电子竞技信息交流系统,附源码(V2.0)

博主介绍&#xff1a;✌IT徐师兄、7年大厂程序员经历。全网粉丝15W、csdn博客专家、掘金/华为云//InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&#x1f3…

AI预测福彩3D第24弹【2024年4月2日预测--第6套算法开始计算第1次测试】

今天&#xff0c;咱们进行第6套算法测试&#xff0c;本套算法将结合012路直选共27种组合&#xff0c;同时考虑了对012路的和值进行统计分析。今天为第1次测试&#xff0c;好了&#xff0c;废话不多说了。直接上结果~ 仍旧是分为两个方案&#xff0c;1大1小。 经过人工神经网络计…

常用的限流方案思路和实现

限流方案 1、计数器&#xff08;固定窗口&#xff09; 1.1、简介 计数器固定窗口算法是最基础也是最简单的一种限流算法。原理就是对一段固定时间窗口内的请求进行计数&#xff0c;如果请求数超过了阈值&#xff0c;则舍弃该请求&#xff1b;如果没有达到设定的阈值&#xf…

【单点登录SSO,Auth2,jwt-过程分析】

目录 单点登录简介 SSO&CAS是什么 单点登录适合什么场景 单点登录的三种实现方式 CAS的几个重要知识点 CAS的实现过程 单点登录简介 单点登录(SingleSignOn&#xff0c;SSO)&#xff0c;就是通过用户的一次性鉴别登录。当用户在身份认证服务器上登录一次以后&#xff0c;即…

C++ //练习 11.12 编写程序,读入string和int的序列,将每个string和int存入一个pair中,pair保存在一个vector中。

C Primer&#xff08;第5版&#xff09; 练习 11.12 练习 11.12 编写程序&#xff0c;读入string和int的序列&#xff0c;将每个string和int存入一个pair中&#xff0c;pair保存在一个vector中。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#x…

【JavaWeb】Day32.MySQL概述

什么是数据库 数据库&#xff1a;英文为 DataBase&#xff0c;简称DB&#xff0c;它是存储和管理数据的仓库。 像我们日常访问的电商网站京东&#xff0c;企业内部的管理系统OA、ERP、CRM这类的系统&#xff0c;以及大家每天都会刷的头条、抖音类的app&#xff0c;那这些大家所…

苍穹外卖Day04套餐管理部分总结

写给像我一样完完全全的小白的。本人代码水平一塌糊涂&#xff0c;前几天就是机械地跟着视频敲代码。对于Day04的作业本来感觉代码抓瞎一点不会写&#xff0c;尽力去理解业务逻辑后发现好像也没那么难&#xff0c;整体代码可以仿照Day03新增菜品来进行实现&#xff01; 一、功…