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

『力扣刷题本』:链表分割

一、题目

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

二、思路解析

首先,让我们列出我们需要做的事情:

  1. 遍历整个链表;
  2. 对于值小于x的节点,把它们暂时存储起来,并从原链表中删除「删除是为了等下重新插入的时候,不造成元素重复的情况」;
  3. 最后,我们要把这些节点重新插入到链表的头部。

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&#xff0c;给一定值x&#xff0c;编写一段代码将所有小于x的结点排在其余结点之前&#xff0c;且不能改变原来的数据顺序&#xff0c;返回重新排列后的链表的头指针。 二、思路解析 首先&#xff0c;让我们列出我们需要做的事情&…...

FISCOBCOS入门(十)Truffle测试helloworld智能合约

本文带你从零开始搭建truffle以及编写迁移脚本和测试文件,并对测试文件的代码进行解释,让你更深入的理解truffle测试智能合约的原理,制作不易,望一键三连 在windos终端内安装truffle npm install -g truffle 安装truffle时可能出现网络报错,多试几次即可 truffle --vers…...

Unity Text文本首行缩进两个字符的方法

Text文本首行缩进两个字符的方法比较简单。通过代码把"\u3000\u3000"加到文本字符串前面即可。 参考如下代码&#xff1a; TMPtext1.text "\u3000\u3000" "这是一段有首行缩进的文本内容。\n这是第二行"; 运行效果如下图所示&#xff1a; 虽…...

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&#xff1a;字节码文件&#xff0c;类的生命周期&#xff0c;类加载器 为什么要学这门课程 1. 初识JVM1.1. 什么是JVM1.2. JVM的功能1.3. 常见的JVM 2. 字节码文件详解2.1. Java虚拟机的组成2.2. 字节码文件的组成2.2.1. 以正确的姿势打开文…...

【IPC】消息队列

1、IPC对象 除了最原始的进程间通信方式信号、无名管道和有名管道外&#xff0c;还有三种进程间通信方式&#xff0c;这 三种方式称之为IPC对象 IPC对象分类&#xff1a;消息队列、共享内存、信号量(信号灯集) IPC对象也是在内核空间开辟区域&#xff0c;每一种IPC对象创建好…...

内网穿透工具NPS(保姆级教程)

前言&#xff1a; 有时候我们受限于硬件设备和网络的的问题&#xff0c;无法将内网的大容量、高性能存储设备或计算设备对外访问。这个时候就会变的特别苦恼&#xff0c;上云呢成本太大&#xff0c;不用云呢公网又无法直接访问&#xff0c;这个时候怎么办呢&#xff0c;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];}并且为什么要求上升序列&#xff0c;是有什么数学知识包含在其中吗&#xff1f; 为什么在求最长公共子序列时&#xff0c;f[mid]大…...

服务器数据恢复—热备盘同步中断导致Raid5数据丢失的数据恢复案例

服务器数据恢复环境&#xff1a; 某单位一台服务器上有一组raid5阵列&#xff0c;该raid5阵列有15块成员盘。上层是一个xfs裸分区&#xff0c;起始位置是0扇区。 服务器故障&检测&#xff1a; 服务器raid5阵列中有硬盘性能表现不稳定&#xff0c;但是由于管理员长时间没有关…...

桥接模式-C++实现

桥接模式是一种结构型设计模式&#xff0c;它是将抽象部分和实现部分隔离&#xff0c;通过组合关系将抽象部分和实现部分解耦&#xff0c;使它们可以独立变化。 因此&#xff0c;桥接模式可以很好的处理两个或两个以上维度的变化。 举一个例子说明&#xff1a; 假设我们现在…...

PHP字符串函数的解析

在PHP中&#xff0c;字符串是一种常见的数据类型&#xff0c;用于存储和操作文本数据。PHP提供了丰富的字符串函数&#xff0c;用于执行各种字符串操作&#xff0c;包括截取、连接、替换、搜索等。在这篇文章中&#xff0c;我们将深入解析一些常用的PHP字符串函数&#xff0c;以…...

科研学习|研究方法——使用python强大的Statsmodel 执行假设检验和线性回归

如果你使用 Python 处理数据&#xff0c;你可能听说过 statsmodel 库。 Statsmodels 是一个 Python 模块&#xff0c;它提供各种统计模型和函数来探索、分析和可视化数据。该库广泛用于学术研究、金融和数据科学。 在本文中&#xff0c;我们将介绍 statsmodel 库的基础知识、如…...

设计模式——责任链模式

文章目录 责任链模式的定义场景示例责任链模式实现方案责任链模式扩展责任链模式的优缺点责任链模式在框架源码中的应用 责任链模式的定义 责任链模式又称职责链模式&#xff0c;是一种行为型设计模式。官方描述&#xff1a;使多个对象都有机会处理请求&#xff0c;从而避免请…...

nginx得if语句内proxy_pass不允许携带url部分,如何处理

在nginx中&#xff0c;proxy_pass指令不能直接携带URL部分。但是&#xff0c;可以使用rewrite指令结合正则表达式来处理URL部分。 下面是一个示例配置&#xff0c;演示如何使用rewrite指令将URL中的某个部分进行替换后传递给后端服务器&#xff1a; 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 服务 步骤 如果你傲娇&#xff0c;不想拷贝&#xff0…...

C++虚函数(定义,作用,原理,案例)

一.定义&#xff1a; C的虚函数是在父类(基类)中声明的的函数&#xff0c;它可在子类(派生类)中重写。二.作用 虚函数的目的是实现多态性&#xff0c;即在程序运行时根据对象的实际类型确定调用哪个函数。三.使用方法&#xff1a; 在基类中声明虚函数时&#xff0c;需要在函…...

C#中.NET 6.0 控制台应用通过EF访问新建数据库

目录 一、 操作步骤 二、编写EF模型和数据库上下文 三、 移植&#xff08;Migrations&#xff09;数据库 四、编写应用程序并运行 前文已经说过.NET Framework4.8 控制台应用通过EF访问新建数据库&#xff0c;这里的数据据库要根据事先编写好的EF模型、经过一番操作&#x…...

conda创建pytorch环境报错

昨天训练数据的时候&#xff0c;发现Anaconda占用C盘达到了20G&#xff08;暑假在cmd状态下安装的&#xff0c;默认下载到了C盘&#xff09;&#xff0c;心道再创建几个环境&#xff0c;C盘就要爆红了&#xff0c;于是重装Anaconda到了D盘&#xff0c;不过之后的初始化并不顺利…...

数据结构-插入排序实现

文章目录 1、描述2、代码实现3、结果4、复杂度 1、描述 待排序的数组分为已排序、未排序两部分; 初始状态时&#xff0c;仅有第一个元素为已排序序列&#xff0c;第一个以外的元素为未排序序列&#xff1b; 此后遍历未排序序列&#xff0c; 将元素逐一插入到已排序的序列中&am…...

CGlib动态代理和JDK动态代理

CGlib代理模式是一种基于字节码操作的代理模式&#xff0c;它通过生成被代理类的子类来实现代理功能。 CGlib通过继承被代理类&#xff0c;生成一个代理类的子类&#xff0c;并重写父类的方法&#xff0c;在方法的前后插入相应的代理逻辑。这种方式不需要被代理类实现接口&…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...

鸿蒙(HarmonyOS5)实现跳一跳小游戏

下面我将介绍如何使用鸿蒙的ArkUI框架&#xff0c;实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...