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

【Leedcode】数据结构中链表必备的面试题(第三期)

【Leedcode】数据结构中链表必备的面试题(第三期)


文章目录

  • 【Leedcode】数据结构中链表必备的面试题(第三期)
  • 一、第一题
    • 1.题目
    • 2.思路
    • 3.源代码
  • 二、第二题
    • 1.题目
    • 2.思路
      • (1)第一种情况:偶数个链表
      • (2)第二种情况:奇数个链表
    • 3.源代码
      • (1)链表的中间结点的实现
      • (2)反转链表的实现
      • (3)链表比较函数的实现
      • (4)整体源代码
  • 总结


一、第一题

1.题目

CM11 链表分割 如下(示例):

现有一链表的头指针ListNode*pHead,给一定值x,
编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。 

在这里插入图片描述


2.思路

1.使用两个哨兵位的头结点lessheadgreathead,把小于4的连接到lesshead后面,大于4的链接到greathead后面;
2.再把小于4的最后一个连接到大于4的第一个:具体如下图


![在这里插入图片描述](https://img-blog.csdnimg.cn/ddf62b3dab8a4de7aea2d12a4549626d.png


注意:如下图!
在这里插入图片描述


3.源代码

代码如下(示例):

struct ListNode {int val;struct ListNode *next;
};
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lessHead, *lessTail, *greaterHead, *greaterTail;lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));lessTail->next = greaterTail->next = NULL;struct ListNode* cur = pHead;while (cur) {if (cur->val < x) {lessTail->next = cur;lessTail = lessTail->next;}else {greaterTail->next = cur;greaterTail = greaterTail->next;}cur = cur->next;}lessTail->next = greaterHead->next;greaterTail->next = NULL;struct ListNode* list = lessHead->next;free(lessHead);free(greaterHead);return list;}
};

二、第二题

1.题目

OR36 链表的回文结构 如下(示例):

对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900

在这里插入图片描述


2.思路

(1)第一种情况:偶数个链表


在这里插入图片描述


(2)第二种情况:奇数个链表

在这里插入图片描述


3.源代码

(1)链表的中间结点的实现

  1. 链表的中间结点的实现 如下(示例):
struct ListNode
{int val;struct ListNode *next;
}
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow,*quick;slow=quick=head;while(quick && quick->next){slow= slow->next;quick= quick->next->next;}return slow;
}

(2)反转链表的实现

  1. 反转链表的实现 如下(示例):
struct ListNode 
{int val;struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* head)
{//第二种方法struct ListNode* newhead=NULL;struct ListNode* cur=head;while(cur){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}

(3)链表比较函数的实现

代码如下(示例):

class PalindromeList {
public:bool chkPalindrome(ListNode* A) {struct ListNode* mid =middleNode(A);struct ListNode* rHead =reverseList(mid);struct ListNode* curA=A;struct ListNode* curR = rHead;while( curA && curR){if(curA -> val != curR ->val){return false;}else {curA=curA->next;curR =curR-> next;}}return true;}
};

(4)整体源代码

代码如下(示例):

struct ListNode 
{int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow,*quick;slow=quick=head;while(quick && quick->next){slow= slow->next;quick= quick->next->next;}return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{//第二种方法struct ListNode* newhead=NULL;struct ListNode* cur=head;while(cur){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;}
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {struct ListNode* mid =middleNode(A);struct ListNode* rHead =reverseList(mid);struct ListNode* curA=A;struct ListNode* curR = rHead;while( curA && curR){if(curA -> val != curR ->val){return false;}else {curA=curA->next;curR =curR-> next;}}return true;}
};

总结

以上就是今天要讲的内容,本文介绍数据结构中链表必备的面试题(第三期)
如果我的博客对你有所帮助记得三连支持一下,感谢大家的支持!

在这里插入图片描述

相关文章:

【Leedcode】数据结构中链表必备的面试题(第三期)

【Leedcode】数据结构中链表必备的面试题&#xff08;第三期&#xff09; 文章目录【Leedcode】数据结构中链表必备的面试题&#xff08;第三期&#xff09;一、第一题1.题目2.思路3.源代码二、第二题1.题目2.思路(1)第一种情况&#xff1a;偶数个链表(2)第二种情况&#xff1a…...

D1.Chopping Carrots (Easy Version)【数学,二分,暴力,思维】

链接 理论基础 已知正整数a,v,求证m⌊av⌋是满足⌊am⌋⩾v的最大的m&#xff0c;其中x是正整数已知正整数a,v,求证m\lfloor \frac {a}{v} \rfloor是满足\lfloor \frac {a}{m} \rfloor \geqslant v的最大的m&#xff0c;其中x是正整数已知正整数a,v,求证m⌊va​⌋是满足⌊ma​⌋…...

【Maven】(二)使用 Maven 创建并运行项目、聊聊 POM 中的坐标与版本号的规则

文章目录1.前言2.hello-world2.1.Archetype 创建2.2.使用 IDE 创建2.3.Maven的目录结构3.pom的基本组成3.1.Maven坐标的概念与规则3.2.版本号规则2.3.打包成可运行的JAR4.结语1.前言 本系列文章记录了从0开始到实战系统了解 Maven 的过程&#xff0c;Maven 系列历史文章&#…...

(考研湖科大教书匠计算机网络)第六章应用层-第六节:电子邮件

获取pdf&#xff1a;密码7281专栏目录首页&#xff1a;【专栏必读】考研湖科大教书匠计算机网络笔记导航 文章目录一&#xff1a;电子邮件&#xff08;1&#xff09;概述&#xff08;2&#xff09;举例二&#xff1a;简单邮件传送协议SMTP&#xff08;1&#xff09;SMTP基本工作…...

一、初识TypeScript、什么是类型系统

初识TypeScript、什么是类型系统 快速上手TypeScript 安装方式&#xff1a; > npm install -g typescriptTypeScript是JavaScript类型的超集&#xff0c;包含JS的所有语法&#xff0c;它可以编译成纯JavaScript。 意味着&#xff0c;纯js代码可以在.ts后缀名文件中编译 …...

一文了解什么是字节对齐(超详细)

什么是字节对齐 1.空类 class A {}对空类做sizeof&#xff08;&#xff09;计算时应当等于1 2.带虚函数的类 如果有一个类&#xff0c;包含两个32位整型的数据成员&#xff0c;一个普通成员函数&#xff0c;还有一个virtual虚函数&#xff0c;在32位机器上&#xff0c;这个…...

Java无法通过形参设置为null改变实参

文章目录问题描述问题例子问题分析问题描述 在实际业务开发过程中&#xff0c;我们会把实参传递给形参&#xff0c;在方法体内对引用对象进行构建或者修改&#xff0c;从而改变实参&#xff0c;因为对形参对象属性修改时&#xff0c;实参对象也会随着改变&#xff0c;详情请看&…...

GEE:样本点选择教程

本文记录了在GEE平台上标记样本的技巧和代码脚本&#xff0c;样本点可以用来做土地利用分类、植被提取、水藻提取、冰川提取、农作物提取等应用中。可以应用到的方法包括随机森林&#xff08;RF&#xff09;分类&#xff0c;支持矢量机&#xff08;SVM&#xff09;分类&#xf…...

3.知识图谱相关学习资料汇总,提供系统化的知识图谱学习路径。一份详细的指南,补全你知识的漏洞

目录 理论及论文图谱及数据集工具及服务白皮书及报告机构及人物视频课程专栏合集评测竞赛项目案例推广技术文章1. 整体概念架构 随着知识图谱的发展,与之相关的概念也越来越多,在阅读论文时先准确的把握该论文所要解决问题处于的层级或者位置对于更好的理解论文也比较有帮助…...

TypeScript学习笔记(一)编译环境、数据类型、函数类型、联合类型

文章目录编译环境基本类型函数类型函数重载联合类型和函数重载编译环境 TypeScript最终会被编译成JavaScript来运行&#xff0c;所以我们需要搭建对应的环境。 首先我们要全局安装typescript # 安装命令 npm install typescript -g # 查看版本 tsc --version⭐️ 方式一&…...

为什么要移除数据库物理外键?

在最早接触数据库的时候&#xff0c;会接触数据库三范式&#xff0c;在表和表之间有关系的时候&#xff0c;需要使用外键添加约束 外键的好处&#xff1a; 1、由数据库自身保证数据一致性&#xff0c;完整性&#xff0c;更可靠&#xff0c;因为程序很难100&#xff05;保证数据…...

Linux 计划任务讲解

目录 计划任务 一次性计划任务 长期性计划任务 计划任务 管理员可以编辑自己的和普通用户的计划任务 普通用户只可以编辑自己的计划任务 计划任务根据执行方式分为一次性计划任务、长期性计划任务 一次性计划任务 此计划只执行一次&#xff0c;执行后或就不会再执行了 通…...

Qt智能指针模板类的使用方式和区别总结

问题描述: 前面有篇文章,写了我建议在函数中new一个指针的时候最好使用QPointer模板类,这样就可以不用后面再加detele pointer的清除操作。当时觉得用QPointer的原因主要是QScopedPointer和QSharedPointer这两个类写起来太长了,费劲。所以觉得QPointer挺好的。 不过,看到…...

【STL】模拟实现vector

目录 1、基本成员变量 2、默认成员函数 构造函数 析构函数 拷贝构造函数 赋值运算符重载函数 3、容器访问相关函数接口 operator [ ]运算符重载 迭代器 范围for 4、vector容量和大小相关函数 size和capacity reserve扩容 resize swap交换数据 empty 5、修…...

Window 的 PHP XAMPP 安装 mongodb 的扩展

需要安装的扩展为&#xff1a;extensionphp_mongodb.dll根据官方的指引&#xff1a;PHP: Installing the MongoDB PHP Driver on Windows - Manual 1需要到 GitHub 上下载扩展&#xff0c;然后进行安装。这里的版本选择有些讲究。首先1.51 是 mongoDB 的驱动版本号&#xff0c;…...

Codeforces Round #849 (Div. 4)(E~G)

A~D比较简单就不写了&#xff0c;哎嘿E. Negatives and Positives给出一个数组a&#xff0c;可以对数组进行若干次操作&#xff0c;每次操作可以将相邻的两个数换为它们的相反数&#xff0c;求进行若干次操作之后能得到数组和的最大值是多少。思路&#xff1a;最大的肯定是把负…...

网易云音乐财报解读:收入大增亏损收窄,“云村”草长莺飞

独家版权时代结束后&#xff0c;在线音乐产业进入了新的发展阶段&#xff0c;各家音乐平台经营状况备受关注。 2月23日&#xff0c;网易云音乐公布了2022年全年财务业绩。财报显示&#xff0c;网易云音乐2022年全年收入为90亿元&#xff0c;较2021年同比增长28.5%。 值得一提的…...

MariaDB-10.8.6安装+主从搭建

【系统版本】CentOS 7.x Linux version 3.10.0-1062.18.1.el7.x86_64【检查系统是否安装过Mysql|mariadb】【查看是否安装Mysql|mariadb】#搜索mysql rpm -qa|grep mysql #搜索mariadb rpm -qa|grep mariadb #搜索MariaDB rpm -qa|grep MariaDB #如果安装过Mysql|mariadb&#…...

Win11系统user profile service服务登录失败解决方法

Win11系统user profile service服务登录失败解决方法分享。有用户在使用电脑的时候遇到了一些问题&#xff0c;系统的user profile service服务无法登录了。出现这个问题可能是系统文件损坏&#xff0c;或者中了病毒。接下来我们一起来看看如何解决这个问题的操作方法分享吧。 …...

Solon2 之基础:四、应用启动过程与完整生命周期

串行的处理过程&#xff08;含六个事件扩展点 两个函数扩展点&#xff09;&#xff0c;代码直接、没有什么模式。易明 提醒&#xff1a; 启动过程完成后&#xff0c;项目才能正常运行&#xff08;启动过程中&#xff0c;不能把线程卡死了&#xff09;AppBeanLoadEndEvent 之前…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving

地址&#xff1a;LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂&#xff0c;正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...