【数据结构初阶】链表OJ

链表OJ

    • 题目一:移除链表元素
    • 题目二:反转链表
    • 题目三:链表的中间节点
    • 题目四:链表中倒数第k个结点
    • 题目五:合并两个有序链表
    • 题目六:链表分割
    • 题目七:链表的回文结构
    • 题目八:相交链表
    • 题目九:环形链表
    • 题目十:环形链表II

题目一:移除链表元素

OJ
在这里插入图片描述
方案一:

题目解析:
在这里插入图片描述

代码演示:
struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head, * prev = NULL;while (cur){if (cur->val == val){if (cur == head){head = cur->next;free(cur);cur = head;}else{prev->next = cur->next;free(cur);cur = prev->next;}}else{prev = cur;cur = cur->next;}}return head;
}

方案二:

题目解析:把原链表遍历一遍,插入新链表
在这里插入图片描述

struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* newnode = NULL, * tail = NULL;struct ListNode* cur = head;while (cur){if (cur->val == val){struct ListNode* del = cur;cur = cur->next;free(del);}else{if (tail == NULL){newnode = tail = cur;//tail = tail->next;}else{tail->next = cur;tail = tail->next;}cur = cur->next;}}if (tail)tail->next = NULL;return newnode;
}

题目二:反转链表

OJ
外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

题目解析:
在这里插入图片描述

代码演示:
struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* reverseList(struct ListNode* head) 
{struct ListNode* newnode = NULL, * cur = head;while (cur){struct ListNode* next = cur->next;//尾插cur->next = newnode;newnode = cur;cur = next;}return newnode;
}

题目三:链表的中间节点

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode 
{int val;struct ListNode* next;
};
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fast = head, * slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

题目四:链表中倒数第k个结点

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) 
{struct ListNode* fast = pListHead, * slow = pListHead;while (k--){if (fast == NULL)return NULL;fast = fast->next;}while (fast){slow = slow->next;fast = fast->next;}return slow;
}

题目五:合并两个有序链表

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode 
{int val;struct ListNode* next;
};
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{if (list1 == NULL)return list2;if (list2 = NULL)return list1;struct ListNode* tail = NULL, * head = NULL;head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));while (list1 && list2){if (list1->val < list2->val){tail->next = list1;tail = tail->next;list1 = list1->next;}else{tail->next = list2;tail = tail->next;list2 = list2->next;}}if (list1)tail->next = list1;if (list2)tail->next = list2;struct ListNode* del = head;head = head->next;free(del);return head;
}

题目六:链表分割

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode 
{int val;struct ListNode* next;ListNode(int x) : val(x), next(NULL) {}
}; 
class Partition
{
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lhead, * ltail, * gtail, * ghead;ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = pHead;while (cur){if (cur->val < x){ltail->next = cur;ltail = ltail->next;}else{gtail->next = cur;gtail = gtail->next;}cur = cur->next;}ltail->next = ghead->next;gtail->next = NULL;struct ListNode* head = lhead->next;free(lhead);free(ghead);return head;}
};

题目七:链表的回文结构

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode 
{int val;struct ListNode* next;ListNode(int x) : val(x), next(NULL) {}
}; 
class PalindromeList
{
public:struct ListNode* middleNode(struct ListNode* head){struct ListNode* fast = head, * slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}struct ListNode* reverseList(struct ListNode* head){struct ListNode* newnode = NULL, * cur = head;while (cur){struct ListNode* next = cur->next;cur->next = newnode;newnode = cur;cur = next;}return newnode;}bool chkPalindrome(ListNode* A){struct ListNode* mid = middleNode(A);struct ListNode* rmid = reverseList(mid);while (A && rmid){if (A->val != rmid->val)return false;A = A->next;rmid = rmid->next;}return true;}
};

题目八:相交链表

OJ
在这里插入图片描述

题目解析:
定义快慢指针,使快指针先走与慢指针同步。然后同时走看是否相交
在这里插入图片描述

代码演示:
struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{struct ListNode* curA = headA, * curB = headB;int lenA = 1, lenB = 1;while (curA){curA = curA->next;lenA++;}while (curB){curB = curB->next;lenB++;}if (curA != curB)return false;int gab = abs(lenA - lenB);struct ListNode* longest = headA, * shortest = headB;if (lenA < lenB){longest = headB;shortest = headA;}while (gab--){longest = longest->next;}while (shortest != longest){shortest = shortest->next;longest = longest->next;}return longest;
}

题目九:环形链表

OJ

在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode {int val;struct ListNode* next;
};
bool hasCycle(struct ListNode* head)
{struct ListNode* fast = head, * slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast)return true;}return false;
}

题目十:环形链表II

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* detectCycle(struct ListNode* head)
{struct ListNode* fast = head, * slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){struct ListNode* meet = slow;while(meet != head){head = head->next;meet = meet->next;}return meet;}}return NULL;
}

💘不知不觉,【数据结构初阶】链表OJ以告一段落。通读全文的你肯定收获满满,让我们继续为数据结构学习共同奋进!!!

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

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

相关文章

遗传算法GA-算法原理与算法流程图

本站原创文章&#xff0c;转载请说明来自《老饼讲解-BP神经网络》bp.bbbdata.com 目录 一、遗传算法流程图 1.1. 遗传算法流程图 二、遗传算法的思想与机制 2.1 遗传算法的思想 2.2 遗传算法的机制介绍 三、 遗传算法的算法流程 3.1 遗传算法的算法…

Ubuntu20.04 安装微信 【优麒麟的镜像源方式安装】

缺点&#xff1a;是网页版本的嵌入&#xff0c;功能少。 推荐wine方式安装&#xff1a;Ubuntu20.04 安装微信 【wine方式安装】推荐 从优麒麟的镜像源安装原生微信 应用下载-优麒麟&#xff5c;Linux 开源操作系统 新建文件software.list sudo vi /etc/apt/sources.list.d/…

损失函数(Loss Function)与代价函数(Cost Function)、目标函数(Objective Function)区别

损失函数定义在单个样本上&#xff0c;算的是一个样本的误差。 代价函数定义在整个训练集上&#xff0c;是所有样本误差的平均&#xff0c;也就是损失函数的平均。 目标函数定义为最终需要优化的函数&#xff0c;等于经验风险 结构风险&#xff08;也就是Cost Function 正则化…

提升工作效率,打造精细思维——OmniOutliner 5 Pro for Mac

在当今快节奏的工作环境中&#xff0c;如何高效地组织和管理我们的思维和任务成为了关键。而OmniOutliner 5 Pro for Mac正是为此而生的一款强大工具。无论你是专业写作者、项目经理还是学生&#xff0c;OmniOutliner 5 Pro for Mac都能帮助你提升工作效率&#xff0c;打造精细…

【开源】基于JAVA的服装店库存管理系统

项目编号&#xff1a; S 052 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S052&#xff0c;文末获取源码。} 项目编号&#xff1a;S052&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 角色管理模块2.3 服…

正则表达式入门教程

一、本文目标 让你明白正则表达式是什么&#xff0c;并对它有一些基本的了解&#xff0c;让你可以在自己的程序或网页里使用它。 二、如何使用本教程 文本格式约定&#xff1a;专业术语 元字符/语法格式 正则表达式 正则表达式中的一部分(用于分析) 对其进行匹配的源字符串 …

Kafka的重要组件,谈谈流处理引擎Kafka Stream

系列文章目录 上手第一关&#xff0c;手把手教你安装kafka与可视化工具kafka-eagle Kafka是什么&#xff0c;以及如何使用SpringBoot对接Kafka 架构必备能力——kafka的选型对比及应用场景 Kafka存取原理与实现分析&#xff0c;打破面试难关 防止消息丢失与消息重复——Kafka可…

CentOS挂载:解锁文件系统的力量

目录 引言1 挂载简介2 挂载本地分区3 挂载网络共享文件系统4 使用CIFS挂载结论 引言 在CentOS&#xff08;一种基于Linux的操作系统&#xff09;上挂载文件系统是一项常见而重要的任务&#xff0c;无论是将新的磁盘驱动器添加到系统&#xff0c;还是挂载网络共享资源&#xff…

【flutter】使用getx下的GetMaterialApp创建路由和使用时间选择器国际化问题

GetMaterialApp是啥 网上解释说是 MaterialApp Getx properties GetMaterialApp 问题 在使用showDateRangePicker组件的时候&#xff0c; 一直报错 No MaterialLocalizations found 我就愁思是不是GetMaterialApp跟MaterialApp方法不一样的问题&#xff0c;结果不是&#…

城市网吧视频智能监控方案,实现视频远程集中监控

网吧环境较为复杂&#xff0c;电脑设备众多且人员流动性大&#xff0c;极易发生人员或消防事故&#xff0c;亟需改变&#xff0c;TSINGSEE青犀AI智能网吧视频监管方案可以帮助实现对网吧环境和用户活动的实时监控和管理。 1、视频监控系统 在网吧内部布置高清摄像头&#xff0…

【C++入门到精通】右值引用 | 完美转发 C++11 [ C++入门 ]

阅读导航 引言一、左值引用和右值引用1. 什么是左值&#xff1f;什么是左值引用&#xff1f;2. 什么是右值&#xff1f;什么是右值引用&#xff1f;3. move( )函数 二、左值引用与右值引用比较三、右值引用使用场景和意义四、完美转发std::forward 函数完美转发实际中的使用场景…

SSM项目初始化流程与操作概念解释-SpringBoot简化版

文章目录 1.引入概念2.导入依赖3.项目配置4.依照SpringMVC框架构建项目 1.引入概念 例如某一个XX系统&#xff0c;该系统存在前台页面&#xff08;给用户直观看或使用&#xff09;&#xff0c;和后台页面&#xff08;给管理人员调整数据和权限&#xff09;。 这二个页面都通过…

机器学习笔记 - Ocr识别中的文本检测EAST网络概述

一、文本检测 文本检测简单来说就是找到图像中可以出现文本的区域。例如,请参见下图,其中在检测到的文本周围绘制了绿色边框。 在进行文本检测时,你可能会遇到两种情况 具有结构化文本的图像:这是指具有干净/均匀背景和常规字体的图像。文本大多密集,行结构正确,…

uniapp中使用render.js进行openers、arcgis等地图操作

uniapp中使用render.js进行openers、arcgis等地图操作 一、为啥需要render.js render.js主要作用于APP上&#xff0c;因为Uniapp本质为vuejshtml进行开发&#xff0c;整个技术栈还是H5&#xff0c;对DOM元素进行操作。而APP中没用Dom元素这个概念。因此利用render.js这个视图层…

GEM5 Garnet DVFS / NoC DVFS教程:ruby.clk_domain ruby.voltage_domain

简介 gem5中的 NoC部分是Garnet实现的&#xff0c;但是Garnet并没有单独的时钟域&#xff0c;而是保持ruby一致&#xff0c;要做noc的DVFS&#xff0c;便是要改ruby的 改电压 #这里只是生成一个随便变量名&#xff0c;存一下值。改是和频率一起的 userssaved_voltage_domain…

C++二分查找算法:查找和最小的 K 对数字

相关专题 二分查找相关题目 题目 给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。 定义一对值 (u,v)&#xff0c;其中第一个元素来自 nums1&#xff0c;第二个元素来自 nums2 。 请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。 示例 1:…

采用Nexus搭建Maven私服

采用Nexus搭建Maven私服 1.采用docker安装 1.创建数据目录挂载的目录&#xff1a; /usr/local/springcloud_1113/nexus3/nexus-data2.查询并拉取镜像docker search nexus3docker pull sonatype/nexus33.查看拉取的镜像docker images4.创建docker容器&#xff1a;可能出现启动…

【数据结构】树与二叉树(十八):树的存储结构——Father链接结构、儿子链表链接结构

文章目录 5.1 树的基本概念5.1.1 树的定义5.1.2 森林的定义5.1.3 树的术语 5.2 二叉树5.3 树5.3.1 树的存储结构1. 理论基础2. 典型实例 5.3.2 Father链接结构a. 定义树节点结构b. 创建新节点c. 主函数d. 代码整合 5.3.3 儿子链表链接结构a. 定义树节点结构b. 创建新节点c. 添加…

【IDEA 使用easyAPI、easyYapi、Apifox helper等插件时,导出接口文档缺少代码字段注释的相关内容、校验规则的解决方法】

问题 IDEA 使用easyAPI、easyYapi、Apifox helper等插件时&#xff0c;导出的接口文档上面&#xff0c;缺少我们代码里的注解字段&#xff0c;如我们规定了NOTNULL、字段描述等。 问题链接&#xff0c;几个月之前碰到过&#xff0c;并提问了&#xff0c;到现在解决&#xff0c…

Docker之DockerFile解析

DockerFile解析 是什么 Dockerfile是用来构建Docker镜像的文本文件&#xff0c;是由一条条构建镜像所需的指令和参数构成的脚本。 概述 官网 https://docs.docker.com/engine/reference/builder/ 构建三步骤 编写Dockerfile文件 docker build命令构建镜像 docker run依镜像运…