『力扣刷题本』:链表分割
一、题目
现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
二、思路解析
首先,让我们列出我们需要做的事情:
- 遍历整个链表;
- 对于值小于x的节点,把它们暂时存储起来,并从原链表中删除「删除是为了等下重新插入的时候,不造成元素重复的情况」;
- 最后,我们要把这些节点重新插入到链表的头部。
Sounds simple, right?
Step 1: 选择好用什么结构来存储值小于 x 的元素
这里我采用的是题解区中一位大佬的解法,他是用栈来存储那些待会要头插于链表的、值小于 x 的元素的。
我们首先定义一个栈来存储所有小于x的节点的值。
如果你对栈不熟悉,没关系,想象一下你在吃饭时堆放碗筷的样子,最后放上去的碗筷总是最先被取走,栈就是这样工作的。
Step 2: 遍历链表
遍历过程,如果我们遇到一个值小于x的节点,我们就把它的值压入栈中,并从原链表中删除这个节点。
如何删除节点,只需要把它前面节点的 next 指针指向它的下一个节点即可。
Step 3: 把栈中元素用头插法,插入链表
在我们遍历完链表后,所有小于x的节点都已经被保存在了栈中,而由于栈的先进后出特性,我们可以保证最早被删除的节点最后被添加回链表。
因此,我们从栈顶开始,每次弹出一个节点,然后创建一个新的节点,并将其添加到链表的头部。这样,我们就可以保证节点的原始顺序被保持。
这就是这道题的完整解题思路啦,下面请看完整代码~
三、完整代码
import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/public class Partition {public ListNode partition(ListNode pHead, int x) {// write code hereif(pHead == null){return null;}Stack<Integer> stack = new Stack<>();ListNode cur = pHead;ListNode prev = null;while(cur != null){if(cur.val < x){stack.add(cur.val);if(cur == pHead){pHead = pHead.next;cur = pHead;}else{cur = cur.next;prev.next = cur;}}else{prev = cur;cur = cur.next;}}while(!stack.isEmpty()){ListNode newNode = new ListNode(stack.pop());newNode.next = pHead;pHead = newNode;}return pHead;}
}
以上就是本篇博客的全部内容啦,如有不足之处,还请各位指出,期待能和各位一起进步!
相关文章:
『力扣刷题本』:链表分割
一、题目 现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。 二、思路解析 首先,让我们列出我们需要做的事情&…...
FISCOBCOS入门(十)Truffle测试helloworld智能合约
本文带你从零开始搭建truffle以及编写迁移脚本和测试文件,并对测试文件的代码进行解释,让你更深入的理解truffle测试智能合约的原理,制作不易,望一键三连 在windos终端内安装truffle npm install -g truffle 安装truffle时可能出现网络报错,多试几次即可 truffle --vers…...
Unity Text文本首行缩进两个字符的方法
Text文本首行缩进两个字符的方法比较简单。通过代码把"\u3000\u3000"加到文本字符串前面即可。 参考如下代码: TMPtext1.text "\u3000\u3000" "这是一段有首行缩进的文本内容。\n这是第二行"; 运行效果如下图所示: 虽…...
TS的函数重载、类型合并、类型断言
函数重载 let list5 [1, 2, 3, 4]function findNum(id: number): number[]function findNum(): number[]function findNum(list: number[]): number[]function findNum(ids?: number | number[]): number[] {if (typeof ids number) {return list5.filter((num) > num …...
JVM:字节码文件,类的生命周期,类加载器
JVM:字节码文件,类的生命周期,类加载器 为什么要学这门课程 1. 初识JVM1.1. 什么是JVM1.2. JVM的功能1.3. 常见的JVM 2. 字节码文件详解2.1. Java虚拟机的组成2.2. 字节码文件的组成2.2.1. 以正确的姿势打开文…...
【IPC】消息队列
1、IPC对象 除了最原始的进程间通信方式信号、无名管道和有名管道外,还有三种进程间通信方式,这 三种方式称之为IPC对象 IPC对象分类:消息队列、共享内存、信号量(信号灯集) IPC对象也是在内核空间开辟区域,每一种IPC对象创建好…...
内网穿透工具NPS(保姆级教程)
前言: 有时候我们受限于硬件设备和网络的的问题,无法将内网的大容量、高性能存储设备或计算设备对外访问。这个时候就会变的特别苦恼,上云呢成本太大,不用云呢公网又无法直接访问,这个时候怎么办呢,NPS它来…...
最长公共子序列问题
构造最长公共子序列为什么要这样构造序列 for(int i1;i<n;i){int k;cin>>k;b[k]i;}for(int i1;i<n;i){int k;cin>>k;a[i]b[k];}并且为什么要求上升序列,是有什么数学知识包含在其中吗? 为什么在求最长公共子序列时,f[mid]大…...
服务器数据恢复—热备盘同步中断导致Raid5数据丢失的数据恢复案例
服务器数据恢复环境: 某单位一台服务器上有一组raid5阵列,该raid5阵列有15块成员盘。上层是一个xfs裸分区,起始位置是0扇区。 服务器故障&检测: 服务器raid5阵列中有硬盘性能表现不稳定,但是由于管理员长时间没有关…...
桥接模式-C++实现
桥接模式是一种结构型设计模式,它是将抽象部分和实现部分隔离,通过组合关系将抽象部分和实现部分解耦,使它们可以独立变化。 因此,桥接模式可以很好的处理两个或两个以上维度的变化。 举一个例子说明: 假设我们现在…...
PHP字符串函数的解析
在PHP中,字符串是一种常见的数据类型,用于存储和操作文本数据。PHP提供了丰富的字符串函数,用于执行各种字符串操作,包括截取、连接、替换、搜索等。在这篇文章中,我们将深入解析一些常用的PHP字符串函数,以…...
科研学习|研究方法——使用python强大的Statsmodel 执行假设检验和线性回归
如果你使用 Python 处理数据,你可能听说过 statsmodel 库。 Statsmodels 是一个 Python 模块,它提供各种统计模型和函数来探索、分析和可视化数据。该库广泛用于学术研究、金融和数据科学。 在本文中,我们将介绍 statsmodel 库的基础知识、如…...
设计模式——责任链模式
文章目录 责任链模式的定义场景示例责任链模式实现方案责任链模式扩展责任链模式的优缺点责任链模式在框架源码中的应用 责任链模式的定义 责任链模式又称职责链模式,是一种行为型设计模式。官方描述:使多个对象都有机会处理请求,从而避免请…...
nginx得if语句内proxy_pass不允许携带url部分,如何处理
在nginx中,proxy_pass指令不能直接携带URL部分。但是,可以使用rewrite指令结合正则表达式来处理URL部分。 下面是一个示例配置,演示如何使用rewrite指令将URL中的某个部分进行替换后传递给后端服务器: location /v100/{proxy_…...
CentOS7设置 redis 开机自启动
CentOS7设置 redis 开机自启动 步骤1.创建redis.service文件2.重新加载所有服务3.设置开机自启动4.自由地使用linux系统命令4.1.启动 Redis 服务4.2.查看 Redis 状态(-l:查看完整的信息)4.3.停止 Redis 服务4.4.重启 Redis 服务 步骤 如果你傲娇,不想拷贝࿰…...
C++虚函数(定义,作用,原理,案例)
一.定义: C的虚函数是在父类(基类)中声明的的函数,它可在子类(派生类)中重写。二.作用 虚函数的目的是实现多态性,即在程序运行时根据对象的实际类型确定调用哪个函数。三.使用方法: 在基类中声明虚函数时,需要在函…...
C#中.NET 6.0 控制台应用通过EF访问新建数据库
目录 一、 操作步骤 二、编写EF模型和数据库上下文 三、 移植(Migrations)数据库 四、编写应用程序并运行 前文已经说过.NET Framework4.8 控制台应用通过EF访问新建数据库,这里的数据据库要根据事先编写好的EF模型、经过一番操作&#x…...
conda创建pytorch环境报错
昨天训练数据的时候,发现Anaconda占用C盘达到了20G(暑假在cmd状态下安装的,默认下载到了C盘),心道再创建几个环境,C盘就要爆红了,于是重装Anaconda到了D盘,不过之后的初始化并不顺利…...
数据结构-插入排序实现
文章目录 1、描述2、代码实现3、结果4、复杂度 1、描述 待排序的数组分为已排序、未排序两部分; 初始状态时,仅有第一个元素为已排序序列,第一个以外的元素为未排序序列; 此后遍历未排序序列, 将元素逐一插入到已排序的序列中&am…...
CGlib动态代理和JDK动态代理
CGlib代理模式是一种基于字节码操作的代理模式,它通过生成被代理类的子类来实现代理功能。 CGlib通过继承被代理类,生成一个代理类的子类,并重写父类的方法,在方法的前后插入相应的代理逻辑。这种方式不需要被代理类实现接口&…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
