链表OJ练习(2)
一、分割链表
题目介绍:
思路:创建两个链表,ghead尾插大于x的节点,lhead尾插小于x的节点。先遍历链表。最后将ghead尾插到lhead后面,将大小链表链接。
我们需要在创建两个链表指针,指向两个链表的头节点,用这两个指针标记lhead和ghead的尾结点,方便与尾插。
注:极端边界场景:所有值都小于x; 所有值都大于x; 空链表。
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/class Partition {
public:ListNode* partition(ListNode* pHead, int x){ListNode* gtail, * ghead, * ltail, * lhead;gtail = ghead = (struct ListNode*)malloc(sizeof(struct ListNode));ltail = lhead = (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;}ltail->next = ghead->next;gtail->next = NULL;struct ListNode* newhead = lhead->next;free(lhead);free(ghead);return newhead;}
};
二、回文链表
题目介绍:

思路:先找到中间节点,可以利用快慢指针找到中间节点,然后将中间节点后面的节点翻转,在和中间节点前面的链表依次比较,如果全部相同则是回文链表否则不是。
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
//struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* falst;struct ListNode* slow;falst = head;slow = head;while (falst && falst->next){slow = slow->next;falst = falst->next->next;}return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur = head;struct ListNode* newhead = NULL;while (cur){struct ListNode* next = cur->next;//头插cur->next = newhead;newhead = cur;cur = next;}return newhead;
}class PalindromeList
{
public:bool chkPalindrome(ListNode* head){//找到中间节点,将中间节点后面的链表翻转,有第一个和中间节点比较,并依次后移,若全部相同,则为回文链表,反之不是。struct ListNode* mid = middleNode(head);struct ListNode* rmid = reverseList(mid);while (rmid && mid){if (rmid->val != head->val){return false;}head = head->next;rmid = rmid->next;}return true;}};
三、找公共点
题目介绍:



思路:先遍历两个链表,计算出两个链表的长度,让后计算出两个链表的长度差k,将长的链表先往前走k步,然后将两个链表指针同时后移,找到第一个相同的节点就是相交节点。
注:需要考虑到空链表,给链表判空,若空headA和headB其中一个为空返回NULL。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* curA = headA;struct ListNode* curB = headB;int lenA = 1;int lenB = 1;if(headA==NULL||headB==NULL){return NULL;}while (curA->next){curA = curA->next;lenA++;}while (curB->next){curB = curB->next;lenB++;}if (curA != curB) //没有交点{return false;}int gap = abs(lenA - lenB);struct ListNode* falst = headA;struct ListNode* slow = headB;if (lenA < lenB){falst = headB;slow = headA;}while (gap--){falst = falst->next;}while (slow != falst){slow = slow->next;falst = falst->next;}return slow;
}
四、判断是否是环形链表
题目介绍:



思路:还是利用快慢指针,当慢指针往前走一步,快指针往前走两步,在一个环中,每次他们的距离就减少一,如果有环,就一定能追上。如果没追上则没有环。
用快指针遍历。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head)
{struct ListNode *falst=head;struct ListNode *slow=head;while(falst&&falst->next){falst=falst->next->next;slow=slow->next;if(falst==slow){return true;}}return false;
}
五、寻找环形链表的入环节点
题目描述:


思路1:假设链表带环,头节点head与入环节点的距离为L,入环节点与相遇点的距离为D,环的大小为C,如下图:

fast从头节点到相遇点:L + D + kC,其中k为正整数,表示在快慢指针相遇前fast所走圈数
slow从头节点到相遇点:L + D
又由于fast每次走两步,slow每次走一步,以上二式可以建立起联系:
L + D + kC = 2 * (L + D)
L = kC - D = (k - 1) * C + C - D
所以可以得出结论:一个指针从相遇点开始走,一个指针从链表头开始走,则这两个指针一定会在入环节点处相遇。
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast=head, *slow=head;while(fast && fast->next){fast=fast->next->next;slow = slow->next;if(fast == slow){//找相遇点meetNodestruct ListNode* meetNode = fast;//相遇点可能就是入环节点if(meetNode == head)return head;//meetNode和head开始每次走一步,直到相遇while(head && meetNode){meetNode = meetNode->next;head = head->next;//当相遇时即为入环节点if(meetNode == head)return meetNode;}}}return NULL;
}
思路2:我们可以在相遇点将链表断开,找到如节点就相当于找到两个链表的交点。
找两个链表的交点我们可以参考题目三
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode *curA=headA;struct ListNode *curB=headB;int lenA=1;int lenB=1;while(curA->next){curA=curA->next;lenA++;}while(curB->next){curB=curB->next;lenB++;}if(curA!=curB) //没有交点{return false;}int gap=abs(lenA-lenB);struct ListNode *falst=headA;struct ListNode *slow=headB;if(lenA<lenB){falst=headB;slow=headA;}while(gap--){falst=falst->next;}while(slow!=falst){slow=slow->next;falst=falst->next;}return slow;
}
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode *fast=head;struct ListNode *slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast) //相遇了{struct ListNode *meet=slow; //将环断开struct ListNode *newhead=meet->next;meet->next=NULL;return getIntersectionNode(head,newhead); //找两个链表的交点}}return NULL;
}相关文章:
链表OJ练习(2)
一、分割链表 题目介绍: 思路:创建两个链表,ghead尾插大于x的节点,lhead尾插小于x的节点。先遍历链表。最后将ghead尾插到lhead后面,将大小链表链接。 我们需要在创建两个链表指针,指向两个链表的头节点&…...
ssh常用操作
ssh常用操作 SSH是一种安全协议,ssh是该协议的客户端程序,openssh-server则是该协议的服务端程序 常用系统都自带了ssh客户端程序,服务端程序则可能要安装 密码远程登陆 前提:服务器安装了openssh-server,未安装时…...
从AD迁移至AAD,看体外诊断领军企业如何用网络准入方案提升内网安全基线
摘要: 某医用电子跨国集团中国分支机构在由AD向AzureAD Global迁移时,创新使用宁盾网络准入,串联起上海、北京、无锡等国内多个职场与海外总部,实现平滑、稳定、全程无感知的无密码认证入网体验,并通过合规基线检查,确…...
Flutter系列文章-Flutter在实际业务中的应用
不同场景下的解决方案 1. 跨平台开发: 在移动应用开发中,面对不同的平台(iOS和Android),我们通常需要编写两套不同的代码。而Flutter通过一套代码可以构建适用于多个平台的应用,大大提高了开发效率&#x…...
FPGA | Verilog仿真VHDL文件
当VHDL模块中有Generic块时,应该怎么例化? VHDL模块代码 entity GenericExample isgeneric (DATA_WIDTH : positive : 8; -- 泛型参数:数据宽度ENABLE_FEATURE : boolean : true -- 泛型参数:是否启用特定功能);Port ( clk : …...
微服务--Gatway:网关
routes: - id:order_route(路由唯一 标识,路由到order) uri:http://localhost:8020 #需要转发的地址 #断言规则(用于路由规则的匹配) predicates: -path/order-serv/** -pathlb://order-service # lb: 使用nacos中的本地…...
Django传递dataframe对象到前端网页
在django前端页面上展示的数据,还是使用django模板自带的语法 方式1 不推荐使用 直接使用 【df.to_html(indexFalse)】 使用to_html他会生成一个最基本的表格没有任何的样式,一点都不好看,如果有需要的话可以自行修改表格的样式,…...
iOS swift5 弹出提示文字(停留1~2s)XHToastSwift
CoderZhuXH/XHToastSwift - github // // XHToast.swift // XHToastSwiftExample // // Created by xiaohui on 16/8/12. // Copyright © 2016年 CoderZhuXH. All rights reserved. // 代码地址:https://github.com/CoderZhuXH/XHToastSwiftimport UIKit/*** Toast…...
Spring Bean 的生命周期,如何被管理的
实例化一个Bean,也就是我们通常说的new 按照Spring上下文对实例化的Bean进行配置,也就是IOC注入 如果这个Bean实现了BeanNameAware接口,会调用它实现的setBeanName(String beanId)方法,此处传递的是Spring配置文件中Bean的ID 如…...
MATLAB算法实战应用案例精讲-【概念篇】量子机器学习
目录 前言 几个高频面试题目 机器学习的方法论 知识储备 机器学习的实现...
【kubernetes】Argo Rollouts -- k8s下的自动化蓝绿部署
蓝绿(Blue-Green)部署简介 在现代软件开发和交付中,确保应用程序的平稳更新和发布对于用户体验和业务连续性至关重要。蓝绿部署是一种备受推崇的部署策略,它允许开发团队在不影响用户的情况下,将新版本的应用程序引入生产环境。 蓝绿部署的核心思想在于维护两个独立的环…...
vue Cesium接入在线地图
Cesium接入在线地图只需在创建时将imageryProvider属性换为在线地图的地址即可。 目录 天地图 OSM地图 ArcGIS 地图 谷歌影像地图 天地图 //矢量服务let imageryProvider new Cesium.WebMapTileServiceImageryProvider({url: "http://t0.tianditu.com/vec_w/wmts?s…...
OBS Studio 30.0 承诺在 Linux 上支持英特尔 QSV,为 DeckLink 提供 HDR 回放功能
导读OBS Studio 30.0 现已推出公开测试版,承诺为这款广受欢迎的免费开源截屏和流媒体应用程序提供多项令人兴奋的新功能,以及大量其他更改和错误修复。 OBS Studio 30.0 承诺在 Linux 上支持英特尔 QSV(快速同步视频)、WHIP/WebRT…...
springboot整合SpringSecurity
先写了一个配置类 给这个访问路径,加上角色权限 package com.qf.config;import org.springframework.security.config.annotation.web.builders.HttpSecurity; import org.springframework.security.config.annotation.web.configuration.EnableWebSecurity; impo…...
最近在搭建ELK日志平台时,logstash报错JSON parse error
直接进入正题,我在搭建elk日志,使用最简单的log4j2 socket json格式 输出到logstash. 但是logstash报错如下: [WARN ] 2023-08-30 10:15:17.766 [nioEventLoopGroup-2-2] jsonlines - JSON parse error, original data now in message field…...
某次护网红队getshell的经历
信息收集 某企业提供信息:企业官网的真实外网ip,内网ip 企业官网比较硬,从控股超过51%的子公司入手 通过企查查找到一堆控股高的子公司,通过ICP/IP地址/域名信息备案管理系统查找子公司官网,收集二级域名。通过google…...
C#实现日期选择器、显示当地时间、跑马灯等功能
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System...
如何让看书变听书?
听书神器 安卓 页面简单,易操作,全网小说随便听 各种声音帮你读你喜欢听的小说,带你进入主人公世界 支持网页版小说、本地小说、图片,都能读给你听 想看小说,又怕伤眼睛的宝子,可以试试看!…...
pytorch异常——loss异常,不断增大,并且loss出现inf
文章目录 异常报错异常截图异常代码原因解释修正代码执行结果 异常报错 epoch1:loss3667.782471 epoch2:loss65358620.000000 epoch3:loss14979486720.000000 epoch4:loss1739650891776.000000 epoch5:loss12361745880317952.000000 epoch6:loss2740315398365287284736.000000…...
Lua学习(一)
lua基础学习 LUA 语言1. 什么是lua?1.1 准备工作 2. 基本语法2.1 注释2.2 标识符2.3 关键字2.4 全局变量 3. 数据类型4. 变量4.1 赋值语句 5. 循环5.1 while循环5.2 for循环5.3泛型for循环5.4 repeat until 循环5.5 break 语句 6. 流程控制6.1 if语句6.2 if else 语…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...
rknn toolkit2搭建和推理
安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 ,不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源(最常用) conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...
文件上传漏洞防御全攻略
要全面防范文件上传漏洞,需构建多层防御体系,结合技术验证、存储隔离与权限控制: 🔒 一、基础防护层 前端校验(仅辅助) 通过JavaScript限制文件后缀名(白名单)和大小,提…...
链式法则中 复合函数的推导路径 多变量“信息传递路径”
非常好,我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题,统一使用 二重复合函数: z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y)) 来全面说明。我们会展示其全微分形式(偏导…...
JavaScript 标签加载
目录 JavaScript 标签加载script 标签的 async 和 defer 属性,分别代表什么,有什么区别1. 普通 script 标签2. async 属性3. defer 属性4. type"module"5. 各种加载方式的对比6. 使用建议 JavaScript 标签加载 script 标签的 async 和 defer …...
RLHF vs RLVR:对齐学习中的两种强化方式详解
在语言模型对齐(alignment)中,强化学习(RL)是一种重要的策略。而其中两种典型形式——RLHF(Reinforcement Learning with Human Feedback) 与 RLVR(Reinforcement Learning with Ver…...
信息系统分析与设计复习
2024试卷 单选题(20) 1、在一个聊天系统(类似ChatGPT)中,属于控制类的是()。 A. 话语者类 B.聊天文字输入界面类 C. 聊天主题辨别类 D. 聊天历史类 解析 B-C-E备选架构中分析类分为边界类、控制类和实体类。 边界…...
