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

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

python/java环境配置

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

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

DiscuzX3.5发帖json api

参考文章&#xff1a;PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下&#xff0c;适配我自己的需求 有一个站点存在多个采集站&#xff0c;我想通过主站拿标题&#xff0c;采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...

goreplay

1.github地址 https://github.com/buger/goreplay 2.简单介绍 GoReplay 是一个开源的网络监控工具&#xff0c;可以记录用户的实时流量并将其用于镜像、负载测试、监控和详细分析。 3.出现背景 随着应用程序的增长&#xff0c;测试它所需的工作量也会呈指数级增长。GoRepl…...