数据结构刷题训练——链表篇(二)

目录

前言

1.题目一:链表分割

1.1 思路

1.2 分析

 1.3 题解

2. 题目二:相交链表

2.1 思路

2.2 分析

2.3 题解

3. 题目三:环形链表

3.1 思路

3.2 分析

3.3 题解

总结


前言

        本期继续分享链表相关的OJ题目,在这个专栏博客中,我们将提供丰富的题目资源和解题思路,帮助读者逐步提高解题能力。同时,我们也将分享一些刷题技巧和经验,帮助读者更加高效地进行刷题训练。通过持之以恒的努力和不断的实践,相信读者可以在数据结构领域取得长足的进步。


1.题目一:链表分割

题目描述:

 题目链接:

链表分割icon-default.png?t=N6B9https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

1.1 思路

        这道题目没有示例,这也是这道题的难点之一,我们只根据题意自己寻找示例,进行分析。题目的意思是说,给一个链表,给一个x值,把小于x的插入到x前边,大于x的插入到x的后边,且不可以打乱原链表中的次序(链表中的数据大小为乱序)。理解了题意,大家可以先自己思考一下解题思路。

        对于这道题的要求我们可以这样做:遍历原链表,将大于等于x的尾插到一个新链表,小于x的尾插到一个新链表,最后将两个链表合并。

1.2 分析

        这道题思路虽然非常简单,但是在实际编写代码时会有很多的坑。例如要考虑链表为NULL的情况,如果原链表中的所有值都大于x或小于x那就会造成两个链表中,其中一个链表为NULL。

 假设原链表为:

 x值为3,那我们就可以把原链表分割成以下两个链表:

         这道题目有两种方法,一种是使用带头节点的链表,一种是使用不带头节点的链表。对于链表掌握不熟悉的,本人推荐使用带头节点的链表,当然带头节点的链表对于这道题也可以简化代码。如果没有带头节点,那我们在初始化后尾插时就需要进行特殊处理。相对比较麻烦,所有我们这里推荐使用带头链表。

        如果带头结点两链表就是这样的:

 将两个链表合并时也不需要特殊处理可以直接连接,如下图:

 不用担心头节点怎么办,两个头节点最后会被销毁,销毁之后就是我们所需要的链表了。

         就算是第一个链表为空,也可以搞定:

         连接的时候也不需要特殊处理,最后销毁两个头节点即可。

 1.3 题解

根据分析的思路,我们对代码进行编写:

ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* head1,*head2,*tail1,*tail2;
        head1=tail1=(struct ListNode*)malloc(sizeof(struct ListNode));//创建两个头节点
        head2=tail2=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur=pHead;    
        while(cur)                    //遍历原链表
        {
            if(cur->val < x)          //小于x就尾插到链表1
            {
                tail1->next=cur;
                tail1=tail1->next;
            }
            else                      //大于等于x就尾插到链表2
            {
                tail2->next=cur;
                tail2=tail2->next;
            }
            cur=cur->next;            
        }
        tail1->next=head2->next;      //将两个链表合并
        tail2->next=NULL;

        struct ListNode* head=head1->next;
        free(head1);
        free(head2);
        return head;                  //最后返回链表1的第一个节点
    }

2. 题目二:相交链表

题目描述:

 示例:

 题目链接:

相交链表icon-default.png?t=N6B9https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

2.1 思路

        这道题目的解题思路就简单了,但要注意链表长度不同的情况。当两个节点的节点个数不相同时,指向长链表的指针要先走它们节点个数的差值步。然后开始一一对比,直到遇到相交节点为止。

2.2 分析

        链表相交并不是像直线那样交叉相交,单链表中,一个节点只能指向一个节点,所有这里的链表相交是如下图的情况:

 总体分 3 步:

  • 先遍历两个链表得到两个链表的长度。
  • 长的链表先走差距步(len1-len2)。
  • 开始遍历两个数组,直到相交点,返回相交的节点

2.3 题解

整理完思路后,根据分析的思路进行编写代码:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* curA=headA,*curB=headB;
    int lenA=1,lenB=1;
    while(curA->next)
    {
        curA=curA->next;
        lenA++;
    }
    while(curB->next)
    {
        curB=curB->next;
        lenB++;
    }
    if(curA!=curB)        //如果遍历到最后两个链表的尾节点不是同一个节点就说明不相交。
    {
        return NULL;
    }
    int t= abs(lenA-lenB);//求出差距步  abs是求绝对值的函数
    struct ListNode* longlist=headA, *shortlist=headB;
    if(lenB>lenA)           //这里先假设链表A长,如果不是链表A长就交换一下,简化代码
    {
        longlist=headB;
        shortlist=headA;
    }
    while(t--)              //长的链表走差距步
    {
        longlist=longlist->next;
    }
    while(longlist!=shortlist)//两链表同时遍历
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;          //循环停止时指向的节点就是第一个相交节点,返回它们两个任意一个
}

3. 题目三:环形链表

题目描述:

 示例:

 题目链接:

环形链表icon-default.png?t=N6B9https://leetcode.cn/problems/linked-list-cycle/description/

3.1 思路

         我们知道循环链表,循环链表的尾指向链表的头,遍历一遍之后会回到链表的头,但这道题属于带环链表,带环链表的尾不一定连接着头,它可能连接着任意节点。带环链表的题目属于链表中较为复杂的题目,那要如何判断一个链表是否带环呢?

        首先我们知道,带环链表在向后遍历的时候,一定会回到入环点,比较链表中的节点是否为入环时的节点就可以了,但是问题来了,我们怎么知道哪个是开始入环的节点?不知道入环的节点又怎么比较是否是同一个节点。显然传统的思路行不通,那我们就来换一种方法。

        这里我们就可以使用快慢指针的方法,一个指针走的快一个指针走的慢,当快的指针再次与慢指针相遇,那就说明这个链表一定是带环链表。

3.2 分析

        带环链表的入环节点可能是任意节点:

         它也可以指向它自己。

        这里我们可以使用快慢指针的方法,使用快指针来追击慢指针,当快指针与慢指针再次相遇,这就说明这个链表一定为带环链表,但是如果快指针走到了NULL,这就说明这个链表不是带环链表。

3.3 题解

 根据分析的思路,我们整理一下,形成代码:

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

         题解也是非常简单。对于带环链表,今天这道题目属于热身,下期我会专门出一期带环链表的题目。


 

总结

        最后,感谢你的阅读和支持。希望你在这个数据结构的学习旅程中能够获得满满的收获和成就感。愿我们共同努力,不断探索和挑战,成为数据结构领域的行家里手!

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

《Linux从练气到飞升》No.11 初识操作系统

&#x1f57a;作者&#xff1a; 主页 我的专栏C语言从0到1探秘C数据结构从0到1探秘Linux菜鸟刷题集 &#x1f618;欢迎关注&#xff1a;&#x1f44d;点赞&#x1f64c;收藏✍️留言 &#x1f3c7;码字不易&#xff0c;你的&#x1f44d;点赞&#x1f64c;收藏❤️关注对我真的…

Python实现调用百度翻译的API

import requests import hashlib import random import jsondef translate(text, from_lang, to_lang):app_id XXXXX # 替换为你的App IDsecret_key XXXXX # 替换为你的Secret Key# 生成随机数salt random.randint(32768, 65536)# 计算签名sign app_id text str(salt) …

vue的proxy代理详解

一、proxy常用参数说明 module.exports {publicPath: "/",devServer: {proxy: {"/api": {// 代理名称 凡是使用/api开头的地址都是用此代理target: "http://1.2.3.4:5000/", // 需要代理访问的api地址changeOrigin: true, // 允许跨域请求pa…

【云原生】K8S集群

目录 一、调度约束1.1 POT的创建过程1.1调度过程 二、指定节点调度2.1 通过标签选择节点 三、亲和性3.1requiredDuringSchedulingIgnoredDuringExecution&#xff1a;硬策略3.1 preferredDuringSchedulingIgnoredDuringExecution&#xff1a;软策略3.3Pod亲和性与反亲和性3.4使…

---------------- 部署 Zookeeper 集群 ----------------

部署 Zookeeper 集群 1.安装前准备2.安装 Zookeeper修改配置文件在每个节点上创建数据目录和日志目录在每个节点的dataDir指定的目录下创建一个 myid 的文件配置 Zookeeper 启动脚本 //准备 3 台服务器做 Zookeeper 集群 192.168.109.1 192.168.109.2 192.168.109.3 1.安装前准…

Zorin OS 16.3 发布:无缝升级和卓越改进!

导读Zorin OS 团队自豪地宣布了备受期待的 Zorin OS 16.3 版本的发布&#xff0c;这是这个受欢迎的 Linux 发行版的一个里程碑版本。自首次发布以来不到两年时间&#xff0c;Zorin OS 已经获得了庞大的用户群体&#xff0c;截至目前已经有 530 万次下载&#xff0c;而 16.3 版本…

QGIS二次开发六:VS不借助QT插件创建UI界面

上一篇博客我们说了在VS中如何使用QT插件来创建UI界面&#xff0c;但是我们二次开发QGIS的第一篇博客就说了&#xff0c;最好使用OSGeo4W中自动下载的QT进行QGIS二次开发&#xff0c;这样兼容性是最好的&#xff0c;那么该如何在VS中不使用外部安装的QT以及QT的VS插件情况下进行…

B树的插入与删除过程

B树的插入 原树&#xff1a; 插入key后&#xff0c;若导致原节点关键字数超过上限&#xff0c;则从中间位置&#xff08; ⌈ m 2 ⌉ \lceil\frac{m}{2}\rceil ⌈2m​⌉&#xff09;将关键字分成两部分&#xff0c;左部分包含的关键字放在原节点中&#xff0c;右部分包含的关键…

应用程序运行报错:First section must be [net] or [network]:No such file or directory

应用程序报错环境&#xff1a; 在linux下&#xff0c;调用darknet训练的模型&#xff0c;报错&#xff1a;First section must be [net] or [network]:No such file or directory&#xff0c;并提示&#xff1a;"./src/utils.c:256: error: Assertion 0 failed." 如…

YOLOv5-7.0实例分割+TensorRT部署

一&#xff1a;介绍 将YOLOv5结合分割任务并进行TensorRT部署&#xff0c;是一项既具有挑战性又令人兴奋的任务。分割&#xff08;Segmentation&#xff09;任务要求模型不仅能够检测出目标的存在&#xff0c;还要精确地理解目标的边界和轮廓&#xff0c;为每个像素分配相应的…

Echarts 让饼图中间文字居中并自适应图表

背景&#xff1a; 产品提出需求在饼图中间放两行文字且居中 “简单&#xff0c;劈劈啪啪写完了” 产品再提出你这个没有自适应啊&#xff0c;屏幕放大、缩小你这个就没有居中了&#xff0c;甚至会和饼图重叠 “emmmmm…" UI图如下&#xff1a; 方案一&#xff1a;使用ti…

Arduino 项目笔记 | Arduino LED Memory Game 颜色记忆游戏机

成果展示 颜色记忆游戏机 &#xff5c; Arduino DIY 1. 线路链连接 1.1 原理图 1.2 PCB 免费PCB打样 Arduino LED Memory Game 颜色记忆机资料下载 1.3 烧录 Bootloader 第二部分&#xff1a;Burn bootloader 2. 程序实现 #define NOTE_B0 31 #define NOTE_C1 33 #define NOT…

3.正则表达式

3.1什么是正则表达式 ●正则表达式( Regular Expression) 是用于匹配字符串中字符组合的模式。在JavaScript中&#xff0c; 正则表达式也是对象 ●通常用来查找、替换那些符合正则表达式的文本&#xff0c;许多语言都支持正则表达式 ●正则表达式在JavaScript中的使用场景: ➢…

赛码网-triangle(dp) 100%AC代码(C)

———————————————————————————————————— ⏩ 大家好哇&#xff01;我是小光&#xff0c;嵌入式爱好者&#xff0c;一个想要成为系统架构师的大三学生。 ⏩最近在准备秋招&#xff0c;一直在练习编程。 ⏩本篇文章对赛码网的01串的魔法 题目做…

竞赛项目 深度学习图像风格迁移

文章目录 0 前言1 VGG网络2 风格迁移3 内容损失4 风格损失5 主代码实现6 迁移模型实现7 效果展示8 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 深度学习图像风格迁移 - opencv python 该项目较为新颖&#xff0c;适合作为竞赛课题…

viewerjs 如何新增下载图片功能(npm包补丁)

文章目录 先实现正常的效果实现下载图片改变viewerjs的build函数源码改变之后&#xff0c;执行npm i 之后node_modules源码又变回了原样 1、viwerjs所有功能都很完善&#xff0c;但唯独缺少了图片的下载 2、需求&#xff1a;在用viwerjs旋转图片后&#xff0c;可以直接下载旋转…

【类和对象】收尾总结

目录 一、初始化列表 1.格式要求 (1) 初始化列表初始化 ①括号中是初始值 ②括号中是表达式 (2) 初始化列表和函数体混用 2.特点 ①初始化时先走初始化列表&#xff0c;再走函数体 ②拷贝构造函数属于特殊的构造函数&#xff0c;函数内也可以使用初始化列表进行初始化 …

【c语言】指针进阶(超详细)

文章目录 ✈ 指向函数指针数组的指针&#x1f4cc;指向函数指针数组的指针的定义&#x1f4cc;指向函数指针数组的数组指针的使用 ✈回调函数&#x1f4cc; 回调函数的定义&#x1f4cc; 回调函数的使用 ✈qsort函数&#x1f4cc; qsort函数的作用&#x1f4cc;qsort函数的定义…

Rikka with Square Numbers 2023“钉耙编程”中国大学生算法设计超级联赛(8)hdu7370

Problem - 7370 题目大意&#xff1a;给出两个数a&#xff0c;b&#xff0c;每次操作可以使其中一个数加上或减去一个任意的完全平方数&#xff0c;问要使a&#xff0c;b相等需要的最少操作次数是多少 1<a,b<1e9,a!b 思路&#xff1a;我们可以将问题转化为将a和b的差w…

最强的表格组件—AG Grid使用以及License Key Crack

PS: 想要官方 License Key翻到最后面 Ag Grid简介 Ag-Grid 是一个高级数据网格&#xff0c;适用于JavaScript/TypeScript应用程序&#xff0c;可以使用React、Angular和Vue等流行框架进行集成。它是一种功能强大、灵活且具有高度可定制性的表格解决方案&#xff0c;提供了丰富…