【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;
}
}
智能推荐
bat 切换网络适配器_支持多网卡，多模式，多系统的IP切换的批处理-程序员宅基地
文章浏览阅读714次。@echo off&setlocal enabledelayedexpansiontitle make by zcHacker QQ: 36868508color 1fmode con: cols=78 lines=30for /f "tokens=* delims= " %%f in ('ver') do echo 本机系统为:%%fecho 系统内核为:%os%echo.echo.☆请..._batq切换网卡
odoo上传文件附件_odoo form发送附件-程序员宅基地
文章浏览阅读3.4k次。在应用中搜索‘Attachments List and Document Indexation’，安装后在form视图中就出现了附件按钮_odoo form发送附件
MATLAB r2021b环境下的基于非下采样小波包分析的轴承故障诊断-程序员宅基地
文章浏览阅读235次，点赞5次，收藏3次。代码运行环境为MATLAB r2021b，非下采样小波包变换执行信号的等带宽精细滤波，而不是离散小波变换中的较粗糙的倍频程滤，而且很好的缓解了小波包变换中的时间分辨率损失，这使得非下采样小波包在许多应用中比小波包或离散小波变换表现的更好。从结果中可以看出，NSWT在保留信号细节的同时，具有更好的频率分辨率，能够更清晰地显示信号的频谱特性。以150 和 200 Hz 的两个间歇正弦波为例，看一下非下采样小波包的时频谱图和离散小波变换的时频谱图，效果显而易见。哥廷根数学学派2023。
IDEA 报Error java:找不到符号 符号: 变量 log 位置_java: 找不到符号 符号: 变量 log-程序员宅基地
文章浏览阅读5.1k次，点赞8次，收藏2次。在网上看了很多种解决办法，如下：在pom文件中添加lombok的依赖。在IDEA中安装lombok的插件：在IDEA中点击 File -> Settings -> Plugins，输入Lombok，选择Lombok的Installed进行安装。在IDEA中勾选Enable Annotation Processors：File -> Settings -> Build, Execution, Deployment -> Compiler -> Annotation._java: 找不到符号 符号: 变量 log
世界围棋人机大战、顶峰对决第二战：围棋世界冠军Lee Sedol（李世石，围棋职业九段）对战Google DeepMind AlphaGo围棋程序，AlphaGo再次胜出！...-程序员宅基地
文章浏览阅读189次。感觉在哔哩哔哩（bilibili）上看比赛直播比较好，一直可以看到比赛的直播画面，还能听到英文解说和中文主持人的解说。YouTube上是不错，但是一方面爬梯子比较卡，另一方面只能听到英文解说。韩国著名围棋九段棋手李世石与谷歌人工智能“阿尔法围棋”(AlphaGo)的5盘对决，将于3月9日、10日、12日、13日和15日在首尔举行。比赛将采用贴7.5目的中国规则（比赛结束时，先走棋的棋手贴..._围棋游戏九段
MQTT协议简介及消息总线EMQX与客户端Paho快速上手_paho mqtt-程序员宅基地
文章浏览阅读5k次。1. MQTT简介MQTT（Message Queuing Telemetry Transport，消息队列遥测传输协议），是基于“订阅/发布”模式的轻量级通信协议，该协议基于TCP/IP，能以极低的带宽为海量（百万级）跨域设备提供可靠的消息服务，因此在物联网、小型移动终端、边缘计算方面有广泛应用。所谓可靠的消息传输，体现为可配置消息的服务质量（QoS），有三种服务质量可选：至多一次：消息发布完全依赖底层TCP/IP网络。会发生消息丢失或重复。应用场景如环境传感器的数据采集，丢失一次记录无所谓，因_paho mqtt
随便推点
python数据分析与可视化-程序员宅基地
文章浏览阅读2.1k次，点赞22次，收藏69次。Python数据分析主要包括数据清洗、数据探索和数据可视化三个部分。数据清洗是数据分析的重要环节，主要是对数据进行预处理，包括缺失值处理、异常值处理、数据类型转换等。数据探索则是通过对数据进行初步分析，了解数据的分布和特征，为后续的数据分析提供基础。数据可视化则是将数据以图形化的方式呈现，帮助人们更好地理解和分析数据。_python数据分析与可视化
Linux操作系统实验：生产者和消费者问题_编写经典的“生产者-消费者”问题的实验,进一步熟悉linux中的多线程编程,并且掌握-程序员宅基地
文章浏览阅读2.8k次，点赞3次，收藏43次。“生产者消费者”问题是一个著名的同时性编程问题的集合。通过编写经典的“生产者消费者”问题的实验，读者可以进一步熟悉 Linux 中多线程编程，并且掌握用信号量处理线程间的同步互斥问题。_编写经典的“生产者-消费者”问题的实验,进一步熟悉linux中的多线程编程,并且掌握
Java并发编程实战之互斥锁_java互斥锁也有必要学吗-程序员宅基地
文章浏览阅读2k次，点赞3次，收藏15次。一谈到互斥，我们很自然就会想到了锁。首先我们把一段需要互斥执行的代码称为临界区。线程在进入临界区之前，首先尝试加锁 `lock()`，如果成功，则进入临界区，此时我们称这个线程持有锁；否则呢就等待，直到持有锁的线程解锁；持有锁的线程执行完临界区的代码后，执行解锁 `unlock()`。_java互斥锁也有必要学吗
【2023地理设计组一等奖】多模态地理空间数据支持下的城市洪涝灾害韧性评价_韧性基线模型(bric)中的韧性维度的是()。-程序员宅基地
文章浏览阅读125次。表5计算了各因子的权重系数，根据结果，我们可以看出，兴趣点密度和人口密度是洪灾恢复过程中最显著的影响因子，权重系数普遍高于0.125，同样GDP因子作为影响城市发展的极其重要的因子，在洪灾恢复方面上也具有较高的影响力。通常情况下，洪灾恢复率（FRR）的计算是基于洪水灾害造成的损失值和洪水后恢复的指标值。（2）在洪水信息提取方面，本作品采用了U-Net语义分割网络，通过训练大量样本，学习Sentinel-1遥感影像中的洪水特征，从而能够实现高效与高精度的识别与提取，为后续的研究与分析提供可靠的数据基础。_韧性基线模型(bric)中的韧性维度的是()。
数论——无关(relationship)（容斥原理）_设 k 是正整数,集合 a 至少有两个元素,且 acn *.如果对于 a 中的任意两个不同-程序员宅基地
文章浏览阅读234次。题目链接数论——无关(relationship)（容斥原理）题目描述若一个集合 A 内所有的元素都不是正整数 N 的因数，则称 N 与集合 A 无关。给出一个含有 k 个元素的集合 A = {a1,a2,a3,…,ak}，求区间 [L,R] 内与 A 无关的正整数的个数。保证 A 内的元素都是素数。输入描述输入数据共两行：第一行三个正整数 L,R,k，意义如“题目描述”。第二行k个正整数，描述集合 A，保证 k 个正整数两两不相同。输出描述输出数据共一行：第一行一个正整数表示区间 [_设 k 是正整数,集合 a 至少有两个元素,且 acn *.如果对于 a 中的任意两个不同
Go 语言通过 SSH 远程登录服务器执行命令和传输文件_go sshclient.newsession-程序员宅基地
文章浏览阅读792次。Go 语言通过 SSH 远程登录服务器执行命令和传输文件_go sshclient.newsession