顺序表链表OJ题(2)->【数据结构】

W...Y的主页 😊

代码仓库分享 💕


前言:

单链表的结构常常不完美,没有双向链表那么”优秀“,所以繁衍出很多OJ练习题。今天我们继续来look look数据结构习题。

下面就是OJ时间!!!

【链表中倒数第K个节点】——牛客网

OJ链接

描述

输入一个链表,输出该链表中倒数第k个结点。

示例1

输入:

1,{1,2,3,4,5}

返回值:

{5}

题目函数接口:

pListHead:目标链表。k:倒数第K个节点。


理论上我们可以先遍历一遍求出链表长度,然后创建一个指针使其走过(k-1)个元素即可找到链表中倒是第k个节点。

但是这道题我们要把时间复杂度降到最大,只能遍历一遍,我们该怎么应对?

我们可以创建两个指针(快慢)slow和fast,将fast先走k个节点,然后让fast与slow开始一块走,直到fast指向NULL停止,这时slow指向的节点就是我们需要倒数第k个节点!!!

这里的快慢指针所使用的是路程差,让fast先走k个就是让slow少走k个,所得到的节点就是倒数第k个节点。

代码演示:

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* slow = pListHead;struct ListNode* fast = pListHead;while(k--){if(fast == NULL)return NULL;fast = fast->next;}while(fast){slow = slow->next;fast = fast->next;}return slow;
}

【leetcode 21.合并两个有序链表】

OJ链接 

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

提示:

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

题目函数接口:

 list1:目标链表1。list2:目标链表2。


 这道题与上篇博客中合并顺序表思路大同小异,创建一个新节点,取小的尾插到节点后面即可。

我们可以创建两个指针head与tail,head记录新链表的头节点,tail记录新链表的尾节点。

代码演示:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode* cur = list1;struct ListNode* tal = list2;struct ListNode* head = NULL;struct ListNode* tail = NULL;if(list1 == NULL)return list2;if(list2 == NULL)return list1;while(tal && cur){if(cur->val>=tal->val){if(head == NULL){head = tail = list2;}else{tail->next = tal;tail = tail->next;}tal = tal->next;}else{if(cur->val<tal->val){if(head == NULL){head = tail = list1;}else{tail->next = cur;tail = tail->next;}}cur = cur->next;}}if(cur)tail->next = cur;if(tal)tail->next = tal;return head;
}

 注意:这种题我们就必须考虑完善,比如:一个链表为空,我们就应该考虑这种情况应该直接返回另一个链表即可。 

if(list1 == NULL)

        return list2;

if(list2 == NULL)
        return list1;

这四句就是考虑为空的情况的,所以我们做题必须全面!!!

 【CM11  链表分割】——牛客网

OJ链接

描述:

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

题目函数接口:

我们一看这个函数接口为c++,但是c++与c在这个函数中内容相同,所以使用c语言也是ok

pHead:目标链表。x:分割数。


我们先举个实际例子说清楚题目含义:【1 3 2 5 1】x = 3

我们就应该以3为分界线,将小于3的放在链表前面,大于等于3的放在链表后面且顺序不能改变,得到的顺序应该为:【1 2 1 3 5】。

那我们该如何实现呢?

我们可以创建两条链表,将小于x的放入链表1,大于等于x的放入链表2中,然后进行合并即可得到结果。

大致思路已经出炉,现在我们应该考虑一下细节该怎么处理。

两条链表我们应该选带哨兵位的还是不带哨兵位的?

哨兵位是为了我们更好的头插,一般情况下带不带哨兵位都可以,不使用哨兵位可以使用二级指针进行操作,效果是相同的。但是这道题是带哨兵位的链表简单些,因为有特殊情况,比如小于x的链表内容为空,如果我们我们进行合并,可能会丢失数据,所以我们得用很多if语句进行判断才行,但是有了哨兵位就不需要考虑这么多问题。

代码演示:

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {ListNode*ghead = NULL;ListNode*gtail = NULL;ListNode*lhead = NULL;ListNode*ltail = NULL;ghead = gtail = (ListNode*)malloc(sizeof(ListNode));lhead = ltail = (ListNode*)malloc(sizeof(ListNode));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;ListNode*head = lhead->next;free(lhead);free(ghead);return head;}
};

【OR36 链表的回文结构】——牛客网

OJ链接

描述:

对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。

给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

测试样例:

1->2->2->1

返回:true

题目函数接口:

 A:目标链表。


那什么是回文呢?

奇数回文:1->2->3->2->1  偶数回文:1->2->2->1

如果是数组,可以从后往前进行非常简单,但是这时链表,应该怎么办呢?

使用快慢指针找到链表的中间节点,将中间节点后面的链表内容反转,然后用两个指针,一个在中间节点处,一个在链表最开始出,进行移动比较,如果都相同则为回文结构,反之则不是回文结构。

代码演示:

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

 此程序我们封装了两个函数,一个为寻找中间节点的函数,一个为链表反转函数。当我们反转链表后,我们不需要将中间节点的next重新连接,让其成为相交链表即可。

这样判断的长度也一样,不需要考虑何时停止。 

【leetcode 160.相交链表】

OJ链接 

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

图示两个链表在节点 c1 开始相交

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构 。

自定义评测:

评测系统 的输入如下(你设计的程序 不适用 此输入):

  • intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
  • skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。

题目函数接口:

headA:目标链表A。headB:目标链表B。


如何判断两个链表相交,因为单链表一个结构体中只有一个next节点存放下一个结构体,所以只需要判断尾节点地址是否相等即可。虽然我们找的不是最开始相交的点,但是这样的思想非常简便。 

首先按照前面思路,判断两个链表是否相交,如果不相交就没有做下去的必要了,直接返回NULL即可。但是如果有节点我们就要寻找起始节点位置。

两个相交链表是由一段不相交的与一段相交的组合一起的,两段链表不一样长的那一段一定在不相交的位置。所以我们可以让较长的链表先遍历两个链表长度之差个节点,这样两个链表就一样长了,再进行逐一比较即可找到起始相交节点!!!

那我们想要知道两个链表长度就可以再判断两个链表是否相交时进行计数,因为判断两个链表相交就是判断尾节点是否相等,就是要将两个链表全部遍历一遍,一举两得。

理论形成,实践开始:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int lena = 1;int lenb = 1;struct ListNode *cura = headA;struct ListNode *curb = headB;while(cura->next){cura = cura->next;lena++;}while(curb->next){curb = curb->next;lenb++;}if(cura != curb){return NULL;}int gap = abs(lena-lenb);struct ListNode *llist = headA;struct ListNode *slist = headB;if(lena > lenb){;}else{llist = headB;slist = headA;}while(gap--){llist = llist->next;}while(llist != slist){llist = llist->next;slist = slist->next;}return llist;
}

【leetcode 141.环形链表】 

OJ链接

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

题目函数接口:

 head:目标链表。


什么是环形链表,我们最先见到过的就是循环列表: 

但其实环形链表还有很多:

向上面的我们都可以称作环形链表。

那我们应该怎样判断出链表为环形链表呢?

这里我们还是基于快慢指针进行,如同数学中的追及问题一样,如果在一个环形跑到中,两个人速度不同,但是快的人落后于慢的人,快的人总会追到慢的人。

我们创建两个指针fast与slow,s两个人都从开始进行,slow走一步,fast走两步,如果有环它们一定会进入环中进行追及。 代码演示:

bool hasCycle(struct ListNode *head) {struct ListNode *fast = head;struct ListNode *slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(fast == slow){return true;}}return false;
}

 以上是本次数据结构OJ题分享,感谢大家观看,三连支持一下博主,博主会干劲十足的!!!

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

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

相关文章

Vue安装过程的困惑解答——nodejs和vue关系、webpack、vue-cli、vue的项目结构

文章目录 1、为什么在使用vue前要下载nodejs&#xff1f;2、为什么安装nodejs后就能使用NPM包管理工具&#xff1f;3、为什么是V8引擎并且使用C实现&#xff1f;4、为什么会安装淘宝镜像&#xff1f;5、什么是webpack模板&#xff1f;6、什么是脚手架 vue-cli&#xff1f;6.1 安…

9.1 消息 字体 颜色 文件对话框 发布软件

保存 void Widget::on_savebtn_clicked() {QString filename QFileDialog::getSaveFileName(this, "保存", "C:/Users/yc/Desktop/", "图片 (*.png *.xpm *.jpg);;文本 (*.txt);;所有文件 (*.*)");if(filename.isNull()){QMessageBox::informa…

window下jdk安装及更换jdk版本的一些问题。

目录 jdk安装jdk的选择。oracle的jdk怎么安装。openjdk怎么安装。 jdk的版本控制。更换jdk的一些问题。 jdk安装 jdk的选择。 目前有两种可选的jdk&#xff0c;oracle的和开源的Openjdk&#xff0c;这两种jdk的区别可以自行查阅&#xff0c;就结果而言&#xff0c;openjdk开源…

包含文心一言在内的首批国产大模型 全面开放

8月31起&#xff0c;国内 11 家通过《生成式人工智能服务管理暂行办法》备案的 AI 大模型产品将陆续上线&#xff0c;面向全社会开放。北京 5 家大模型产品分别是百度的 “文心一言”、抖音的 “云雀”、百川智能的 “百川大模型”、清华系 AI 公司智谱华章旗下的 “智谱清言”…

【解决】idea启动spring MVC报错:一个或多个listeners启动失败Listener ClassNotFoundException

idea配置教程。tomcat调试报错Artifact :war exploded: Error during artifact deployment。 修改代码后&#xff0c;启动不生效&#xff0c;仍是旧代码。 根本原因是&#xff1a; Modules output path和Artifacts output directory不匹配 Modules output path一定要等于Ar…

JavaScript Web APIs - 06 正则表达式

Web APIs - 06 文章目录 Web APIs - 06正则表达式正则基本使用元字符边界符量词范围字符类 替换和修饰符正则插件change 事件判断是否有类 目标&#xff1a;能够利用正则表达式完成小兔鲜注册页面的表单验证&#xff0c;具备常见的表单验证能力 正则表达式综合案例阶段案例 正…

Docker harbor私有仓库部署与管理

一、搭建本地私有仓库二、Harbor私有仓库部署与管理1、Harbor概述2、Harbor的特性3、Harbor的核心组件3.1 Proxy3.2 Registry3.3 Core services3.3.1 UI&#xff08;harbor-ui&#xff09;3.3.2 WebHook3.3.3 Token 服务 3.4 Database&#xff08;harbor-db&#xff09;3.5 Log…

C++ 学习系列 -- const 关键字

C 中引入了 const 关键字&#xff0c;被 const 关键字修饰的变量其值不能修改&#xff0c;是只读的。 一 const 变量的初始化与存储 1. const 变量初始化时就需要赋初值&#xff0c;否则无法编译通过 二 const 与指针 指针常量&#xff1a; 指针所指向的值不可改变&…

Python程序化交易接口批量获取数据源码

小编举例下面是一个简单的示例代码&#xff0c;展示如何使用Python的程序化交易接口批量获取数据&#xff0c;例如开发文档参考&#xff1a;MetaTradeAPI (metatradeapi) - Gitee.com 签名 int Init(); 功能 API 初始化 参数 无 返回值 授权成功的交易账户数量 返回值 &…

一百六十六、MySQL——systemctl stop mysqld无法停止MySQL8.0服务

一、目的 为了解决MySQL的中文乱码问题&#xff0c;需要对/etc/my.cnf文件进行参数配置。 而对/etc/my.cnf文件进行配置参数之前&#xff0c;需要先停止MySQL服务 二、错误命令语句示范 &#xff08;一&#xff09;错误的命令语句 # systemctl stop mysqld &#xff08;…

C++进阶之多态

多态 多态的概念多态的定义及实现1.多态的构成条件2.虚函数3.虚函数的重写4.虚函数重写的两个例外5.C11 override 和 final6.重载、覆盖(重写)、隐藏(重定义)的对比 抽象类1.概念2.接口继承和实现继承 多态的原理1.虚函数表2.多态的原理3.动态绑定与静态绑定 单继承和多继承关系…

SQL高阶语句

目录 1、概念 1.1、概述 1.2、常见的MySQL高阶语句的概念&#xff1a; 1.3、 SQL高阶语句的作用 2、常用查询 2.1、按关键字排序 2.1.1、概述和作用 2.1.2、 &#xff08;1&#xff09;语法 2.1.3、模板表&#xff1a;ky30 ​编辑2.1.4、分数按降序排列 2.1.5、ORDER…

Kubernetes技术--使用kubeadm搭建高可用的K8s集群(贴近实际环境)

1.高可用k8s集群架构(多master) 2.安装硬件要求 一台或多台机器,操作系统 CentOS7.x-86_x64 硬件配置:2GB或更多RAM,2个CPU或更多CPU,硬盘30GB或更多 注: 这里属于教学环境,所以使用三台虚拟机模拟实现。 3.部署规划 4.部署前准备 (1).关闭防火墙 systemctl stop fi…

《Go 语言第一课》课程学习笔记(十二)

函数 Go 函数与函数声明 在 Go 语言中&#xff0c;函数是唯一一种基于特定输入&#xff0c;实现特定任务并可返回任务执行结果的代码块&#xff08;Go 语言中的方法本质上也是函数&#xff09;。在 Go 中&#xff0c;我们定义一个函数的最常用方式就是使用函数声明。 第一部…

重新理解百度智能云:写在大模型开放后的24小时

在这些回答背后共同折射出的一个现实是——大模型不再是一个单选题&#xff0c;而更是一个综合题。在这个新的时代帆船上&#xff0c;产品、服务、安全、开放等全部都需要成为必需品&#xff0c;甚至是从企业的落地层面来看&#xff0c;这些更是刚需品。 作者| 皮爷 出品|产…

在Nodejs中使用JWT进行鉴权

什么是 JSON Web Token&#xff08;JWT&#xff09;&#xff1f; JSON Web Token&#xff08;JWT&#xff09;是一种用于在web上传递信息的标准&#xff0c;它以JSON格式表示信息&#xff0c;通常用于身份验证和授权。 JWT由三个部分组成&#xff1a;Header&#xff08;头部&…

软件测试Day4|软件测试理论02

目录 6. 测试用例基础6.1 测试用例的定义6.2 测试用例要素6.3 测试用例设计和编写的作用 7. 黑盒测试用例设计方法7.1 用例设计方法分类7.2 测试数据选择7.2.1 等价类划分&#xff08;1&#xff09;等价类划分原理&#xff08;2&#xff09;确定等价类的原则&#xff08;3&…

摆动序列【贪心算法】

摆动序列 如果连续数字之间的差严格地在正数和负数之间交替&#xff0c;则数字序列称为 摆动序列 。第一个差&#xff08;如果存在的话&#xff09;可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。 class Solution {public int wiggleMaxLength(int…

zabbix安装部署

前期准备&#xff1a;安装mysql数据库和nginx 一、下载zabbix rpm -Uvh https://repo.zabbix.com/zabbix/4.4/rhel/7/x86_64/zabbix-release-4.4-1.el7.noarch.rpm yum-config-manager --enable rhel-7-server-optional-rpms yum install epel-release numactl yum install…

Spring Cloud Gateway的快速使用

环境前置搭建Nacos&#xff1a;点击跳转 Spring Cloud Gateway Docs 新建gateway网关模块 pom.xml导入依赖 <!-- 网关 --> <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-gateway</artifact…