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

数据结构 ——— 单链表oj题:链表分割(带哨兵位单向不循环链表实现)

目录

题目要求

手搓简易单链表

代码实现 


题目要求

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

举例说明:

输入:x = 5 ; [1,3,9,6,5,4,7,2]

输出:[1,3,4,2,9,6,5,7]


手搓简易单链表

代码演示:

struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n1);
struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n2);
struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n3);
struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n4);
struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n5);
struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n6);
struct ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n7);
struct ListNode* n8 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n8);n1->val = 1;
n2->val = 3;
n3->val = 9;
n4->val = 6;
n5->val = 5;
n6->val = 4;
n7->val = 7;
n8->val = 2;n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = n6;
n6->next = n7;
n7->next = n8;
n8->next = NULL;

代码实现

代码演示:

struct ListNode* partition(struct ListNode* head, int x)
{// 小于 x 的头尾节点struct ListNode* lesshead;struct ListNode* lesstail;// 大于等于 x 的头尾节点struct ListNode* greaterhead;struct ListNode* greatertail;// 定义哨兵位lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = head;while (cur != NULL){if (cur->val < x){lesstail->next = cur;lesstail = lesstail->next;}else{greatertail->next = cur;greatertail = greatertail->next;}cur = cur->next;}// 链接两个链表lesstail->next = greaterhead->next;greatertail->next = NULL;head = lesshead->next;free(lesshead);free(greaterhead);return head;
}

代码解析:

代码思路:创建两个带哨兵位的单链表,一个用来链接小于 x 的节点,一个用来链接大于等于 x 的节点,最后再把两个链表进行链接,这样就完成了链表的分割,并且没有改变原来的数据顺序

代码逻辑:lesshead 和 lesstail 用来管控小于 x 的节点,lesshead 是哨兵位,不存储有效数据,lesstail 向后链接小于 x 的节点,greaterhead 和 greatertail 作用同上,是用来链接大于等于 x 的节点,进行分割后,不要忘记将 greatertail 的 next 置空,因为分割后 greatertail 节点不一定是为节点,最后再将 lesshead 哨兵位的 next 赋值给 head ,再释放,即可

代码验证:

算法的时间和空间复杂度:

while 循环执行了 N 次,每次内部常数次,只 malloc 开辟了两个节点,可忽略不计

算法的时间复杂度:O(N)

算法的空间复杂度:O(1)

相关文章:

数据结构 ——— 单链表oj题:链表分割(带哨兵位单向不循环链表实现)

目录 题目要求 手搓简易单链表 代码实现 题目要求 现有一链表的头指针 ListNode* head &#xff0c;给一定值 x &#xff0c;编写一段代码将所有小于 x 的节点排在其余节点之前&#xff0c;且不能改变原来的数据顺序&#xff0c;返回重新排列后的链表的头节点 举例说明&a…...

华为 HCIP-Datacom H12-821 题库 (32)

&#x1f423;博客最下方微信公众号回复题库,领取题库和教学资源 &#x1f424;诚挚欢迎IT交流有兴趣的公众号回复交流群 &#x1f998;公众号会持续更新网络小知识&#x1f63c; 1.当一个运行 MSTP 协议的交换设备端口收到一个配置BPDU 时&#xff0c;会与设备保存的全局配…...

[C++][第三方库][brpc]详细讲解

目录 1.介绍2.安装3.类与接口介绍1.日志输出类与接口2.ProtoBuf类与接口3.服务端类与接口4.客户端类与接口 4.使用0.一般流程1.Server2.客户端 -- 同步调用3.客户端 -- 异步调用 1.介绍 brpc是用C编写的工业级RPC框架&#xff0c;常用于搜索、存储、机器学习、广告、推荐等高性…...

Python-Learning

补充不熟悉的python知识 1 **是表示平方 注释是用来阐述代码要做什么&#xff0c;以及是如何做的 先编写行之有效的代码&#xff0c;再决定是对其做进一步改进&#xff0c;还是转而去编写新代码 列表常用是append&#xff0c;但也有pop&#xff0c;这个pop是输出一个值&…...

如何让 Android 的前端页面像 iOS 一样“优雅”?

作者:方英杰&#xff08;崇之&#xff09; 最近在调研前端页面适配 Android 端异形屏的方案&#xff0c;调研过程中发现了一些比较有意思的点&#xff0c;本文主要是做一个总结。 一、提出问题 首先&#xff0c;我们需要知道 Android 上的前端适配面临着什么问题。 问题其实很…...

10.3学习

1.循环依赖 循环依赖其实就是循环引用&#xff0c;也就是两个或者两个以上的 Bean 互相持有对方&#xff0c;最终形成闭环。比如A 依赖于B&#xff0c;B又依赖于A Spring中循环依赖场景有: prototype 原型 bean循环依赖 构造器的循环依赖&#xff08;构造器注入&#xff09;…...

Shell文本处理(三)

Shell文本处理三:字符串处理 1、字符串截取(切片)2、字符串替换3、字符串删除4、去除空格5、大小写转换6、字符串分割7、去除中文在Shell中,字符串没有单独的数据类型,一切都是变量。但这并不意味着我们不能像在Java、Python等其他编程语言中那样处理字符串 1、字符串截取…...

5个python多线程简单示例

示例 1: 基本线程创建 # 示例 1: 基本线程创建 import threading import timedef print_numbers():for i in range(5):time.sleep(1)print(i)# 创建线程 thread threading.Thread(targetprint_numbers)# 启动线程 thread.start()# 等待线程完成&#xff08;可选&#xff09; …...

Streamlit:用Python快速构建交互式Web应用

在传统的Web开发中&#xff0c;开发者常常需要编写大量的前端和后端代码&#xff0c;才能实现一个简单的交互式Web应用。Streamlit 通过简化这一过程&#xff0c;使得你只需要用Python编写代码&#xff0c;就能快速创建具有丰富交互功能的Web应用。本文将介绍如何使用Streamlit…...

深入浅出Vue.js组件开发:从基础到高级技巧

解锁Python编程的无限可能:《奇妙的Python》带你漫游代码世界 Vue.js 是一个轻量级且功能强大的 JavaScript 框架,专注于构建用户界面。它的核心优势之一是组件系统,它允许开发者通过模块化、可复用的方式构建复杂的应用程序。在这篇文章中,我们将详细探讨如何开发 Vue.js…...

Python并发编程挑战与解决方案

Python并发编程挑战与解决方案 并发编程是现代软件开发中的一项核心能力&#xff0c;它允许多个任务同时运行&#xff0c;提高程序的性能和响应速度。Python因其易用性和灵活性而广受欢迎&#xff0c;但其全局解释器锁&#xff08;GIL&#xff09;以及其他特性给并发编程带来了…...

LeetCode从入门到超凡(五)深入浅出---位运算

引言 大家好&#xff0c;我是GISer Liu&#x1f601;&#xff0c;一名热爱AI技术的GIS开发者。本系列文章是我跟随DataWhale 2024年9月学习赛的LeetCode学习总结文档&#xff1b;本文主要讲解 位运算算法。&#x1f495;&#x1f495;&#x1f60a; 一、 位运算简介 1.什么是位…...

一些 Go Web 开发笔记

原文&#xff1a;Julia Evans - 2024.09.27 在过去的几周里&#xff0c;我花了很多时间在用 Go 开发一个网站&#xff0c;虽然不知道它最终会不会发布&#xff0c;但在这个过程中我学到了一些东西&#xff0c;想记录下来。以下是我的一些收获&#xff1a; Go 1.22 现在有了更…...

[Go语言快速上手]初识Go语言

目录 一、什么是Go语言 二、第一段Go程序 1、Go语言结构 注意 2、Go基础语法 关键字 运算符优先级 三、Go语言数据类型 示例 小结 一、什么是Go语言 Go语言&#xff0c;通常被称为Golang&#xff0c;是一种静态类型、编译型的计算机编程语言。它由Google的Robert Gr…...

基于STM32的智能风扇控制系统设计

引言 本项目将基于STM32微控制器设计一个智能风扇控制系统&#xff0c;通过温度传感器实时检测环境温度&#xff0c;并根据预设的温度范围自动调节风扇的转速。该系统展示了STM32的PWM输出、传感器接口以及自动控制应用的实现。 环境准备 1. 硬件设备 STM32F103C8T6 开发板…...

OpenCV 形态学相关函数详解及用法示例

OpenCV形态学相关的运算包含腐蚀(MORPH_ERODE)&#xff0c;膨胀(MORPH_DILATE)&#xff0c;开运算(MORPH_OPEN)&#xff0c;闭运算(MORPH_CLOSE)&#xff0c;梯度运算(MORPH_GRADIENT)&#xff0c;顶帽运算(MORPH_TOPHAT)&#xff0c;黑帽运算(MORPH_BLACKHAT)&#xff0c;击中…...

Kafka学习笔记(三)Kafka分区和副本机制、自定义分区、消费者指定分区

文章目录 前言7 分区和副本机制7.1 生产者分区写入策略7.1.1 轮询分区策略7.1.2 随机分区策略7.1.3 按key分区分配策略7.1.4 自定义分区策略7.1.4.1 实现Partitioner接口7.1.4.2 实现分区逻辑7.1.4.3 配置使用自定义分区器7.1.4.4 分区测试 7.2 消费者分区分配策略7.2.1 RangeA…...

华为 HCIP-Datacom H12-821 题库 (31)

&#x1f423;博客最下方微信公众号回复题库,领取题库和教学资源 &#x1f424;诚挚欢迎IT交流有兴趣的公众号回复交流群 &#x1f998;公众号会持续更新网络小知识&#x1f63c; 1. 默认情况下&#xff0c;IS-IS Level-1-2 路由器会将 Level-2 区域的明细路由信息发布到Lev…...

占位,凑满减

占位&#xff0c;凑满减...

SpringBoot校园资料平台:从零到一的构建过程

1系统概述 1.1 研究背景 如今互联网高速发展&#xff0c;网络遍布全球&#xff0c;通过互联网发布的消息能快而方便的传播到世界每个角落&#xff0c;并且互联网上能传播的信息也很广&#xff0c;比如文字、图片、声音、视频等。从而&#xff0c;这种种好处使得互联网成了信息传…...

SMUDebugTool终极指南:快速掌握AMD Ryzen系统调试与优化技巧

SMUDebugTool终极指南&#xff1a;快速掌握AMD Ryzen系统调试与优化技巧 【免费下载链接】SMUDebugTool A dedicated tool to help write/read various parameters of Ryzen-based systems, such as manual overclock, SMU, PCI, CPUID, MSR and Power Table. 项目地址: http…...

RPCS3完全攻略:从零开始打造你的PC端PS3游戏中心

RPCS3完全攻略&#xff1a;从零开始打造你的PC端PS3游戏中心 【免费下载链接】rpcs3 PS3 emulator/debugger 项目地址: https://gitcode.com/GitHub_Trending/rp/rpcs3 还在为无法重温经典PS3游戏而烦恼吗&#xff1f;想要在电脑上体验《最后生还者》、《神秘海域》等索…...

10.JVM-垃圾回收器

Serial 与 Serial Old核心特征&#xff1a;单线程、Stop The World (STW)。工作机制&#xff1a;它们在进行垃圾回收时&#xff0c;必须暂停所有其他的工作线程&#xff0c;直到它收集结束。Serial&#xff1a;新生代&#xff0c;采用标记-复制算法。Serial Old&#xff1a;老年…...

告别手动拖拽!用.men和.tbr文件在UG NX里一键创建专属菜单栏(附完整脚本模板)

告别手动拖拽&#xff01;用.men和.tbr文件在UG NX里一键创建专属菜单栏&#xff08;附完整脚本模板&#xff09; 在UG NX的二次开发中&#xff0c;手动拖拽按钮和菜单不仅效率低下&#xff0c;还容易出错。想象一下&#xff0c;每次部署新功能都要重复点击几十次鼠标&#xff…...

零基础快速入门前端DOM 节点操作核心知识点及蓝桥杯 Web 应用开发考点解析(可用于备赛蓝桥杯Web应用开发)

DOM&#xff08;文档对象模型&#xff09;是 JavaScript 操作网页内容的核心接口&#xff0c;而节点操作则是 DOM 编程的基础&#xff0c;是蓝桥杯 Web 应用开发赛道的必考核心考点&#xff0c;无论是动态交互效果、数据渲染还是功能实现&#xff0c;都离不开节点的获取、增删、…...

EcomGPT-7B多语言能力:俄语商品→自动适配Wildberries平台标题规则

EcomGPT-7B多语言能力&#xff1a;俄语商品→自动适配Wildberries平台标题规则 1. 引言&#xff1a;跨境电商的本地化难题 如果你正在做俄罗斯电商&#xff0c;或者想把商品卖到Wildberries平台&#xff0c;一定遇到过这个头疼的问题&#xff1a;怎么把中文的商品信息&#x…...

告别黑盒操作:详解mmc_utils在Android设备上的20+个实用命令(从extcsd读到RPMB写)

eMMC深度操作指南&#xff1a;解锁mmc-utils的20个高阶应用场景 当你的Android设备出现存储性能下降、分区异常或安全验证需求时&#xff0c;系统自带的工具往往束手无策。此时&#xff0c;一个被低估的神器mmc-utils正躺在Linux内核源码树中等待被唤醒——它不仅能够读取eMMC芯…...

终极zsh语法高亮插件版本兼容性测试:Zsh 5.0到5.9全面支持指南

终极zsh语法高亮插件版本兼容性测试&#xff1a;Zsh 5.0到5.9全面支持指南 【免费下载链接】zsh-syntax-highlighting Fish shell like syntax highlighting for Zsh. 项目地址: https://gitcode.com/gh_mirrors/zs/zsh-syntax-highlighting zsh-syntax-highlighting是Z…...

3倍效率提升的B站视频下载工具:DownKyi如何重构资源获取体验

3倍效率提升的B站视频下载工具&#xff1a;DownKyi如何重构资源获取体验 【免费下载链接】downkyi 哔哩下载姬downkyi&#xff0c;哔哩哔哩网站视频下载工具&#xff0c;支持批量下载&#xff0c;支持8K、HDR、杜比视界&#xff0c;提供工具箱&#xff08;音视频提取、去水印等…...

SNOMED CT入门指南:从概念、关系到数据文件,手把手带你理解这个医学术语标准

SNOMED CT技术解析&#xff1a;从数据结构到医疗信息系统的实战指南 在医疗信息化领域&#xff0c;数据标准化是打破信息孤岛的关键。当不同医院的电子病历系统使用各自独立的术语体系时&#xff0c;跨机构的数据交换就像一场没有翻译的多国会议——充满误解和低效。这正是SNOM…...