【数据结构】单链表的应用

1.移除链表元素

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

思路: 创建新链表,找值不为val的节点,尾插到新链表中

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {ListNode*newHead,*newTail;  //创建新链表的头指针和尾指针newHead=newTail=NULL;//遍历原链表ListNode*pcur=head;while(pcur){//找值不为val的节点,尾插到新链表中if(pcur->val!=val){//链表为空  第一次插入if(newHead==NULL){newHead=newTail=pcur;}else{// 链表不为空   后续插入newTail->next=pcur;newTail=newTail->next;}         }pcur=pcur->next;}if(newTail)  //防止输入一个空链表对空指针解引用newTail->next=NULL;  //尾部置空return newHead;
}

 2.反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

 思路:创建三个指针,完成原链表的翻转。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {//判空if(head==NULL){return head;}//创建3个指针ListNode*n1,*n2,*n3;n1=NULL;n2=head;n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)//n3可能已经走到空了n3=n3->next;}return n1;
}

3.链表的中间节点

给你单链表的头结点 head ,请你找出并返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

思路:使用快慢指针,慢指针每次走一步,快指针每次走两步。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {//创建快慢指针ListNode*slow=head;ListNode*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}//此时slow刚好指向中间节点return slow;
}

while(fast&&fast->next) 语句可以写成 while(fast->next&&fast)吗?

不可以。若链表中有偶数个节点,fast最后会直接走到空,fast->next操作对空指针进行解引用,会报错!

4.合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

思路:创建新的空链表,遍历原链表,将节点值小的节点拿到新链表中进行尾插操作。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//判空  list1为空  list2为空  list和list2都为空if(list1==NULL){return list2;}if(list2==NULL){return list1;}ListNode*l1=list1;ListNode*l2=list2;//创建的新链表ListNode*newHead=NULL;ListNode*newTail=NULL;while(l1&&l2){if(l1->val<l2->val){//l1拿下来尾插if(newHead==NULL){newHead=newTail=l1;}else{newTail->next=l1;newTail=newTail->next;}l1=l1->next;}else{//l2拿下来尾插if(newHead==NULL){newHead=newTail=l2;}else{newTail->next=l2;newTail=newTail->next;}l2=l2->next;}}//跳出循环有两种情况:一.l1走到空了 二.l2走到空了if(l2){newTail->next=l2;}if(l1){newTail->next=l1;}return newHead;
}

仔细观察,上面代码存在重复,重复操作判断链表是否为空,怎么解决这个问题呢?

让新链表不为空。使用malloc函数给 newHead 和 newTail 指针申请一块空间,它们不再是空指针,此时链表不为空,头尾指针都指向了一个有效的地址。如下图,newHead为头结点,被称为“哨兵位

代码优化为:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//判空  list1为空  list2为空  list和list2都为空if(list1==NULL){return list2;}if(list2==NULL){return list1;}ListNode*l1=list1;ListNode*l2=list2;//创建的新链表ListNode*newHead,*newTail;newHead=newTail=(ListNode*)malloc(sizeof(ListNode));    while(l1&&l2){if(l1->val<l2->val){//l1拿下来尾插newTail->next=l1;newTail=newTail->next;l1=l1->next;}else{//l2拿下来尾插newTail->next=l2;newTail=newTail->next;l2=l2->next;}}//跳出循环有两种情况:1.l1走到空了 2.l2走到空了if(l2){newTail->next=l2;}if(l1){newTail->next=l1;}//动态申请的空间手动释放掉ListNode* ret=newHead->next; //newHead的下一个节点保存下来free(newHead);newHead=NULL;return ret;  
}

5.循环链表经典应用

——环形链表的约瑟夫问题

著名的Josephus问题

据说著名犹太 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与 Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个人重新报数,直到所有人都自杀身亡为止。 然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己自排在第16个与第31个位置,于是逃过了这场死亡游戏。

题目描述

思路: 

typedef struct ListNode ListNode;//创建节点ListNode* buyNode(int x){ListNode*node=(ListNode*)malloc(sizeof(ListNode));if(node==NULL){exit(1);}node->val=x;node->next=NULL;return node;}ListNode*createCircle(int n){//先创建头节点ListNode* phead=buyNode(1);ListNode* ptail=phead;for (int i=2; i<=n; i++) {ptail->next=buyNode(i);ptail=ptail->next;}ptail->next=phead;//首尾相连,链表成环return ptail;}int ysf(int n, int m ) {// 根据n创建带环链表ListNode*prev=createCircle(n);ListNode*pcur=prev->next;int count=1; //计数while(pcur->next!=pcur){if(count==m){//销毁pcur节点prev->next=pcur->next;free(pcur);pcur=prev->next;count=1;}else{prev=pcur;pcur=pcur->next;count++;}}//此时剩下一个节点,返回的节点里的值return pcur->val;
}

6.分割链表

题目描述

 

思路: 

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){if(head==NULL){return head;}//创建两个带头链表ListNode*lessHead,*lessTail;ListNode*greaterHead,*greaterTail;lessHead=lessTail=(ListNode*)malloc(sizeof(ListNode));  greaterHead=greaterTail= (ListNode*)malloc(sizeof(ListNode));//遍历原链表,将原链表中的节点尾插到大小链表中ListNode*pcur=head;while(pcur){if(pcur->val<x){//尾插到小链表中lessTail->next=pcur;lessTail=lessTail->next;}else{//尾插到大链表中greaterTail->next=pcur;greaterTail=greaterTail->next;}pcur=pcur->next;}//修改大链表的尾节点的next指针的指向greaterTail->next=NULL;  //小链表的尾节点和大链表的第一个有效节点首尾相连lessTail->next=greaterHead->next;ListNode*ret=lessHead->next;free(lessHead);free(greaterHead);lessHead=greaterHead=NULL;return ret;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/418578.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

OpenAI发布GPT-4o mini,3.5从此退出历史舞台?

随着OpenAI在2024年7月18日正式发布GPT-4o Mini&#xff0c;无疑在科技界引发了一场新的风暴。这一创新不仅标志着GPT-3.5模型正式退出历史舞台&#xff0c;更预示着人工智能在自然语言处理领域迈入了一个全新的时代。 之前速度最快的模型一直是GPT3.5&#xff0c;随着后来的GP…

基于大数据的科研热点分析与挖掘系统

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长 QQ 名片 :) 1. 项目简介 科研活动的快速发展产生了大量的学术文献&#xff0c;如何从这些文献中提炼出有价值的科研热点和趋势成为了一个重要的问题。本项目旨在开发一个基于大数据的科研热点分析可视化系统&#xff0c;采…

python tkinter 文本类组件

Label组件 Label(win,text文本,justifycenter) win指定Label组件的父容器&#xff1b;text指定标签中的文本&#xff1b;justify指定标签中拥有多行文本时&#xff0c;最后一行文本的对齐方式。 from tkinter import * from PIL import Image,ImageTkroot Tk() root.title(…

水晶连连看 - 无限版软件操作说明书

水晶连连看 – 无限版游戏软件使用说明书 文章目录 水晶连连看 – 无限版游戏软件使用说明书1 引言1.1 编写目的1.2 项目名称1.3 项目背景1.4 项目开发环境 2 概述2.1 目标2.2 功能2.3 性能 3 运行环境3.1 硬件3.2 软件 4 使用说明4.1 游戏开始界面4.2 游戏设定4.2.1 游戏帮助4…

「大数据分析」图形可视化,如何选择大数据可视化图形?

​图形可视化技术&#xff0c;在大数据分析中&#xff0c;是一个非常重要的关键部分。我们前期通过数据获取&#xff0c;数据处理&#xff0c;数据分析&#xff0c;得出结果&#xff0c;这些过程都是比较抽象的。如果是非数据分析专业人员&#xff0c;很难清楚我们这些工作&…

前端常用工具网站分享:MemFire Cloud,懒人开发者的福音

你是否曾梦想过&#xff0c;有那么一款工具&#xff0c;能够让你像变魔术一样快速搭建起一个应用&#xff0c;而无需深陷复杂的后端搭建和接口开发的泥潭&#xff1f;今天&#xff0c;我要为你介绍的&#xff0c;就是这样一个神奇的存在——MemFire Cloud&#xff0c;一款专为懒…

13款常用AI编程工具

AI编程工具的选择和使用&#xff0c;主要取决于具体的项目需求、编程语言、以及AI任务的类型&#xff08;如机器学习、自然语言处理、计算机视觉等&#xff09;。下面是一些广泛使用的AI编程工具合集&#xff0c;涵盖了从开发、训练、到部署的各个环节&#xff1a; Jupyter Not…

随手记:小程序体积超出2M包大小如何优化

小程序的包体积限制是2M&#xff0c;超出包大小如何优化 先简单列出&#xff0c;最近比较忙&#xff0c;后续优化明细&#xff0c;有着急的先留言踢我 1.分包 留几个主要的页面体积小的&#xff0c;剩下的在page.json中拆到subpackages中&#xff0c;简单举个例子 "page…

【C++ Primer Plus习题】10.8

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream> #include "List.h" …

[数据集][目标检测]水面垃圾检测数据集VOC+YOLO格式2027张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;2027 标注数量(xml文件个数)&#xff1a;2027 标注数量(txt文件个数)&#xff1a;2027 标注…

MarkdownEditor 配置以及使用

MarkdownEditor 配置以及使用 MarkdownEditor是一款基于浏览器的 Markdown 编辑器&#xff0c;虽然他是独立软件&#xff0c;但该软件内嵌一个浏览器。功能非常简单实用、反应速度很快&#xff0c;号称是Markdown领域的NotePad&#xff08;记事本&#xff09;。 MarkdownEdit…

JDBC与数据库之间的操作(增删改查、获取主键、业务逻辑分离、属性文件配置)

参考视频哔哩哔哩 1、Service和Servicelmpl的概念 java中service和servicelmpl是常见的代码组织方式 Service是指业务逻辑的接口&#xff0c;定义了系统对外提供的功能。Servicelmpl是Service接口的具体实现&#xff0c;实现了具体的业务逻辑。 Service和Servicelmpl的好处…

SpinalHDL之数据类型(一)

本文作为SpinalHDL学习笔记第五十四篇,介绍SpinalHDL的Bool数据类型。 SpinalHDL技术交流QQ群: Note: 1.本群是个人技术交流群,不是什么官方答疑群; 2.提问是你的权利,但回答不是别人的义务; 3.可以潜水,不能灌水; 4.请文明交流,做这行的都算高层次人才,希望你…

黑神话悟空背后的技术揭秘与代码探秘

《重塑神话&#xff1a;黑神话悟空背后的技术揭秘与代码探秘》 引言 在国产游戏领域&#xff0c;《黑神话:悟空》无疑是一颗璀璨的明星&#xff0c;它不仅融合了深厚的中国文化元素&#xff0c;更在技术上实现了诸多突破&#xff0c;为玩家带来了前所未有的沉浸式体验。本文将…

sqli-lab靶场学习(一)——Less1-4

前言 最近一段时间想切入安全领域&#xff0c;因为本身有做数据库运维工作&#xff0c;就打算从sql注入方向切入。而sql注入除了学习日常书本上的概念外&#xff0c;需要有个实践的环境&#xff0c;刚好看到sqli-lab这个靶场&#xff0c;就打算先用这个来学习。 安装部署 网上…

HTTP“请求”和“响应”的报头及正文详解

目录 一、请求 "报头" (header) 二、请求 "正文" (body) 2.1 application/x-www-form-urlencoded 2.2 multipart/form-data 2.3 application/json 三、HTTP 响应状态码 四、响应 "报头" (header) 五、响应 "正文" (body) 5.1…

微信小程序实践案例

参考视频&#xff1a; https://www.bilibili.com/video/BV1834y1676P/?p36&spm_id_frompageDriver&vd_sourceb604c19516c17da30b6b1abb6c4e7ec0 前期准备 1、新建三个页面 "pages": ["pages/home/home","pages/message/message",&quo…

智慧交通基于yolov8的井盖异常检测系统python源码+onnx模型+评估指标曲线+精美GUI界面

【算法介绍】 智慧交通中的井盖异常检测系统&#xff0c;基于先进的YOLOv8算法&#xff0c;为城市基础设施的安全管理提供了强有力的技术支持。该系统通过集成YOLOv8的深度学习技术&#xff0c;实现了对道路井盖状态的实时、精准监测。 YOLOv8以其高效、准确的特点&#xff0…

为什么现在不建议去电力设计院?终于有人把电力设计院说清楚了!

作者&#xff1a;电气哥 最近电气哥收到了许多面临就业的同学特别是硕士同学有关于电力设计院的咨询&#xff0c;那么现在电力设计院到底还值不值得去&#xff1f;电气哥带你来分析一下电力设计院的前世今生。 01 电力设计院的前世今生 曾经&#xff0c;在我国的大基建时代&…

“Docker网络模式详解与应用“

目录 前言 Docker内置网络 bridge 基本概念 案例 工作原理 使用场景 host 基本概念 案例 工作原理 使用场景 none 基本概念 案例 &#xff01;&#xff01;&#xff01;大佬救命 container 基本概念 案例 自定义网络 自定义bridge 基本概念 案例 Docker…