广东门户网站建设,徐州建站模板,金湖网页设计多少钱,怎么打开google网站作者#xff1a;几冬雪来 时间#xff1a;2023年3月10日 内容#xff1a;数据结构链表OJ题目讲解 来源#xff1a;牛客网和力扣 目录
前言#xff1a; 刷题#xff1a;
1.反转链表#xff1a;
1.改变指向的解法#xff1a;
2.取头结点插入到新链表#xff1a;
… 作者几冬雪来 时间2023年3月10日 内容数据结构链表OJ题目讲解 来源牛客网和力扣 目录
前言 刷题
1.反转链表
1.改变指向的解法
2.取头结点插入到新链表
2.合并两个有序链表
1.正常尾插 2.带哨兵位尾插 3.链表分割
4.链表的回文结构
5.相交链表
结尾 前言 在上一篇博客中我们讲解了一些有关链表的OJ题目但是在刷题的过程中我们的题目并没有覆盖到方方面面有一些链表拓展出来的新的写法我们没有讲解到。因此今天我们又选取了几道题目来进行我们的讲解。 刷题 刷题是我们在学习数据结构又或者是学习语言等必不可少的过程我们通过刷题可以了解到一些不同的解题思路和方法。也可以发现不少我们写题的时候可能会犯错的地方因此刷题是一种可以提升我们解题能力的一种手段。 1.反转链表 反转链表作为数据结构链表的一道经典题目如今还在许多公司等作为面试的题目使用。
1.改变指向的解法
这道题用指针的解法来解因为要调换前后两个结点的指向因此单指针绝对是不行的起码都要是双指针。但是这道题仅仅是双指针还是不够的假设我们让第二个结点指向第一个结点这样两者的指向就交换了但是这个时候第二个结点不再指向第三个结点我们就会找不到第三个结点了。因此在这里我们还需要创建一个指针用来保存我们的第三个结点。 那我们这个程序什么时候结束呢是n3为空的时候吗并不是这个程序我们结束的标志是n2为空的时候才结束。 这里一开始先创建三个指针指向就是上面画的那种图n1指向空n2指向头结点n3指向n2的下一个结点。然后开始循环因为n2为空我们的编程结束所以循环条件也就为n2。接下来就是翻转翻转前是n1-next n2那么将其翻转后就是n2的下一个结点指向n1也就是n2-next n1。接下来n1n2n3全部向后移动一个位置然后再次循环最后返回n1指针。 运行代码后代码出现了错误根据报错提醒我们的n3 n3-next会出现空指针的问题因为代码是n2为空的时候结束当n2指向尾结点的时候n3就已经为空了。这个时候n3 n3-next会出错就很正常。因此在这里我们要给n3的执行加上一个条件。 如果n3已经为空的话我们的n3 n3-next这个代码就不用执行了。这样就能保证n3不会出现空指针的问题。再次运行代码。 当我们的链表为空的时候这个代码又出错了如果链表为空的话我们这里就没有头结点。下面的赋值多多少少都会出错因此在一开始我们就要对它是否为空进行判断。 这样我们的代码就通过了。那么下来我们就将代码放上来。 当然这个问题我们两种方法来解决。
2.取头结点插入到新链表
对于这道题我们的另一种解决方法就是取头结点然后将其插入到新链表。这种方法我们在学习数据结构链表的时候也经常用到这里我们就画图说明一下即可。 在这里我们需要创建两个指针一个指针用于插入另一个指针用于保存数组直到原链表的所有结点都插入完毕即可。 开始讲我们给原链表的头文件定义一个指针cur而后定义一个空指针作为新链表。接下来就是循环因为要结点插入有多少个结点就插入多少个这里的循环条件就为cur。然后进入循环先创建一个指针保存cur-next而后开始头插将cur-next指向空作为我们的新链表的尾结点。接下来newhead要进行更新cur也指向下一个结点。
运行代码起来看看。 用例都通过这就证明我们的代码和思路没有问题同时相比较上面那种方法取头结点插入新链表的代码量明显少了。
2.合并两个有序链表 下来就是一道新的题目了题目要求我们合并合并两个有序链表形成一个新的升序的链表然后将其返回。而我们要做的就是将两个链表的结点依次比较取小的值进行尾插。
1.正常尾插 这个就是我们的操作原理就是两个链表之间的结点进行相比较最终形成一个新的链表。下来就来看看我们的代码是怎么样的。 在这个代码一开始创建两个指针指向两个链表的头结点同时再创建两个指针作为新的链表的头结点。接下来进入循环无论哪一个指针先走我们就结束循环。然后就是判断如果cur1的值小于cur2的话我们就进行if语句。
首先对新链表是否为空进行判断如果head为空的话这里进行的操作就不是插入而是赋值操作。如果不为空则将cur1的值给tail-next然后tail结点进行更新向后走一步同时cur1也向后走一步来到它的下一个结点。如果cur2大于cur1则也是如果操作只不过将里面的cur1更换为cur2罢了。 注因为我们cur1并没有被修改因此不需要一个新指针保存下一个结点。 最后如果哪个链表先走完那就将另一个链表直接并在新链表的后面因为我们这里并没有修改原链表的值因此只要将一个结点链接到我们新链表的后面就可以了后面的结点本身就是链接到一起的。 但是我们的这个代码是存在问题的也就是空指针的问题看用例的话则是第一个指针为空的情况。如果链表为空那么我们的赋值操作就不会进行。 因此我们要在一开始对其进行判断是否为空的情况。 如果list1为空我们就返回list2反之返回list1。 修改过后我们的代码也是成功的通过了所有的用例。那么还是老规矩运行成功之后我们要将代码给放上来。 2.带哨兵位尾插
既然上面那种方法已经了解了那么接下来我们要介绍一种新方法——带哨兵位的链表操作。
在我们上边的代码中书写的时候要注意很多空指针的问题。例如两个链表一开始是否为空第一次插入新链表的时候要判断是否为空来决定是赋值操作还是插入操作。 同时哨兵位也不存放我们的有效值。 但是这里采用哨兵位的解法就没有这些问题了那么哨兵位是怎么样操作的呢? 类似这种方法一开始我们就创建一块空间使我们新创建的两个指针指向这块空间因为两个指针都存在有空间所以它们不可能为0。那么接下来我们应该怎么对我们的代码进行修改呢 这里我们就创建两个指针并让指针指向一块空间。然后将tail-next置空为链表的插入做准备。这里因为tail有指向一块空间不为空因此判断结束准备插入的时候不用再对tail是否为空进行判断。下面的进程是一样的最后因为链表是没有哨兵位的所以结束时要将创建的那块空间进行一个释放。最后返回我们新链表的头结点的位置。 最后结果也可以看出来我们的思路并没有错误。 3.链表分割 这道题是我们从牛客网中找到的题目链表分割在牛客网给出的难度是困难但是在力扣里面难度可能会变为中等不过即使这样我们依旧要解决这道题。
这道题我们依旧要创建哨兵位来求解这样子会更加方便。然后进行尾插操作小于x的尾插到一个链表中大于等于x的分装到另一个链表上去最后将两个链表相链接。 假设我们输入的为1 5 2 3 7 4 多说无益接下来我们就通过写代码来证明。 这里我们先创建四个指针两个固定指针两个移动指针。然后创建两个哨兵位的头结点给两个固定的指针。接下来把两个移动指针的下一个位置置空用于链表链接使用。紧接着创建一个指针指向原链表的头结点下来开始循环如果cur-next小于x那么我们就将其插入到小于x的链表中反之插入到大于等于的链表中又因为我们插入了新结点所以我们的lTal或者gTail需要更新往下走一步同时cur也向下走一步。最后将两个链表链接在一起并将哨兵位删除释放。 多少运行起来我们的代码就出现了问题这个代码的问题就是发生了内存超限。为什么会内存超限明明没有用到多少内存这里就出现了链表中一个经典的问题——环问题。 这里可以看见我们的链表链接后最后一个结点指向的并不是空而是3这是因为我们这里插入方法采取的是尾插不改变本次插入的next指向只是改变上一个结点的next指向。
因此在最后将其链接后最后一个结点的next置空即可。 这里不知道为什么没有通过我也不知道哪里错了。但是思路应该是没问题的。 4.链表的回文结构 那么什么是链表的回文呢简单来说就是链表的对称。 那么我们该怎么解决这道题呢这道题也有一种很简单的方法。 1.找到中间结点 2.从中间结点开始对后半段进行逆置 3.前半段和后半段进行比较 这就是我们这道题的解决思路。这里有人就要问了偶数逆置看得懂但是奇数的链表逆置后变为了1 2 1 2 3是不一样的怎么可能成立但是其实这个地方即使是逆置了前一个2的next的指向依旧指向3并没有被修改。
那么我们该怎么书写我们的代码呢这里我们可以偷个懒从我们往期博客中将反转链表和链表的中间结点两道题目的代码复制过来使用。 一开始我们就使用反转链表和链表的中间结点题目的代码分别求出中间结点并且将中间结点后面的所有结点进行逆置操作并将中间结点的位置设计为一个新的头结点。然后进行判断在headrhead中如果二者中有一个不相等我们就返回false相反如果相同的话我们的两个头结点就往后走一步。如果循环结束了我们的head依旧等于rhead这个时候返回true就可以了。 最后通过测试也是可以看出我们的代码并没有什么问题。那么我们这道题目也就成功解决了接下来就是另一道题目了。
5.相交链表 在数学中我们经常遇到函数相交的情况。 两条函数相交与一个点那么我们可以说这两条函数相交这个相交的地方也被我们称为交点。那么我们的相交链表也是这样的吗如果这样想那就大错特错了。 这种理解是错误的因为当我们链表相交之后它们会交于一个共同的结点而这个结点只有一个next它只会指向下一个结点并不会指向两个不同的结点。
那我们要怎么判定两个链表相交了呢 这里我们通过判定尾结点的地址来看看两个链表有没有相交。如果两个链表的尾结点的地址相同那么它们就是相交的如果不同那就不相交。 注判断的是尾结点的地址而不是尾结点的值。 但是如果这个样子那么我们要怎么样找到交点有人说找到a2和b3的next即可但是这里我们又怎么确定a2和b3在哪里 那么这里最简单粗暴的就是直接暴力比较。拿a1与b1~c3相比较如果都不相等那么就拿a2和b1~c3再次相比。但是如果是这种方法的话我们的时间复杂度就为ON^2它就是一个很大的值了。
如果题目有给我们一个限制要求我们的时间复杂度为O(N)空间复杂度为1,那这道题我们又应该怎么办解。 那说到这里我们就动手写代码吧。 这里一开始我们就创建两个指针来存放两个链表的头结点并定义两个变量赋值为1。然后就是循环判断先找两个链表的尾结点并且lenA和lenB都要移动为了后面比较长短做准备如果尾结点不同我们就直接返回空。如果相等的话我们就创建一个变量来存放差距步的多少因为这里不知道两个链表哪个比较长因此在这之后还要再创建两个指针指向我们的头结点一开始我们就直接先假设A链表比B链表长然后判断要是链表A没有链表B长我们就将两个值调换。
接下来我们的长链表就要先走差距步gap就是差距步的个数。当差距步走完后我们就开始判断如果longList不等于shortList说明二者并没有指向同一个地址这里的两个结点就要同时向后走一步如果找到了就直接返回指针的地址。 最后我们这个代码也是通过了用例。
结尾 本次我们链表OJ的题目也就到这里结束了在这篇博客中又学习到了不少新知识——哨兵位的头结点但是还是有一些链表的题目我们并没有讲到例如后面的链表环形结构等。不过这些题目也并不简单后面要熟悉链表的得认真反复的去学习。最后希望这一篇链表OJ题目的讲解可以为各位带来帮助让大家更了解链表知识。
