当前位置: 首页 > 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;这种种好处使得互联网成了信息传…...

GTE-Pro行业落地:制造业设备维修手册语义检索替代传统目录树导航

GTE-Pro行业落地&#xff1a;制造业设备维修手册语义检索替代传统目录树导航 1. 引言&#xff1a;当维修师傅找不到说明书时 想象一下这个场景&#xff1a;工厂里一台关键设备突然报警停机&#xff0c;维修师傅小王满头大汗地站在机器旁。他记得这台设备的维修手册有上千页&a…...

给STM32密码锁加个“记忆”:手把手教你用CubeMX配置I2C读写EEPROM(AT24C02)

为STM32密码锁赋予持久记忆&#xff1a;CubeMX驱动AT24C02 EEPROM全攻略 当你的密码锁在断电后依然能记住最后一次设置的密码&#xff0c;这种"记忆"能力往往能大幅提升用户体验。本文将带你深入探索如何通过I2C总线连接AT24C02 EEPROM芯片&#xff0c;为基于STM32F1…...

不止是上网:用PVE虚拟的OpenWRT旁路由解锁Docker、AdGuard Home和异地组网玩法

解锁PVE虚拟OpenWRT旁路由的进阶玩法&#xff1a;从Docker到智能家居中枢 在家庭网络架构中&#xff0c;OpenWRT旁路由早已超越了简单的网关转发角色。当它运行在PVE虚拟化环境中时&#xff0c;这个轻量级Linux系统&#xff08;仅需1G内存&#xff09;可以变身为多功能家庭网络…...

HAL库定时器双杀技:STM32F401CCU6同时实现PWM输出+输入捕获的避坑指南

HAL库定时器双杀技&#xff1a;STM32F401CCU6同时实现PWM输出输入捕获的避坑指南 在嵌入式开发中&#xff0c;定时器是最基础也最强大的外设之一。对于STM32F4系列微控制器&#xff0c;HAL库提供了丰富的定时器功能&#xff0c;但如何在同一芯片上同时实现PWM输出和输入捕获&am…...

如何高效下载B站视频:BilibiliDown终极指南与完整教程

如何高效下载B站视频&#xff1a;BilibiliDown终极指南与完整教程 【免费下载链接】BilibiliDown (GUI-多平台支持) B站 哔哩哔哩 视频下载器。支持稍后再看、收藏夹、UP主视频批量下载|Bilibili Video Downloader &#x1f633; 项目地址: https://gitcode.com/gh_mirrors/b…...

[特殊字符] Local Moondream2图文对话教程:详细步骤实现自定义问题提问

Local Moondream2图文对话教程&#xff1a;详细步骤实现自定义问题提问 1. 引言&#xff1a;让电脑拥有"眼睛"的智能工具 你是否曾经希望电脑能像人一样看懂图片&#xff0c;并且回答关于图片内容的问题&#xff1f;Local Moondream2就是这样一款神奇的工具&#x…...

EcomGPT中英文7B模型部署案例:跨境电商运营者如何用一行bash启动AI助手

EcomGPT中英文7B模型部署案例&#xff1a;跨境电商运营者如何用一行bash启动AI助手 1. 项目概述 EcomGPT电商领域智能助手是基于阿里EcomGPT-7B-Multilingual多语言电商大模型开发的Web应用。这个工具专门为电商从业者设计&#xff0c;通过直观的网页界面提供商品分类、属性提…...

Granite TimeSeries FlowState R1实战:基于卷积神经网络(CNN)的时序特征提取进阶

Granite TimeSeries FlowState R1实战&#xff1a;基于卷积神经网络&#xff08;CNN&#xff09;的时序特征提取进阶 你是不是也遇到过这样的问题&#xff1f;面对一长串传感器读数、股票价格波动或者服务器监控数据&#xff0c;感觉信息量巨大&#xff0c;却不知道从哪里入手…...

终极视频硬字幕提取指南:本地OCR识别87种语言的完整解决方案

终极视频硬字幕提取指南&#xff1a;本地OCR识别87种语言的完整解决方案 【免费下载链接】video-subtitle-extractor 视频硬字幕提取&#xff0c;生成srt文件。无需申请第三方API&#xff0c;本地实现文本识别。基于深度学习的视频字幕提取框架&#xff0c;包含字幕区域检测、字…...

Pixel Dream Workshop 助力前端开发:Vue.js 项目动态视觉素材生成指南

Pixel Dream Workshop 助力前端开发&#xff1a;Vue.js 项目动态视觉素材生成指南 1. 为什么前端开发者需要关注视觉素材生成 作为一名Vue.js开发者&#xff0c;你可能经常遇到这样的困扰&#xff1a;产品经理突然要求给新功能加个炫酷的Banner图&#xff0c;设计师资源紧张排…...