单链表经典oj题(2)

前言

这次将要把剩下的oj题将以图解和自己的理解把它讲解完,希望对大家有所帮助,这次的讲解也是干货

第一题

21. 合并两个有序链表 - 力扣(LeetCode)

ok这次就简单点,大家自己去看题目了

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

暴力思路

想想看不考虑空间和时间的消耗,什么代码最容易想

两个链表,可不可以直接把两个链表的值放在一个数组中

然后再排序,当然这里的链表大小是有序的,放在数组中时

可以判断大小,从而不用去排序

再根据数组自行去malloc一个链表,是不是非常暴力的思路

这个暴力代码其实也很重要,至少是算法小白入门的绝招

#include<stdio.h>
#include<stdlib.h>
typedef struct SlistNode {struct SlistNode* next;int val;
}SLNode,*SL;
SLNode* Buyslistnode(int data)
{SL newnode = (SL)malloc(sizeof(SLNode));newnode->next = NULL;newnode->val = data;return newnode;
}
SL initlist1()
{SL list1 = (SL)malloc(sizeof(SLNode));list1->val = 1;list1->next = Buyslistnode(2);list1->next->next = Buyslistnode(4);return list1;
}
SL initlist2()
{SL list2 = (SL)malloc(sizeof(SLNode));list2->val = 1;list2->next = Buyslistnode(3);list2->next->next = Buyslistnode(4);return list2;
}
int cmp(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}
void text1()
{//我们这里直接考虑list1与list2都不是空链表的情况//其实其他的情况可以通过if判断排除//初始化题目//list1   1->2->4//list2   1->3->4SL list1 = initlist1();SL list2 = initlist2();//题目中链表的结点数是0~50//所以直接可以用静态数组int newarr[110];int size = 0;while (list1){newarr[size++] = list1->val;list1 = list1->next;}while (list2){newarr[size++] = list2->val;list2 = list2->next;}qsort(newarr, size, sizeof(int), cmp);SL phead = (SL)malloc(sizeof(SLNode));SL cur = phead;for (int i = 0; i < size; i++){cur->next = Buyslistnode(newarr[i]);cur = cur->next;}//至此已经完成//打印看结果吧cur = phead->next;while (cur){printf("%d ", cur->val);cur = cur->next;}
}
int main()
{text1();return 0;
}

那么看结果

OK接下来看看优化的思路 头结点+双头插

对于这个例子

我们一第二条链表为基础对他进行插入操作

我们使用两个指针,分别指向两条链表的第一个位置cur1 cur2

如果第一个链表的值小于第二个链表的值那么尾插到此时第二个链表指针的前面

cur1->val<=cur2->val      

并且让第一个指针cur1=cur1->next;

当然这里只是大题思路不是代码

如果大于 cur1->val>cur2->val   

那么让cur2=cur2->next

在进行操作的时候,我们为了避免在第一个位置插入 ,从而加入了头指针

OK,看代码呗

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1==NULL&&list2==NULL)return list1;else if(list1!=NULL&&list2==NULL)return list1;else if(list1==NULL&&list2!=NULL)return list2;struct ListNode*p1=list1;struct ListNode*p2=list2;struct ListNode*p2head=(struct ListNode*)malloc(sizeof(struct ListNode));p2head->next=p2;struct ListNode*front=p2head;while(p1&&p2){if(p1->val<=p2->val){//双指针中间插入//front->next=p1;struct ListNode*temp=p1;p1=p1->next;temp->next=p2;front=temp;}else{front=p2;p2=p2->next;}}//如果p2==null此时p1不为空,把p1接起来if(p2==NULL)front->next=p1;return p2head->next;}

 第二题

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

链表分割_牛客题霸_牛客网 (nowcoder.com)

ok

这个题目其实也可以暴力

但是

已经写了好多次暴力了,对吧

这一次可以说说思路

仍然可以使用数组,然后直接排序,不管x为多少,按从小到大的顺序,没有错

然后构建链表,这个题目就完了

挺暴力的吧

可以的

但是这个代码和之前大差不差

直接来看具体的思路

我们可以把一个链表分成两个链表,list1一个是大于等于x的,list2一个是小于x的

最后让list2连接list1

就完成任务了

思路看起来简单但是细节还是很多

我们在代码中有注释

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {if(pHead==NULL&&pHead->next==NULL)return pHead;auto *head=(ListNode*)malloc(sizeof(ListNode));head->next=pHead;//头结点ListNode*front=head;ListNode*newlist=NULL;ListNode*newtail=NULL;ListNode*p=pHead;while(p){if(p->val<x){//在原有的链表上去除小于x的值ListNode*temp=p;p=p->next;temp->next=NULL;front->next=p;//对新的链表操作//小于x的值重新连成一个链表if(newlist==NULL){newlist=newtail=temp;}else{newtail->next=temp;newtail=temp;}}else {front=p;p=p->next;  }}//不要忘了呀,新的链表有可能为空呀,哎呦,搞了个半天if(newtail==NULL)return pHead;elsenewtail->next=head->next;return newlist;}
};

这个题目思路还是不难,继续努力

第三题

链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

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

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

1->2->2->1
返回:true

这个题目有难度了

所以我们可以通过画图来理解一下

思路,

我们可以找到中间的结点,把中间的结点逆置过来

然后一个指针从中间

另一个指针从开头

一直判断他们是否相等,就可以得到答案

看图呗

 OK,找中以及逆转链表之前已经有过讲解了

单链表的经典oj题(1)-CSDN博客

好吧,不懂可以去看

我们现在直接去看代码喽

 ListNode*middle(ListNode*A){ListNode*slow=A;ListNode*fast=A;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow;}ListNode* revearse(ListNode*src){ListNode* cur=src;ListNode* prev=NULL;while(cur){ListNode* temp=cur->next;cur->next=prev;prev=cur;cur=temp;}return prev;}bool chkPalindrome(ListNode* A) {// write code hereListNode*cur=middle(A);ListNode* tail=revearse(cur);while(A&&tail){if(tail->val!=A->val)return false;tail=tail->next;A=A->next;}return true;}

第四题

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

题目在这里

160. 相交链表 - 力扣(LeetCode)

OK

思路

 首先要判断他们是否是有相交节点

OK可以让他们走到最后一个节点

如果他们的最后一个节点相等,那他们就有相交节点,那么问题来了

怎么找到节点呢

要是知道两个链表的长度,再利用相对位移让他们距离相交节点的位移一样

最后让他们同时走,再判断,直到相等即可

OK

看代码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode*A =headA;struct ListNode*B =headB;//这里最后一个节点没有加上,所以初始为1int sizeA=1;int sizeB=1;while(A->next){A=A->next;sizeA++;}while(B->next){B=B->next;sizeB++;}if(A!=B)return NULL;//通过假设,来简化代码//总之就是让A最长if(sizeA<sizeB){A=headB;B=headA;}else{A=headA;B=headB;}int abs=sizeA-sizeB>0?sizeA-sizeB:sizeB-sizeA;//使他们里相交点的距离相等while(abs--){A=A->next;}while(A!=B){A=A->next;B=B->next;}return B;
}

第五题 

 141. 环形链表 - 力扣(LeetCode)

题目

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

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

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

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点

OK

这个题目的思路很重要,我这里有两种做法

暴力求解

如果只要求求出题目,那么我们可不可以用一个数据来标明这个节点走过没有

  • -10^5 <= Node.val <= 10^5

当我们走过一个结点

直接给他加上一个10^6+10

+10是防止特殊情况,那么只要遍历一遍,走到某个节点,如果它大于

10^5证明我们走过这里,但是此时又回到了这里,此时可以判断为有环

缺点是破坏了链表

bool hasCycle(struct ListNode *head) {while(head){if(head->val>1e5)return true;else{head->val+=1e6+10;}head=head->next;}return false;
}

这种办法还是挺有意思的不是吗?

OK

来看看不改变链表的结构的写法吧

这个还是要画图理解,并且这里还是涉及到了相对位置的概念

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

话不多说下一题

第六题

142. 环形链表 II - 力扣(LeetCode)

 这个题目,是上个题目的升级版

OK看题

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

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

不允许修改 链表。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

思路

大家看这里就是不允许修改链表了

这该如何是好

还是画图吧

这个题目更是一个物理的模型

OK,看代码吧

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode*slow=head;struct ListNode*fast=head;struct ListNode*meet=NULL;struct ListNode*find=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){meet=slow;break;}}if(meet==NULL)return NULL;while(find!=meet){find=find->next;meet=meet->next;}return find;
}

总结

今天的题还是挺多的,好好练吧

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

流量分析(一)

数据库类流量分析 MySQL流量 常规操作&#xff0c;查找flag ctfhub{} 注意要选择字符集 Redis流量 查找ctfhub结果没找到 尝试把其变成十六进制继续进行查找 看到了前半段flag 接着往下看 找到了后半段的flag MongoDB流量 还是一样查找ctfhub 字符串没找到 转成十六进制也没…

《软件方法(下)》8.3.2.2 警惕拼凑泛化(202405更新)

DDD领域驱动设计批评文集 做强化自测题获得“软件方法建模师”称号 《软件方法》各章合集 8.3 建模步骤C-2 识别类的关系 8.3.2 识别泛化关系 8.3.2.1 识别泛化的思路 &#xff08;3&#xff09;自上而下&#xff08;从一般到特殊&#xff09; 如图8-92所示&#xff0c;这…

目标检测——道路检测数据集

引言 亲爱的读者们&#xff0c;您是否在寻找某个特定的数据集&#xff0c;用于研究或项目实践&#xff1f;欢迎您在评论区留言&#xff0c;或者通过公众号私信告诉我&#xff0c;您想要的数据集的类型主题。小编会竭尽全力为您寻找&#xff0c;并在找到后第一时间与您分享。 …

鹦鹉优化算法原理及代码实现

鹦鹉(Pyrrhura Molinae)表现出四种不同的行为特征&#xff1a;觅食、停留、交流和对陌生人的恐惧。这些行为(如图1所示)在现实环境中构成了我们设计PO动机的基础。 觅食&#xff1a;驯化的鹦鹉(Pyrrhura Molinae)的觅食行为令人着迷&#xff0c;因为个体选择在食物丰富的小群体…

第十三届蓝桥杯决赛(国赛)真题 Java A 组【原卷】

文章目录 发现宝藏【考生须知】试题 A: 火柴棒数字试题 B: 小蓝与钥匙试题 C: 内存空间试题 D: 斐波那契数组试题 E: 交通信号试题 F: 数组个数试题 G: 六六大顺试题 H : \mathrm{H}: H: 选素数试题 I: 图书借阅试题 J \mathrm{J} J : 括号序列树 发现宝藏 前些天发现了一个…

Web服务器--虚拟主机配置

实验1&#xff1a;建立两个基于ip地址访问的网站&#xff0c;要求如下 该网站ip地址的主机位为100&#xff0c;设置DocumentRoot为/www/ip/100&#xff0c;网页内容为&#xff1a;this is 100。 该网站ip地址主机位为200&#xff0c;设置DocumentRoot为/www/ip/200&#xff0c…

数据结构--顺序表和链表的区别

顺序表和链表之间各有优劣&#xff0c;我们不能以偏概全&#xff0c;所以我们在使用时要关注任务的注重点&#xff0c;以此来确定我们要使用两者中的哪一个。 不同点&#xff1a; 存储空间上&#xff1a; 顺序表在物理结构上是一定连续的&#xff0c;而链表(这里以带头双向循环…

凸优化理论学习一|最优化及凸集的基本概念

文章目录 一、优化问题&#xff08;一&#xff09;数学优化&#xff08;二&#xff09;凸优化 二、凸集&#xff08;一&#xff09;一些标准凸集&#xff08;二&#xff09;保留凸性的运算&#xff08;三&#xff09;正常锥和广义不等式&#xff08;四&#xff09;分离和支撑超…

网络基础-ICMP协议

ICMP&#xff08;Internet Control Message Protocol&#xff0c; Internet控制消息协议&#xff09; ICMP协议是IP协议的辅助协议&#xff0c;用于在IP网络上发送控制消息&#xff0c;它通常被用于诊断网络故障、执行网络管理任务以及提供一些错误报告&#xff1b;对于收集各…

彩虹聚合DNS管理系统

聚合DNS管理系统可以实现在一个网站内管理多个平台的域名解析&#xff0c;目前已支持的域名平台有&#xff1a;阿里云、腾讯云、华为云、西部数码、CloudFlare。本系统支持多用户&#xff0c;每个用户可分配不同的域名解析权限&#xff1b;支持API接口&#xff0c;支持获取域名…

MySQL的表级锁

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;面经 ⛺️稳中求进&#xff0c;晒太阳 表级锁 介绍 对于表锁&#xff0c;分为两类&#xff1a; 表共享读锁表独占写锁 语法 1. 加锁&#xff1a;lock tables 表名... read/write 2.…

PHP 提取数组中的特定的值

需求&#xff1a; 前端展示&#xff1a; &#xff08;1&#xff09;之前的页面&#xff1a; &#xff08;2&#xff09;修改后的页面&#xff1a; 之前接口返回的数据 &#xff1a; 解决办法&#xff1a;提取tags 中的 ’约 的数组 添加到一个新的数组中去 1&#xff1a;一开…

CSAPP笔记——第一章计算机系统漫游

hello&#xff0c;你好鸭&#xff0c;我是Ethan&#xff0c;很高兴你能来阅读&#xff0c;昵称是希望自己能不断精进&#xff0c;向着优秀程序员前行!&#x1f4aa;&#x1f4aa;&#x1f4aa; 目前博客主要更新Java系列、项目案例、计算机必学四件套等。✔️✔️✔️ 人生之败…

OpenCV中的模块:点云配准

点云配准是点云相关的经典应用之一。配准的目的是估计两个点云之间位姿关系从而完成两者对应点之间的对齐/对应,因而在英文中又叫“align”、“correspondence”。笔者曾经是基于OpenCV进行三维重建的,并且从事过基于深度学习的6DoF位置估计等工作。在这些工作中,除了重建点…

深度学习课程论文精读——ESRGAN

目录 1.研究概述 2.论文创新 2.1 改进生成器的网络框架 2.2 改进判别器 2.3 改进感知损失 2.4 网络插值 3.实验 3.1 评价指标 3.2 训练细节 3.3 对比实验 3.4 消融实验 3.5 网络插值 4.总结 5.阅读参考 文章标题&#xff1a;《ESRGAN: Enhanced Super-Resolution…

SDXL-ControlNet模型MistoLine:引领高精度图像生成的革新高质量图像模型

在数字艺术的浩瀚星空中&#xff0c;MistoLine犹如一颗璀璨的新星&#xff0c;以其对SDXL-ControlNet技术的深度整合&#xff0c;展示了对多种线稿类型的非凡适应能力&#xff0c;并在高精度图像生成领域树立了新的标杆。 GitHub&#xff1a;https://github.com/TheMistoAI/Mi…

Web实时通信的学习之旅:轮询、WebSocket、SSE的区别以及优缺点

文章目录 一、通信机制1、轮询1.1、短轮询1.2、长轮询 2、Websocket3、Server-Sent Events 二、区别1、连接方式2、协议3、兼容性4、安全性5、优缺点5.1、WebSocket 的优点&#xff1a;5.2、WebSocket 的缺点&#xff1a;5.3、SSE 的优点&#xff1a;5.4、SSE 的缺点&#xff1…

代码随想录day62 | 单调栈P2 | ● 503. ● 42.

终于来到了大名鼎鼎的接雨水, 舍友的23年暑期面试就是接雨水 XD 503.下一个更大元素II 给定一个循环数组 nums &#xff08; nums[nums.length - 1] 的下一个元素是 nums[0] &#xff09;&#xff0c;返回 nums 中每个元素的 下一个更大元素 。 数字 x 的 下一个更大的元素 是…

ArcGIS如何计算地级市间的距离

一、数据准备 加载配套实验数据包中的地级市和行政区划矢量数据(订阅专栏后,从私信查收数据),如下图所示: 二、计算距离 1. 计算邻近表 ArcGIS提供了计算点和另外点之间距离的工具:分析工具→邻域分析→生成临近表。 计算一个或多个要素类或图层中的要素间距离和其他邻…

C++ | Leetcode C++题解之第79题单词搜索

题目&#xff1a; 题解&#xff1a; class Solution { public:bool exist(vector<vector<char>>& board, string word) {rows board.size();cols board[0].size();for(int i 0; i < rows; i) {for(int j 0; j < cols; j) {if (dfs(board, word, i, …