数据结构 ——— 单链表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 ,给一定值 x ,编写一段代码将所有小于 x 的节点排在其余节点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头节点 举例说明&a…...
华为 HCIP-Datacom H12-821 题库 (32)
🐣博客最下方微信公众号回复题库,领取题库和教学资源 🐤诚挚欢迎IT交流有兴趣的公众号回复交流群 🦘公众号会持续更新网络小知识😼 1.当一个运行 MSTP 协议的交换设备端口收到一个配置BPDU 时,会与设备保存的全局配…...
[C++][第三方库][brpc]详细讲解
目录 1.介绍2.安装3.类与接口介绍1.日志输出类与接口2.ProtoBuf类与接口3.服务端类与接口4.客户端类与接口 4.使用0.一般流程1.Server2.客户端 -- 同步调用3.客户端 -- 异步调用 1.介绍 brpc是用C编写的工业级RPC框架,常用于搜索、存储、机器学习、广告、推荐等高性…...
Python-Learning
补充不熟悉的python知识 1 **是表示平方 注释是用来阐述代码要做什么,以及是如何做的 先编写行之有效的代码,再决定是对其做进一步改进,还是转而去编写新代码 列表常用是append,但也有pop,这个pop是输出一个值&…...
如何让 Android 的前端页面像 iOS 一样“优雅”?
作者:方英杰(崇之) 最近在调研前端页面适配 Android 端异形屏的方案,调研过程中发现了一些比较有意思的点,本文主要是做一个总结。 一、提出问题 首先,我们需要知道 Android 上的前端适配面临着什么问题。 问题其实很…...
10.3学习
1.循环依赖 循环依赖其实就是循环引用,也就是两个或者两个以上的 Bean 互相持有对方,最终形成闭环。比如A 依赖于B,B又依赖于A Spring中循环依赖场景有: prototype 原型 bean循环依赖 构造器的循环依赖(构造器注入)…...
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()# 等待线程完成(可选) …...
Streamlit:用Python快速构建交互式Web应用
在传统的Web开发中,开发者常常需要编写大量的前端和后端代码,才能实现一个简单的交互式Web应用。Streamlit 通过简化这一过程,使得你只需要用Python编写代码,就能快速创建具有丰富交互功能的Web应用。本文将介绍如何使用Streamlit…...
深入浅出Vue.js组件开发:从基础到高级技巧
解锁Python编程的无限可能:《奇妙的Python》带你漫游代码世界 Vue.js 是一个轻量级且功能强大的 JavaScript 框架,专注于构建用户界面。它的核心优势之一是组件系统,它允许开发者通过模块化、可复用的方式构建复杂的应用程序。在这篇文章中,我们将详细探讨如何开发 Vue.js…...
Python并发编程挑战与解决方案
Python并发编程挑战与解决方案 并发编程是现代软件开发中的一项核心能力,它允许多个任务同时运行,提高程序的性能和响应速度。Python因其易用性和灵活性而广受欢迎,但其全局解释器锁(GIL)以及其他特性给并发编程带来了…...
LeetCode从入门到超凡(五)深入浅出---位运算
引言 大家好,我是GISer Liu😁,一名热爱AI技术的GIS开发者。本系列文章是我跟随DataWhale 2024年9月学习赛的LeetCode学习总结文档;本文主要讲解 位运算算法。💕💕😊 一、 位运算简介 1.什么是位…...
一些 Go Web 开发笔记
原文:Julia Evans - 2024.09.27 在过去的几周里,我花了很多时间在用 Go 开发一个网站,虽然不知道它最终会不会发布,但在这个过程中我学到了一些东西,想记录下来。以下是我的一些收获: Go 1.22 现在有了更…...
[Go语言快速上手]初识Go语言
目录 一、什么是Go语言 二、第一段Go程序 1、Go语言结构 注意 2、Go基础语法 关键字 运算符优先级 三、Go语言数据类型 示例 小结 一、什么是Go语言 Go语言,通常被称为Golang,是一种静态类型、编译型的计算机编程语言。它由Google的Robert Gr…...
基于STM32的智能风扇控制系统设计
引言 本项目将基于STM32微控制器设计一个智能风扇控制系统,通过温度传感器实时检测环境温度,并根据预设的温度范围自动调节风扇的转速。该系统展示了STM32的PWM输出、传感器接口以及自动控制应用的实现。 环境准备 1. 硬件设备 STM32F103C8T6 开发板…...
OpenCV 形态学相关函数详解及用法示例
OpenCV形态学相关的运算包含腐蚀(MORPH_ERODE),膨胀(MORPH_DILATE),开运算(MORPH_OPEN),闭运算(MORPH_CLOSE),梯度运算(MORPH_GRADIENT),顶帽运算(MORPH_TOPHAT),黑帽运算(MORPH_BLACKHAT),击中…...
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)
🐣博客最下方微信公众号回复题库,领取题库和教学资源 🐤诚挚欢迎IT交流有兴趣的公众号回复交流群 🦘公众号会持续更新网络小知识😼 1. 默认情况下,IS-IS Level-1-2 路由器会将 Level-2 区域的明细路由信息发布到Lev…...
占位,凑满减
占位,凑满减...
SpringBoot校园资料平台:从零到一的构建过程
1系统概述 1.1 研究背景 如今互联网高速发展,网络遍布全球,通过互联网发布的消息能快而方便的传播到世界每个角落,并且互联网上能传播的信息也很广,比如文字、图片、声音、视频等。从而,这种种好处使得互联网成了信息传…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist
现象: android studio报错: [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决: 不要动CMakeLists.…...
Web后端基础(基础知识)
BS架构:Browser/Server,浏览器/服务器架构模式。客户端只需要浏览器,应用程序的逻辑和数据都存储在服务端。 优点:维护方便缺点:体验一般 CS架构:Client/Server,客户端/服务器架构模式。需要单独…...
给网站添加live2d看板娘
给网站添加live2d看板娘 参考文献: stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下,文章也主…...
