【Leetcode 程序员面试金典 02.04】 —— 分割链表|双指针-程序员宅基地
技术标签： java 链表 leetcode 双指针 Leetcode
面试题02.04. 分割链表
给你一个链表的头节点head和一个特定值x，请你对链表进行分隔，使得所有 小于 x的节点都出现在 大于或等于 x的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
示例1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]
题目分析
我们可以使用双指针解决本题，定义两个链表 small 和 big 即可，small 链表按顺序存储所有小于 x 的节点，big 链表按顺序存储所有大于等于 x 的节点。
遍历完原链表后，我们只要将 small 链表尾节点指向 big 链表的头节点即能完成对链表的分割
双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息
经典双指针的数组遍历，更多案例可见 Leetcode 双指针详解
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
// 新建起始节点，方便处理头节点为空的边界条件
ListNode small = new ListNode(0), big = new ListNode(0);
ListNode smallHead = small, bigHead = big;
while(head != null){
// 判断值以决定加入small/big链表
if (head.val < x) {
small.next = head;
small = small.next;
} else {
big.next = head;
big = big.next;
}
head = head.next;
}
// 尾结点
big.next = null;
// 小值链表接大值链表
small.next = bigHead.next;
return smallHead.next;
}
}
智能推荐
java使用密文链接数据库_Java基础——数据库连接信息使用密文-程序员宅基地
文章浏览阅读492次。背景数据库连接配置文件一般都是使用明文，这会带来数据库泄露的安全问题。例如jdbc.properties配置文件中，数据库连接地址、用户名、密码都是明文，如何使配置文件中的数据库连接信息避免明文显示是本文重点内容，即如何使配置信息使用密文就可以达到跟明文一样的效果。分析假如数据库连接密码使用了密文。修改连接池源码顾名思义，修改dbcp、c3p0、Druid连接池的源码，先对加密的密码解密，然后再创..._java读取加密的密码连接数据库
鸿蒙操作系统游戏模式,鸿蒙OS 2.0采用鸿蒙和Android 10双架构，游戏性能比EMUI11表现好...-程序员宅基地
文章浏览阅读5.5k次。鸿蒙OS 2.0采用鸿蒙和Android 10双架构，来支持兼容安卓APP看到报道的这个成绩，鸿蒙系统下比EMUI11系统表现更加优秀，这一点就成功了，接下来当真正完全使用鸿蒙内核之后应该有很好的表现吧！但是网友似乎并不买单，怎么回事！反正不推出鸿蒙专用app，就是让我们认为是安卓换皮，任你如何解释也没用，第三方没有研发鸿蒙app，至少华为自己要推出几款鸿蒙系统专用的APP供人家下载吧。不然恐怕换..._鸿蒙2与安卓10哪个操作系统好用?
MySQL 用户权限和远程访问设置_mysql远程访问权限-程序员宅基地
文章浏览阅读9.2k次。MySQL 用户权限和远程访问设置_mysql远程访问权限
c#中计算三角形面积公式_三角形面积公式！你到底知道几个？-程序员宅基地
文章浏览阅读573次。微信公众号“中学数学教与学”教师群公告微信QQ教师群入群方式及介绍高中数学教与学★教师QQ群【324623715】初中数学教与学★教师QQ群【460287009】中学数学教与学★学生QQ群【837494287】你知道几个呢？三角形面积公式！第一种已知三角形的底边长为,高为,则三角形面积：第二种已知三角形的周长为,内切圆半径为,则三角形面积：第三种已知三角形的三边长的乘积为,外接圆半径为,..._c#直角三角形面积公式
基于Python爬虫山东青岛二手房数据可视化系统设计与实现(Django框架) 研究背景与意义、国内外研究现状-程序员宅基地
文章浏览阅读1.2k次，点赞24次，收藏16次。基于Python爬虫山东青岛二手房数据可视化系统设计与实现(Django框架) 研究背景与意义、国内外研究现状。通过采集、整理和分析二手房市场的数据，可以为购房者提供更全面、准确的市场信息，有助于优化购房决策，提高购房效率和准确性。二手房市场的区域差异研究 由于不同地区的经济发展水平、人口密度、交通条件等方面的差异，二手房市场在不同地区也存在一定的差异。二手房市场的价格预测研究 许多学者和研究人员通过统计分析、机器学习等方法，对二手房市场的价格走势进行研究和预测。
numba.jit警告：failed type inference due to: non-precise type pyobject-程序员宅基地
文章浏览阅读2.9k次。from numba import jit代码报错：failed type inference due to: non-precise type pyobject解决方法：把jit函数挪到类的外面去用。_non-precise type pyobject
随便推点
Libevent book 笔记(11) Connection listeners accepting TCP connections_.net启动 the connection listener failed to accept an-程序员宅基地
文章浏览阅读296次。文章目录Creating or freeing an evconnlistenerevconnlistener_newevconnlistener_new_bindevconnlistener_freeRecognized flagsThe connection listener callbackEnabling and disabling an evconnlistenerevconnlistener_disableevconnlistener_enableAdjusting an evconnliste_.net启动 the connection listener failed to accept any new connections
开源的 Sora 复现方案，成本降低近一半！-程序员宅基地
文章浏览阅读723次，点赞19次，收藏14次。近日，开发 ChatGPT 的 OpenAI 公司又放出王炸 Sora，一个可以根据文本生成视频的 AI 模型。上图就是 OpenAI 公布的 Sora 生成的视频片段，可以毫不夸张地说 Sora 直接将视频生成技术推向了新的高度，这也标志着人工智能视频生成技术迈入了新的时代。此项技术，可以广泛应用于电影、动画、游戏、广告等领域，为内容创作者提供更加便捷、高效的创作工具。虽然 Sora 没有开源，..._sora开源了吗
android8.1上新增camera设备_android 8.1 camera-程序员宅基地
文章浏览阅读1.3k次。在工作中，camera这一块上，可能会有各种各样的需求。比如有人想新增一个虚拟摄像头，当用户app打开摄像头设备时，打开的不是系统默认的camera hal代码，而是自己指定的代码，用自己事先准备好的视频数据，来喂给app；也有人想在系统默认的一套app框架上，新增一个外接的usbcamera，并且要能溶入到camera框架中。app只需要指定usbcamera的id，就能像打开普通摄像头那样，去打开我们的usbcamera；也有人，想在现有的框架上，同时兼容老的hal1+api1流程的androi..._android 8.1 camera
利用AD13设计PCB的问题总结1-10_ad13选择器件-程序员宅基地
文章浏览阅读1.2k次。利用AD13设计PCB问题总结1，PCB布线，不能有90度角，必须是45度或180度。2，根据项目的架构和功能，选择元器件的封装类型和电气特性。在画原理图的时候，必须要确定每个元器件的“封装类型”和“引脚标号”。_ad13选择器件
Win10+RTX3060配置CUDA等深度学习环境_wind10 cuda536 +3060-程序员宅基地
文章浏览阅读4.4w次，点赞47次，收藏390次。这里写目录标题1、下载准备2、下载安装Anaconda3、下载安装CUDA和CUDNN3.1 cuda和cudnn下载3.2 cuda和cudnn安装4、安装GPU版pytorch与TensorFlow4.1 下载4.2 安装1、下载准备 相关的安装包比如Anaconda、CUDA、CUDNN、Pytorch、TensorFlow等都可以在https://blog.csdn.net/weixin_43760844/article/details/113474_wind10 cuda536 +3060
分享多线程、线程池、hystrix_hystrix默认线程池是业务线程吗-程序员宅基地
文章浏览阅读588次。多线程的圣经：1、线程。1.1、我们的程序跑在哪个线程里？是怎样执行请求的？在不考虑自己写线程池的前提下。假如就是一句最普通的xxModel.setName(“xx");到底是运行在哪里的？我们找调用它的一条链，我相信总有一次调用，是你找不到的了。可能是controller，可能是dubbo，总而言之是别的框架，调进来的。这就是我总说的四大入口，controller，dubbo-server，mq-consumer和job。注意：这里正好能显现出来，dubbo-server是等着别人来调，du_hystrix默认线程池是业务线程吗