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

【数据结构】单链表OJ题

在这里插入图片描述

前言:
本节博客将讲解单链表的反转,合并有序链表,寻找中间节点及约瑟夫问题

文章目录

  • 一、反转链表
  • 二、合并有序链表
  • 三、链表的中间结点
  • 四、环形链表的约瑟夫问题

一、反转链表

在这里插入图片描述

要反转链表,我们需要遍历链表并改变每个节点的 next 指针,使其指向其前一个节点。为了完成这个任务,我们需要三个指针:prev、cur和 next_node。

  • prev:保存当前节点的前一个节点。初始化为 NULL,因为链表的新头部(原始链表的尾部)的 next 指针将指向 NULL。
  • cur:表示当前正在处理的节点。
  • next_node:保存当前节点的下一个节点。
    在这里插入图片描述
struct ListNode* reverseList(struct ListNode* head) {typedef struct ListNode ListNode;ListNode* prev = NULL;ListNode* cur = head;ListNode* next_node = NULL;while (cur != NULL) {next_node = cur->next;  // 保存当前节点的下一个节点cur->next = prev;       // 更新当前节点的next指针prev = cur;             // 将prev移动到当前节点cur = next_node;        // 移动到下一个节点}return prev;  // 返回新的头部
}

二、合并有序链表

在这里插入图片描述
分为四个步骤:

  • 开始阶段: 首先,函数检查两个列表是否为空。如果其中一个为空,则直接返回另一个列表,因为没有合并的必要。
  • 初始化合并链表的头: 函数接着检查list1和list2的首个节点,看哪一个的值较小。较小的那个节点将成为新的合并链表的首个节点。
  • 合并过程: 使用一个while循环来遍历list1和list2,每次循环会从这两个列表中选择一个较小的节点,并将其添加到合并列表的末尾。
  • 处理剩余节点: 循环结束后,list1和list2可能还有未处理的节点。以下的代码将剩余的节点添加到合并列表的末尾。
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//开始阶段if (!list1) return list2;if (!list2) return list1;//初始化合并链表的头ListNode* mergedHead = NULL;  // 合并后的链表头if (list1->val < list2->val) {mergedHead = list1;list1 = list1->next;} else {mergedHead = list2;list2 = list2->next;}ListNode* cur = mergedHead;  // 指向合并后链表的当前节点//合并过程while (list1 && list2) {if (list1->val <= list2->val) {cur->next = list1;list1 = list1->next;} else {cur->next = list2;list2 = list2->next;}cur = cur->next;}//处理剩余节点// 如果list1还有剩余节点if (list1) {cur->next = list1;}// 如果list2还有剩余节点if (list2) {cur->next = list2;}return mergedHead;
}

在这里插入图片描述


三、链表的中间结点

在这里插入图片描述
这题我们可以使用快慢指针,在循环中,fast 指针每次移动两个节点,而 slow 指针每次只移动一个节点。这意味着,当 fast 指针到达链表的末尾时,slow 指针将位于链表的中间位置。

 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

四、环形链表的约瑟夫问题

在这里插入图片描述
以下是代码的主要思路:

  1. 数据结构选择:
    使用单向循环链表来模拟这个问题。循环链表是一个适合此问题的数据结构,因为当链表到达末尾时,它可以自动回到头部。
  2. 链表节点创建:
    ListBuyNode(int x):这个函数用于创建一个新的链表节点,它接受一个整数值 x 作为参数,并返回一个新的链表节点。
  3. 循环链表创建:
    CreateList(int n):这个函数用于创建一个有 n 个节点的单向循环链表。链表的节点值从 1 到 n。链表的最后一个节点指向头节点,使其形成一个循环。
  4. 约瑟夫环算法:
  • ysf(int n, int m):这个函数实现了约瑟夫环的主要算法。
  • 首先,它调用 CreateList(n) 来创建一个 n 个节点的单向循环链表。
  • 使用两个指针,prev 和 cur,分别表示当前节点的前一个节点和当前节点。
  • 使用一个计数器 count 从 1 开始计数,每次循环增加计数器的值。
  • 当 count 达到 m 时,当前的 cur 节点将被删除(淘汰),并释放其内存。然后,cur 指向下一个节点,并且计数器重置为 1。
  • 如果 count 不等于 m,prev 和 cur 都向前移动一个节点,继续循环。
  • 当链表只剩下一个节点时(即 cur->next 等于 cur 时),循环结束。
  • 返回最后一个剩下的节点的值,即最后一个被淘汰的人的位置。
// 定义链表节点结构
typedef struct ListNode ListNode;// 分配内存并创建一个链表节点,值为x
ListNode* ListBuyNode(int x){ListNode* node = (ListNode*)malloc(sizeof(ListNode)); // 分配内存if(node == NULL){ // 检查内存分配是否成功perror("Malloc fail;");exit(1); // 分配失败,退出程序}node->val = x; // 设置节点的值node->next = NULL; // 初始化下一个节点为NULLreturn node; // 返回创建的节点
}// 创建一个包含n个节点的单向循环链表
ListNode* CreateList(int n){ListNode* phead = ListBuyNode(1); // 创建头节点,值为1ListNode* pTail = phead; // 初始化尾节点为头节点for(int i = 2; i <= n; i++){ // 从2到n循环创建节点ListNode* node = ListBuyNode(i); // 创建新节点pTail->next = node; // 把新节点连接到链表的尾部pTail = pTail->next; // 更新尾节点为新创建的节点}pTail->next = phead; // 将链表的尾部连接到头部,使其成为一个循环链表return pTail; // 返回链表的尾节点
}// 约瑟夫环问题的解决函数
int ysf(int n, int m ) {ListNode* prev = CreateList(n); // 创建一个单向循环链表,并返回尾节点ListNode* cur = prev->next; // 当前节点从头节点开始int count = 1; // 计数器初始化为1while(cur->next != cur){ // 当链表只剩下一个节点时停止循环if(count == m){ // 当计数器达到m时prev->next = cur->next; // 删除当前节点free(cur); // 释放当前节点的内存cur = prev->next; // 更新当前节点为下一个节点count = 1; // 重置计数器}else{prev = cur; // 否则,移动到下一个节点cur = cur->next;count++; // 增加计数器}}return cur->val; // 返回最后剩下的节点的值
}

在这里插入图片描述
如果你喜欢这篇文章,点赞👍+评论+关注⭐️哦!
欢迎大家提出疑问,以及不同的见解。

相关文章:

【数据结构】单链表OJ题

前言: 本节博客将讲解单链表的反转&#xff0c;合并有序链表&#xff0c;寻找中间节点及约瑟夫问题 文章目录 一、反转链表二、合并有序链表三、链表的中间结点四、环形链表的约瑟夫问题 一、反转链表 要反转链表&#xff0c;我们需要遍历链表并改变每个节点的 next 指针&#…...

智能工厂架构

引:https://www.bilibili.com/video/BV1Vs4y167Kx/?spm_id_from=333.788&vd_source=297c866c71fa77b161812ad631ea2c25 智能工厂框架 智能工厂五层系统框架 MES 数据共享 <...

阿里云多款ECS产品全面升级 性能最多提升40%

“阿里云始终围绕‘稳定、安全、性能、成本、弹性’的目标不断创新&#xff0c;为客户创造业务价值。”10月31日&#xff0c;杭州云栖大会上&#xff0c;阿里云弹性计算计算产品线负责人张献涛表示&#xff0c;通过持续的产品和技术创新&#xff0c;阿里云发布了HPC优化实例等多…...

责任链模式(Chain of Responsibility)

责任链模式是对象的行为模式。使多个对象都有机会处理请求&#xff0c;从而避免请求的发送者和接受者直接的耦合关系。 public abstract class Handler {protected Handler successor;public abstract void handlerRequest(String condition);protected Handler getSuccessor()…...

文件管理技巧:根据大小智能分类并移动至目标文件夹

在文件管理过程中&#xff0c;我们经常需要整理大量的文件。根据文件的大小&#xff0c;将其智能分类并移动至目标文件夹&#xff0c;可以帮助我们更高效地管理文件&#xff0c;提高工作效率。通过使用云炫文件管理器可以根据文件大小进行智能分类和移动至目标文件夹&#xff0…...

具有自主产权的SaaS门店收银系统全套源码输出

PHPMysql前后端分离&#xff0c; 小程序线上商城&#xff1b; 进销存管理库存盘点&#xff0c; 多仓库库存调拨&#xff0c; 会员系统。 消费者扫码查价系统。...

论文阅读:One Embedder, Any Task: Instruction-Finetuned Text Embeddings

1. 优势 现存的emmbedding应用在新的task或者domain上时表现会有明显下降&#xff0c;甚至在相同task的不同domian上的效果也不行。这篇文章的重点就是提升embedding在不同任务和领域上的效果&#xff0c;特点是不需要用特定领域的数据进行finetune而是使用instuction finetun…...

[BUUCTF NewStarCTF 2023 公开赛道] week3 crypto/pwn

居然把第3周忘了写笔记了. 后边难度上来了,还是很有意思的 Crypto Rabins RSA rsa一般要求e与phi互质,但rabin一般用2,都是板子题也没什么好解释的 from Crypto.Util.number import * from secret import flag p getPrime(64) q getPrime(64) assert p % 4 3 assert q %…...

软件测试---边界值分析(功能测试)

能对限定边界规则设计测试点---边界值分析 选取正好等于、刚好大于、刚好小于边界的值作为测试数据 上点: 边界上的点 (正好等于)&#xff1b;必选(不考虑区开闭) 内点: 范围内的点 (区间范围内的数据)&#xff1b;必选(建议选择中间范围) 离点: 距离上点最近的点 (刚好…...

使用pytorch处理自己的数据集

目录 1 返回本地文件中的数据集 2 根据当前已有的数据集创建每一个样本数据对应的标签 3 tensorboard的使用 4 transforms处理数据 tranfroms.Totensor的使用 transforms.Normalize的使用 transforms.Resize的使用 transforms.Compose使用 5 dataset_transforms使用 1 返回本地…...

http进一步认识

好久不见各位&#xff0c;今天为大家带来http协议的进一步认识 文章目录 &#x1f440;http协议的认识&#x1f440;新的改变 &#x1f440;http协议的认识 http协议经历了三个版本的演化&#xff0c;HTTP0.9是第一个版本的协议&#xff0c;它的组成极其简单&#xff0c;只涉…...

grafana docker安装

grafana docker安装 Grafana是一款用Go语言开发的开源数据可视化工具&#xff0c;可以做数据监控和数据统计&#xff0c;带有告警功能。目前使用grafana的公司有很多&#xff0c;如paypal、ebay、intel等。 Grafana 是 Graphite 和 InfluxDB 仪表盘和图形编辑器。Grafana 是开…...

【Kubernetes】初识k8s--扫盲阶段

文章目录 1、k8s概述2、为什么要有k8s2.1 回顾以往的应用部署方式2.2 容器具有的优势 3、k8s能带来什么 1、k8s概述 kubernetes是一个可移植、可扩展的开源平台&#xff0c;用于管理 容器化 的工作负载和服务&#xff0c;可促进申明式配置和自动化。kubernetes拥有一个庞大且快…...

“01”滴答“摩尔斯电码”加密解密单个字符

“01”替换滴嗒“.-”“摩尔斯电码”字符&#xff0c;加密解密键盘输入的单个字符。 (本笔记适合熟悉循环和列表的 coder 翻阅) 【学习的细节是欢悦的历程】 Python 官网&#xff1a;https://www.python.org/ Free&#xff1a;大咖免费“圣经”教程《 python 完全自学教程》&a…...

P3817 小A的糖果

Portal. 贪心。 注意到这里的盒子不会被删除&#xff0c;只会改变盒子的值。问题立刻简单化了。对于一组相邻的糖果个数和大于 x x x 的盒子组&#xff0c;优先吃掉靠后的盒子。 证明正确性也很显然&#xff0c;因为减少后面的盒子的糖果数可以使得后面的情况更优。 #incl…...

Yolov8目标识别与实例分割——算法原理详细解析

前言 YOLO是一种基于图像全局信息进行预测并且它是一种端到端的目标检测系统&#xff0c;最初的YOLO模型由Joseph Redmon和Ali Farhadi于2015年提出&#xff0c;并随后进行了多次改进和迭代&#xff0c;产生了一系列不同版本的YOLO模型&#xff0c;如YOLOv2、YOLOv3、YOLOv4&a…...

HandlerMethodArgumentResolver方法参数解析器支持多用户

1、概述 HandlerMethodArgumentResolver,中文称为方法参数解析器,是Spring Web(SpringMVC)组件中的众多解析器之一,主要用来对Controller中方法的参数进行处理。 使用场景 在一般的接口调用场景下,每次调用Controller都需要检查请求中的token信息,并根据token还原用户信息…...

【Linux】 man命令使用

介绍 man命令是Linux下最核心的命令之一。而man命令也并不是英文单词“man”的意思&#xff0c;它是单词manual的缩写&#xff0c;即使用手册的意思。 man命令会列出一份完整的说明。 其内容包括命令语法、各选项的意义及相关命令 。更为强大的是&#xff0c;不仅可以查看Lin…...

同一个数据库服务器进行数据表间的数据迁移-MySQL

同一个数据库服务器进行数据表间的数据迁移 一、相同结构的表数据迁移/备份/导入到同一MySQL的某个库的某张表 实验目标&#xff1a;将t1.table_one的数据备份到migration_one.table_11&#xff08;提醒&#xff1a;这两个表结构一致&#xff09; 同一个MySQL中有很多库&…...

适用于 Linux 的 WPF:Avalonia

许多年前&#xff0c;在 WPF 成为“Windows Presentation Foundation”并将 XAML 作为 .NET、Windows 等的 UI 标记语言引入之前&#xff0c;有一个代号为“Avalon”的项目。Avalon 是 WPF 的代号。XAML 现在无处不在&#xff0c;XAML 标准是一个词汇规范。 Avalonia 是一个开…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...

Unity VR/MR开发-VR开发与传统3D开发的差异

视频讲解链接&#xff1a;【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...