【数据结构】“单链表”的练习题

在这里插入图片描述

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 :阿然成长日记 👈点击可跳转
📆 个人专栏: 🔹数据结构与算法🔹C语言进阶
🚩 不能则学,不知则问,耻于问人,决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍

文章目录

  • 876.链表的中间节点
  • 203.移除链表元素
  • 牛客题---链表中倒数第k个结点
  • 反转链表
  • cm11-链表分割
  • 链表的回文结构

876.链表的中间节点

题目要求:

给你单链表的头结点 head ,请你找出并返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。
示例 1:

在这里插入图片描述

输入:head = [1,2,3,4,5]
输出:[3,4,5]
解释:链表只有一个中间结点,值为 3 。

示例 2:
在这里插入图片描述

输入:head = [1,2,3,4,5,6]
输出:[4,5,6]
解释:该链表有两个中间结点,值分别为 3 和 4,返回第二个结点。

思路:
1.定义快指针和慢指针
2.快指针一次走两步,慢指针一次走一步,
3.快指针走到链表最后时,快指针所走的距离正好是慢指针的二倍。

在这里插入图片描述

代码实现:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* low = head;struct ListNode* fast = head;while(fast && fast->next){low = low->next;fast = fast->next->next;}return low;
}

203.移除链表元素

题目要求:

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

示例 1:
在这里插入图片描述

输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5]

示例 2:

输入:head = [], val = 1 输出:[]

示例 3:

输入:head = [7,7,7,7], val = 7 输出:[]

思路:
1.如果第一个节点就是要删除的。进行头删
2.如果head一开始就是空,或者,进行N次头删之后,为空。就返回head
3.中间的节点正常删除。尾删与之一样。

在这里插入图片描述

代码:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val)
{  	   while(head && head->val == val) head = head->next;   //排除第一个节点就相等的情况if(!head) //如果删除第一个,判断是否就空了return head; struct ListNode* slow = head;     //定义快慢指针,也要写在上一步之后struct  ListNode* fast = head->next;while(fast) {if(fast->val==val) {        //遇到相等就删除slow->next = fast->next;fast = slow->next;}  else {                   //否则快慢指针依次后移slow = slow->next;fast = fast->next;}}return head;}

在这里插入图片描述

牛客题—链表中倒数第k个结点

题目要求:
输入一个链表,输出该链表中倒数第k个结点。
示例1

输入: 1,{1,2,3,4,5}
返回值: {5}

思路分析:
在这里插入图片描述
注意点:考虑链表为空的情况,K的值大于链表的长度。

代码:.

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code herestruct ListNode* fast = pListHead;struct ListNode* low = pListHead;int i = k-1;//判断是否为空,或这k有问题if(pListHead==NULL||k<=0)return NULL;while(i--){if(fast->next==NULL){return NULL;}fast = fast->next;}//两个指针开始同时移动,到最后low表示倒数k的节点    while(fast->next){low = low->next;fast = fast->next;}return low;}

答案正确!
注意:在测试样例中我发现个问题。
在这里插入图片描述
倒数第五个不应该是1吗?
原因是,fast后移k-1个,此时fast指针已经指向最后一个元素(fast->next==NULL),所以,根本就没有进行while循环,两个指针同步移动中去。又因为我们最开始给 low= =plisthead,所以,此时返回的是整个链表。

反转链表

头插法:
思路:
在这里插入图片描述

从头开始取链表的每一个节点插入到newnode之前

struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur = head;struct ListNode* newnode = NULL;//头插while(cur){//定义一个之指针用来保存下一个节点struct ListNode* tmp = cur->next;cur->next = newnode;//头插newnode = cur;//将newnode指针前移cur = tmp;}return newnode;
}

在这里插入图片描述

cm11-链表分割

描述
现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
思路:
在这里插入图片描述

代码:

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode* ghead,* gtail,* lhead,* ltail;lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = pHead;//遍历链表,大于等于x的放ghead链表中,小于x的放lhead链表while(cur){if(cur->val >= x){gtail->next = cur;//尾插gtail = gtail->next;//移向下一位}else {ltail->next = cur;//尾插ltail = ltail->next;}cur = cur->next;}ltail->next = ghead->next;gtail->next = NULL;struct ListNode* head = lhead->next;free(lhead);free(ghead);return head;}
};

链表的回文结构

题目:对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

测试样例: 1->2->2->1 返回:true

思路:
1.找到中间节点
2.从中间节点往后逆置
3.定义快慢指针,向后遍历判断是否相等。
在这里插入图片描述

class PalindromeList {
public:struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow = head,*fast = head;while(fast&& fast->next){slow = slow->next;fast = fast->next->next;}return slow;}struct ListNode* reveseList(struct ListNode* head){struct ListNode* cur = head;struct ListNode* newhead = nullptr;while(cur){struct ListNode* next = cur->next;cur->next = newhead;newhead  = cur;cur = next;} return newhead;} bool chkPalindrome(ListNode* head) {// write code herestruct ListNode* mid = middleNode(head);struct ListNode* rmid = reveseList(mid);while(rmid && head){if(rmid->val !=head->val){return false;}rmid = rmid->next;head = head->next;}return true;}
};

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

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

相关文章

vue使用FullCalendar插件实现日历会议预约功能

目录 1. vue 项目使用npm安装插件 2. vue 页面代码&#xff08;直接复制粘贴可用&#xff09; 3. vue FullCalendar的内置函数以及配置 前言&#xff1a;此案例是用FullCalendar插件做一个会议日程预约功能&#xff0c;此功能可查看自己的日程安排会议信息等...... FullC…

【ChatGPT 指令大全】怎么使用ChatGPT写履历和通过面试

目录 怎么使用ChatGPT写履历 寻求履历的反馈 为履历加上量化数据 把经历修精简 为不同公司客制化撰写履历 怎么使用ChatGPT通过面试 汇整面试题目 给予回馈 提供追问的问题 用 STAR 原则回答面试问题 感谢面试官的 email 总结 在职场竞争激烈的今天&#xff0c;写一…

安卓4G核心板开发板_MTK6785/MT6785(Helio G95)安卓手机主板方案

联发科MTK6785&#xff08;Helio G95&#xff09;安卓核心板采用八核 CPU 具有两个强大的 Arm Cortex-A76 处理器内核&#xff0c;主频高达 2.05GHz&#xff0c;外加六个 Cortex-A55 高效处理器。其强大的图形性能由 Arm Mali-G76 MC4 提供&#xff0c;速度可提升至 900MHz 。 …

Java 之LocalDateTime的介绍和使用

LocalDateTime是Java的日期和时间类之一&#xff0c;用于表示不带时区信息的日期时间。 LocalDateTime 没有时区&#xff0c; 所以也就不能用来直接获取时间戳LocalDateTime 是一个基于值得类&#xff0c; 所以该类的示例不是通过构造函数的方式进行创建 以下是一些关于Loca…

07. Docker网络通信模式

目录 1、前言 2、基本原理 3、Docker网络配置 3.1、查看网络配置 3.2、4种网络模式 3.3、bridge模式 3.3.1、使用bridge网络 3.3.2、自定义bridge网络 3.4、host模式 3.5、container模式 3.6、none模式 4、小结 1、前言 前面我们介绍了Docker容器的相关内容&#…

GaussDB数据库的元数据及其管理简介

目录 一、前言 二、元数据简介 1、元数据定义 2、元数据分类 3、数据库元数据管理 三、GaussDB数据库的元数据管理 1、GaussDB数据库的元数据管理 2、通过“SQL 系统表/系统视图/系统函数”的方式管理&#xff08;采集&#xff09;元数据 1&#xff09;获取表、视图及…

【雷达通信】非相干多视处理(CSA)(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

Kubernetes高可用集群二进制部署(三)部署api-server

Kubernetes概述 使用kubeadm快速部署一个k8s集群 Kubernetes高可用集群二进制部署&#xff08;一&#xff09;主机准备和负载均衡器安装 Kubernetes高可用集群二进制部署&#xff08;二&#xff09;ETCD集群部署 Kubernetes高可用集群二进制部署&#xff08;三&#xff09;部署…

vue2-v-if和v-for的优先级是什么?

1、v-if和v-for的区别 作用&#xff1a; v-if指令用于条件性地渲染一块内容&#xff0c;这块内容只会在指令的表达式返回true值的时候被渲染。 v-for指令基于一个数组来渲染一个列表&#xff0c;v-for指令需要使用item in items 形式的特殊语法&#xff0c;其中&#xff0c;it…

性能测试怎么做?测试工具怎么选择?

在当前软件测试行业&#xff0c;熟练掌握性能测试已经是测试工程师们面试的敲门砖了&#xff0c;当然还有很多测试朋友们每天的工作更多的是点点点&#xff0c;性能方面可能也只是做过简单的并发测试&#xff0c;对于编写脚本&#xff0c;搭建环境方面也比较陌生。今天这篇文章…

vue3搭建(vite+create-vue)

目录 前提条件 输入命令 对于Add an End-to-End Testing Solution nightwatch和Cypress 和 Playwright 运行 前提条件 熟悉命令行已安装 16.0 或更高版本的 Node.js &#xff08;node -v查看版本&#xff09; 输入命令 npm init vuelatest 这一指令将会安装并执行 create-…

NVIDIA 535.86.05 Linux 图形驱动程序改进 Wayland 支持

导读NVIDIA公司近日发布了适用于 Linux、FreeBSD 和 Solaris 系统的 NVIDIA 535.86.05 图形驱动程序&#xff0c;作为其生产分支的维护更新&#xff0c;解决了各种错误和问题。 NVIDIA 535.86.05 是在 NVIDIA 535.54.03 发布一个多月之后发布的&#xff0c;它通过解决在使用某…

PSO粒子群优化算法

PSO粒子群优化算法 算法思想matlab代码python代码 算法思想 粒子群算法&#xff08;Particle Swarm Optimization&#xff09; 优点: 1&#xff09;原理比较简单&#xff0c;实现容易&#xff0c;参数少。 缺点: 1&#xff09;易早熟收敛至局部最优、迭代后期收敛速度慢的…

linux 文件的权限

修改文件的权限 我这里有一个test.txt 文件&#xff0c;我们ll 查看一下该文件相应的属性信息 其中&#xff0c;权限的位置是相对固定的即&#xff1a; 第一个位置是r 权限&#xff0c;代表可读权限。 第二个位置是w权限&#xff0c;代表可修改权限。 第三个位置是x权限&…

SSL 证书过期巡检脚本 (Python 版)

哈喽大家好&#xff0c;我是咸鱼 之前写了个 shell 版本的 SSL 证书过期巡检脚本 &#xff08;文章&#xff1a;《SSL 证书过期巡检脚本》&#xff09;&#xff0c;后台反响还是很不错的 那么今天咸鱼给大家介绍一下 python 版本的 SSL 证书过期巡检脚本 &#xff08;完整代码…

本地mvn仓库清理无用jar包

背景 开发java时间久了&#xff0c;本地的m2仓库就会产生很多过期的jar包&#xff0c;不清理的话比较占空间。 原理 是通过比较同一目录下&#xff0c;对应jar包的版本号的大小&#xff0c;保留最大版本号那个&#xff0c;删除其他的。 脚本 执行脚本见文章顶部 执行方式 …

mac使用mvn下载node-sass 会Binary download failed, trying source

m1 上使用nvm 以下node的版本可以直接下载&#xff08;Binary download&#xff0c;而不是 trying source&#xff09;而不用切换mac cpu架构 zhiwenwenzhiwenwendeMBP cockpit % nvm install 14.15.5 Downloading and installing node v14.15.5... Downloading https://node…

华为云hcip核心知识笔记(存储服务规划)

云上存储 &#xff1a; 云硬盘:基于分布式架构&#xff0c;可弹性扩展的虚拟块存储服务 注意事项 挂载云硬盘实例和云硬盘必须在同一区域&#xff0c;否则挂载失败文件存储服务&#xff1a;完全托管的共享文件存储 可以为多个实例实现共享访问&#xff0c;不同vpc中可以进行对…

网络工程师 快速入门

需要掌握 以下技术 1.网络 基础 知识 TCP/IP 、OSI 7层协议、IP地址、ARP地址解析协议、ICMP&#xff08;英特网控制报文协议&#xff0c;ping&#xff09;等 入门面试常问问题。 2.路由 路由匹配 三原则、静态路由、OSPF路由协议。 2.交换 如何放数据&#xff1f; VLAN TRU…

【《快速构建AI应用——AWS无服务器AI应用实战》——基于云的解决方案快速完成人工智能项目的指南】

基于云的人工智能服务可以自动完成客户服务、数据分析和财务报告等领域的各种劳动密集型任务。其秘诀在于运用预先构建的工具&#xff0c;例如用于图像分析的Amazon Rekognition或用于自然语言处理的AWS Comprehend。这样&#xff0c;就无须创建昂贵的定制软件系统。 《快速构…