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

C语言单链表OJ题(较难)

一、链表分割

牛客网链接

题目描述:

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

思路:

题目中要求不能改变原来的数据顺序,所以不能采用交换的方法写,应该单独创建两个链表,第一个链表尾插小于x的数据,另外一条链表尾插大于x的数据,最后将这两条链表进行链接。

尾插不改变原来数据顺序,头插将原来的数据顺序逆置

我们引用哨兵卫头结点解决这道题会更加方便。

不仅方便尾插,不需要分类判断空指针与否,而且也避免两个链表链接时第一个链表为空的情况。

TIP:

一般尾插时,最后一个结点的next容易出现问题,我们一般需要自己将其置成空指针

 代码:

#include <cstddef>
#include <cstdlib>
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* ghead,*gtail,*lhead,*ltail;//使用哨兵卫的头结点更加简单ghead=gtail=(struct ListNode*)malloc(sizeof(struct ListNode));lhead=ltail=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur=pHead;while(cur){if(cur->val < x){ltail->next=cur;ltail=ltail->next;}else {gtail->next=cur;gtail=gtail->next;}cur=cur->next;}gtail->next=NULL;//滞空,不然可能导致环形链表的出现ltail->next=ghead->next;struct ListNode* newhead=lhead->next;free(ghead);free(lhead);return newhead;}
};

二、链表的回文结构

牛客网链接

题目描述:

对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。

给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

测试样例:

1->2->2->1
返回:true

思路:

因为单链表只能从一个方向开始遍历,所以先让一串链表从中间结点开始往后逆置,接着两端链表进行比较。从中间结点开始逆置需要找中间结点,逆置也是之前讲过的,相当于再次复习巩固一遍

代码:

#include <cstddef>
class PalindromeList {
public:bool chkPalindrome(ListNode* head) {//寻找中间结点struct ListNode* fast=head;struct ListNode* slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}//从中间结点开始逆置struct ListNode* newhead=NULL;struct ListNode* cur=slow;struct ListNode* next=NULL;while(cur){next=cur->next;cur->next=newhead;newhead=cur;cur=next;}//开始判断while(head && newhead){if(head->val!=newhead->val){return false;}head=head->next;newhead=newhead->next;}return true;}
};

三、相交链表

leetcode链接

题目描述:

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

图示两个链表在节点 c1 开始相交

题目数据 保证 整个链式结构中不存在环。

思路:

首先有一个暴力解法,从第一条链表开始,将每一个结点的地址与第二条链表比较,直到找到相同的为止,这样的时间复杂度就是O(N^2),不太理想,下面将一个O(N)的算法:

首先判断有无相交结点,直接遍历两条链表,看尾结点的地址是否相同。

如果相同,则计算两条链表的结点的差值,接着让长的链表先走差值步,这时因为相交结点后面的个数一定相同,长的链表走差值步后,相交结点的前面也是相同个数的结点,直接一一比较地址是否相同,就不用遍历两遍了,也就是O(N)

代码:

truct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode* curA=headA;struct ListNode* curB=headB;int numA=1;int numB=1;//判断是否有相交的结点while(curA->next){curA=curA->next;numA++;}while(curB->next){curB=curB->next;numB++;}if(curA!=curB){return NULL;}int gap=abs(numA-numB);//直接假设长链表,不用if语句struct ListNode* longlist=headA;struct ListNode* shortlist=headB;if(numA<numB){longlist=headB;shortlist=headA;}//长的先走差距步,走gap步就是后置--while(gap--){longlist=longlist->next;}//在已知有公共结点的情况下,遍历返回while(1){if(longlist==shortlist){return longlist;}longlist=longlist->next;shortlist=shortlist->next;}
}

四、环形链表

leetcode链接

题目描述:

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

 思路:

本题要求较为简单,只需要判断是否含有环形结构,我们还是利用快慢指针的思想,快指针走两步,慢指针走一步,如果不带环,则快指针作为循环判断的条件,如果带环,则最后两者肯定会相遇,直到快慢指针地址相同时跳出循环

代码:

bool hasCycle(struct ListNode *head) 
{struct ListNode* slow=head;struct ListNode* fast=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){return true;}}return false;
}            

五、环形链表(进阶)

142. 环形链表 II - 力扣(LeetCode)

题目描述:

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

思路一:

本题主要找环形链表进入环的第一个节点,当然需要判断是不是环形链表,判断后需要进行一个数学的函数证明

 经过计算验证,我们发现一个指针从起点走,另外一个从相遇点走,在相同步伐下,他们会在入口点相遇

有这样一个等式,接下来就只需要找相遇点,正好上一题我们就找的是相遇点。

代码:

struct ListNode *detectCycle(struct ListNode *head) 
{struct ListNode* slow = head;struct ListNode* fast = head;struct ListNode* meet = NULL;struct ListNode* cur = head;//先判断是否有环while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){//找到相遇结点meet = slow;break;}}if(meet==NULL){return NULL;}//相遇节点与头结点一起走,直到相等,就是入口while(1){if(meet==cur){return meet;}meet=meet->next;cur=cur->next;}
}

思路二:

利用相交链表的思路。

首先也是找到相遇点,然后将相遇点的后面的结点断掉,这样就形成了两个链表,一条链表从头结点开始,另一条链表从断口开始。并且这两个链表的交点就是我们的入口点!

struct ListNode *detectCycle(struct ListNode *head) 
{struct ListNode* slow = head;struct ListNode* fast = head;struct ListNode* meet = NULL;struct ListNode* cur = head;//先判断是否有环while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){//找到相遇结点meet = slow;break;}}if(meet==NULL){return NULL;}//struct ListNode* newhead = meet->next;meet->next = NULL;struct ListNode* curnew = newhead;//开始相交链表int len1 = 0;int len2 = 0;while(curnew){curnew=curnew->next;len1++;}while(cur){cur=cur->next;len2++;}int gap=abs(len1-len2);struct ListNode* longlist = newhead;struct ListNode* shortlist = head;if(len1<len2){longlist = head;shortlist=newhead;}while(gap--){longlist=longlist->next;}while(1){if(longlist==shortlist){return longlist;}longlist=longlist->next;shortlist=shortlist->next;}}

六、复制带随机值指针的链表

138. 复制带随机指针的链表 - 力扣(LeetCode)

题目描述:

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为  null 。

你的代码  接受原链表的头节点 head 作为传入参数。

思路:

本题要求拷贝一串链表,并且结点中含有随机值指向,并且要求拷贝的链表与原链表一样,随机域也要指向一样。

  1. 首先,我们将拷贝的结点一个一个插在原结点后面
  2. 这时拷贝结点的随机指针域就是原结点指向的随机指针域的next.
  3. 再取拷贝结点组成新的链表

代码:

struct Node* copyRandomList(struct Node* head) 
{struct Node* copy = NULL;struct Node* next = NULL;struct Node* cur = head;while(cur){//copy结点放在原结点后面next = cur->next;copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;cur->next = copy;copy->next = next;cur = copy->next;}//拷贝随机指针cur = head;while(cur){copy = cur->next;if(cur->random == NULL){copy->random = NULL;}else{   //关键copy->random = cur->random->next;}cur = copy->next;}struct Node* copyhead = NULL;struct Node* copytail = NULL;cur = head;while(cur){//将copy组装成一个新链表(尾插)copy = cur->next;if(copyhead == NULL){copyhead = copytail = copy;}else{//尾插copytail->next = copy;copytail = copytail->next;}//恢复原链表cur->next = copy->next;cur = cur->next;}return copyhead;
}

 

相关文章:

C语言单链表OJ题(较难)

一、链表分割 牛客网链接 题目描述&#xff1a; 现有一链表的头指针 ListNode* pHead&#xff0c;给一定值x&#xff0c;编写一段代码将所有小于x的结点排在其余结点之前&#xff0c;且不能改变原来的数据顺序&#xff0c;返回重新排列后的链表的头指针。 思路&#xff1a;…...

工业巡检ar沉浸式互动培训体验实现更加直观、生动的流程展示

以往的工业手工巡检效率极低&#xff0c;错误率偏高&#xff0c;漏检问题严重&#xff0c;会因为现场人员对机械设备的早期维护、操作不会&#xff0c;而影响正常交付和服务&#xff0c;智慧工业是工业智能化和信息化的重要体现&#xff0c;在巡检方面自然也要同步提升&#xf…...

【Spring】核心容器——依赖自动装配

Spring容器根据bean所依赖的资源在容器中自动查找并注入bean的过程叫做自动装配自动装配的方式 1、按类型 2、按名称&#xff08;耦合性较高&#xff09; 3、按构造方法 自动装配特点 1、自动装配用于对引用类型进行依赖注入&#xff0c;不能对简单类型进行操作 2、自动装配的…...

TestNG和Junit5测试框架梳理

一、testNG 1. testNG优势 注解驱动&#xff1a; TestNG 使用注解来标识测试方法、测试类和配置方法&#xff0c;使得测试更具可读性。 并行执行&#xff1a; TestNG 支持多线程并行执行测试&#xff0c;可以加速测试套件的执行。 丰富的配置&#xff1a; 可以通过 XML 配置文…...

算法练习Day46|139.单词拆分

LeetCode:139.单词拆分 139. 单词拆分 - 力扣&#xff08;LeetCode&#xff09; 1.思路 字符串是否能被字符串列表中的元素拼接出来&#xff0c;显然是一个背包问题&#xff0c;而且需要排列。 将字典转换为HashSet,利用.contains()方法判断是否存在元素与背包中的子串相同…...

Maven工程的安装配置及搭建(集成eclipse完成案例,保姆级教学)

目录 一.下载及安装及环境配置 1.下载及安装 2.环境变量的配置 3.检测是否安装成功 4.配置Maven 1.更换本地仓库 2. 配置镜像 二.集成eclipse完成案例 1.eclipse前期配置Maven 2.创建Maven工程 一.下载及安装及环境配置 1.下载及安装 下载地址&#xff1a;Maven – Down…...

82 | Python可视化篇 —— Plotly数据可视化

文章目录 什么是 Plotly安装 Plotly创建散点图创建线图创建条形图创建饼图创建热力图3D图(3D Plot)直方图(Histogram)3D表面图(3D Surface Plot)箱线图(Box Plot)散点地图(Scatter Map)量级地图(Choropleth Map)在网页中嵌入 Plotly 图表总结什么是 Plotly Plotly…...

Golang 包详解以及go mod

Golang 中包的介绍和定义 包(package)是多个 Go 源码的集合,是一种高级的代码复用方案,Go 语言为我们提供了 很多内置包,如 fmt、strconv、strings、sort、errors、time、encoding/json、os、io 等。 Golang 中的包可以分为三种:1、系统内置包 2、自定义包 3、第三方包…...

中级课程-SSRF(CSRF进阶)

文章目录 成因危害挖掘 成因 危害 挖掘...

C++命名空间

目录 格式 使用 命名空间的嵌套 使用 using声明 命名空间里面包含了逻辑结构上相互关联的一组类、函数、模板等。命名空间像是一个容器&#xff0c;把某些在逻辑结构上相关的 “ 对象 ” 放在一起并与外界区分。特别的&#xff0c;命名空间里的变量名或类名可以和命名空间外…...

阿里云服务器搭建Magento电子商务网站图文教程

本文阿里云百科分享使用阿里云服务器手动搭建Magento电子商务网站全流程&#xff0c;Magento是一款开源电商网站框架&#xff0c;其丰富的模块化架构体系及拓展功能可为大中型站点提供解决方案。Magento使用PHP开发&#xff0c;支持版本范围从PHP 5.6到PHP 7.1&#xff0c;并使…...

Docker安装 Kibana

目录 前言安装Kibana步骤1&#xff1a;准备1. 安装docker2. 搜索可以使用的镜像。3. 也可从docker hub上搜索镜像。4. 选择合适的redis镜像。 步骤2&#xff1a;拉取 kibana 镜像拉取镜像查看已拉取的镜像 步骤3&#xff1a;创建容器创建容器方式1&#xff1a;快速创建容器 步骤…...

数字图像处理 --- 相机的内参与外参(CV学习笔记)

Pinhole Camera Model&#xff08;针孔相机模型&#xff09; 针孔相机是一种没有镜头、只有一个小光圈的简单相机。 光线穿过光圈并在相机的另一侧呈现倒立的图像。为了建模方便&#xff0c;我们可以把物理成像平面(image plane)上的图像移到实际场景(3D object)和焦点(focal p…...

基于新浪微博海量用户行为数据、博文数据数据分析:包括综合指数、移动指数、PC指数三个指数

基于新浪微博海量用户行为数据、博文数据数据分析&#xff1a;包括综合指数、移动指数、PC指数三个指数 项目介绍 微指数是基于海量用户行为数据、博文数据&#xff0c;采用科学计算方法统计得出的反映不同事件领域发展状况的指数产品。微指数对于收录的关键词&#xff0c;在指…...

金融反欺诈的应用实践

“根据980起全球重大金融欺诈事件分析&#xff0c;60%的欺诈发生在移动端&#xff0c;同比增长170%。“&#xff0c;在香港近日举办的金融科技沙龙上&#xff0c;顶象金融业务安全专家史博表示&#xff0c;金融业已成为不法分子重要的攻击对象。 本届金融科技沙龙由Databricks…...

Win10启动Jmeter报错提示jmeter.log拒绝访问问题

jmeter版本&#xff1a;5.4.1 查看版本 在dos命令窗口中进入jmeter安装目录下的bin目录中&#xff1a;执行jmeter - v命令 我启动的方式是&#xff1a;进入jmeter安装目录下的bin目录中双击jmeter.bat启动的。结果报错&#xff0c;但是不影响使用。 报错日志如下&#xff1a; …...

Vue中使用Tailwind css

1.什么是Tailwind 就是一个CSS框架&#xff0c;和你知道的bootstrap&#xff0c;element ui&#xff0c;Antd&#xff0c;bulma。一样。将一些css样式封装好&#xff0c;用来加速我们开发的一个工具。 Tailwind解释 tailwind css 中文文档 2.Vue使用Tailwind配置 1. 新建vu…...

承接各种设计

小弟985研究生毕业&#xff0c;目前攻读读博士&#xff0c;可做各种设计&#xff0c;包括但不限于Matlab 电力电子/电气工程&#xff0c;matlab/simulink 电气专业仿真MATLAB 电气工程专业&#xff0c;matlab建模 电力电子&#xff0c;电气工程&#xff0c;电力系统&#xff0c…...

HTTP请求性能分析 - 简单

使用随手可得的工具&#xff0c;尽量少的前置要求&#xff0c;来完成任务。 0. 目录 1. 前言2. 分析工具2.1 基于Chrome DevTools 的Timing2.1.1 关于Network标签页下的Timing部分2.1.2 一些注意项 2.2 基于Curl 命令 3. 剩下的工作 1. 前言 对于业务开发选手而言&#xff0c;…...

腾讯云标准型CVM云服务器详细介绍

腾讯云CVM服务器标准型实例的各项性能参数平衡&#xff0c;标准型云服务器适用于大多数常规业务&#xff0c;例如&#xff1a;web网站及中间件等&#xff0c;常见的标准型云服务器有CVM标准型S5、S6、SA3、SR1、S5se等规格&#xff0c;腾讯云服务器网来详细说下云服务器CVM标准…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...