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

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...