当前位置: 首页 > 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;在方法的前后插入相应的代理逻辑。这种方式不需要被代理类实现接口&…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

如何做好一份技术文档?从规划到实践的完整指南

如何做好一份技术文档&#xff1f;从规划到实践的完整指南 &#x1f31f; 嗨&#xff0c;我是IRpickstars&#xff01; &#x1f30c; 总有一行代码&#xff0c;能点亮万千星辰。 &#x1f50d; 在技术的宇宙中&#xff0c;我愿做永不停歇的探索者。 ✨ 用代码丈量世界&…...

【Zephyr 系列 16】构建 BLE + LoRa 协同通信系统:网关转发与混合调度实战

🧠关键词:Zephyr、BLE、LoRa、混合通信、事件驱动、网关中继、低功耗调度 📌面向读者:希望将 BLE 和 LoRa 结合应用于资产追踪、环境监测、远程数据采集等场景的开发者 📊篇幅预计:5300+ 字 🧭 背景与需求 在许多 IoT 项目中,单一通信方式往往难以兼顾近场数据采集…...

中国政务数据安全建设细化及市场需求分析

(基于新《政务数据共享条例》及相关法规) 一、引言 近年来,中国政府高度重视数字政府建设和数据要素市场化配置改革。《政务数据共享条例》(以下简称“《共享条例》”)的发布,与《中华人民共和国数据安全法》(以下简称“《数据安全法》”)、《中华人民共和国个人信息…...

Linux系统:进程间通信-匿名与命名管道

本节重点 匿名管道的概念与原理匿名管道的创建命名管道的概念与原理命名管道的创建两者的差异与联系命名管道实现EchoServer 一、管道 管道&#xff08;Pipe&#xff09;是一种进程间通信&#xff08;IPC, Inter-Process Communication&#xff09;机制&#xff0c;用于在不…...