少年也识愁滋味,写作码文挠破头。
前言:期末考试临近,博主也在备战期末,自上篇链表oj面试题博客的发布后,近一个月没有新文出炉了,博主跟小伙伴们一样都在好好复习呢!!不知道诸位小伙伴考的如何,在这里博主给大家伙拜个早年啦!同时也很感谢各位小伙伴们的支持!!新年新气象,2024一起加油吧!!!
目录
1. 链表分割
1)代码实现
2. 链表的回文结构
2)代码实现
3.相交链表
3)代码实现
4.环形链表
4)代码实现
1. 链表分割
题目:编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前
首先这有个链表,题目没有说是有序的,所以我们以乱序的链表为例:
假设x = 30,那么根据题意(所有小于x的结点排在大于或等于x的结点之前),最后链表的效果如下:
我们来看看力扣的题目描述:现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
题目分析:他要求我们不能改变原来的数据顺序,我们看最上面那张图,在x = 30的情况下,23和12同时小于30,但是23在12的前面,所以在效果图里,23还是在12之前,大于30的部分,也保持了45、34、56的顺序,他们的相对顺序没有改变。最后让我们返回一个排列后的链表的头指针,说明让我们返回一个新的链表
解题思路:这题将链表分割成两部分,一部分小于x,一部分大于等于x,我们可以在这两条链表的头尾都加上一个标记,如下图所示:
当我们把小于x的放到了左边的链表,大于等于x的都放到了右边的链表,我们再把 be 和 as 连接起来,然后返回bs,是不是就解决了?
我们可以定义一个cur来遍历我们的链表,如果cur小于x,就放左边那个小链表,如果cur大于等于x,就放右边那个小链表,如下图:
注意:我们要保持顺序相同,所以23一定要在12前面,45一定要在34、56前面,所以我们应该用尾插法来实现
当我们尾插各小链表的第一个数时,这个数既是各个小链表的头,又是各个小链表的尾,所以我们把bs和be,as和ae同时放到各自的数下面,为什么这么做呢?如果我们不把be和ae放到这里,那么我们在插第二个数的时候怎么找到这条链表的尾部进行尾插呢?如上图:
当我们进行尾插时候,就不需要遍历链表了,因为我们的be永远指向第一条链表的最后一个节点,所以我们可以直接让be.next = cur; 然后让 be 往后走 ,如下图:
当我们重复尾插完后,让 be.next = as ; 然后返回 bs 即可解决题目,如下图:
这题还需要考虑几个特殊的点:
1.pHead是否为空?也就是说给的链表是不是空表
2.能确定一定存在小于x的值或者大于等于x的值吗?也就是说不一定存在两个小链表都存在的情况,如果没有小于x的值,我们最后让两个小链表合并,就会发生空指针异常
所以我们先要判断链表是否为空
if(pHead == null) {return null;}
第二个问题,我们只需要在最后合并链表时候添加一个If判断就可以了
if(bs == null) {
return as;
}
be.next =as;
这样就解决问题了吗?其实还有个非常隐形的问题:假设最后一个数字为6,如下图:
那么我们尾插完后应该如下图:
这个时候再通过下面这段代码:
if(bs == null) {
return as;
}
be.next =as;
最后结果就如下图:
你就发现问题了,我们的尾节点不是为null,力扣网无法校验答案,所以在第二个小链表有数据时应该分为两种情况:
1.ae == null;
2.ae != null;
所以我们需要添加一个判断:
if(as != null) {
ae.next = null;
}
这样不管ae是否为空,我们都手动置为空,就可以解决这个问题。
1)代码实现
public class Partition {
public ListNode partition(ListNode pHead, int x) {
if(pHead == null) {return null;}
ListNode cur = pHead;
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
//使用cur遍历所有节点
while(cur != null) {
if(cur.val < x) {
if(bs == null) { //判断是否第一次插入节点
bs = cur; //这个过程相当于插入第一个节点
be = cur;
}else {
be.next = cur;
be = be.next; //或者be = cur;
}
}else {
//大于等于x
if(as == null) {
as = cur; //这个过程相当于插入第一个节点
ae = cur;
}else {
ae.next = cur;
ae = ae.next;
}
}
cur = cur.next;
}
//预防一边有一边没有
if(bs == null) {
return as;
}
be.next =as;
if(as != null) {
ae.next = null;
}
return bs;
}
}
2. 链表的回文结构
首先我们要明白什么是回文结构,如下图所示,从前往后读,跟从后往前读是一样的。
思路一:这里总会有人投机取巧,把链表遍历一遍放到数组,然后看这个数组是不是回文的,但是要注意一个点,题目要求时间复杂度O(n),额外空间复杂度O(1)。所以这种方式不可取。
思路二:还有的人会这么想,在头节点定义一个指针,在最后一个节点定义一个引用,然后让他们往中间走,每走一步比较一次二者是否相等,但他们走到中间值都一样时,这就是个回文结构,这是个不错的思路,但是这是个单向链表,不是双向链表,所以这种方式也有问题。
解题思路:其实我们可以改进一下思路二,先找到这个链表的中间节点,然后把中间节点的后面部分全部翻转,如下图:
接下来就简单了,我们在头节点定义一个指针,最后一个节点定义一个引用,然后让他们两个往中间走,完成这个过程,那就是回文结构了,其实这题所运用的方法在上篇文章中已经讲过了,换汤不换药,就看小伙伴们还记不记得了。先在头节点位置定义一个slow和fast,fast一次走两步,slow一次走一步,节点为偶数个时,当fast.next指向null的时候,slow就是中间节点,如下图:
当fast指向null时候,slow就是中间节点。如下图:
奇数情况下的反转:
我们首先在slow的下个节点定义一个cur,我们要翻转这个cur指向slow这个中间节点,先要记录下来cur的next域,不然会丢失cur后面的节点,所以我们在cur的下一个节点位置定义一个curNext,如下图所示:
然后让cur指向slow,便完成了这一节点的翻转,如下图一:
接着让slow指向cur,cur指向curNext,cueNext指向下一个节点,然后重复上一部分的操作,进行该节点的翻转,如下图所示:
改完之后,slow指向cur,cur指向curNext,现在我们可以看到这个链表翻转完了
最后让head和slow同时向中间遍历,注意不要拿fast遍历,因为在偶数个节点的情况下,fast为空,注意上图博主的值没有修改,所以这个链表不是回文结构,但是思路是没有问题的。
偶数的代码实现:
public class PalindromeList {
public boolean chkPalindrome(ListNode head) {
if(head == null) {
return true;
}
//1.找中间节点
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//2.翻转
ListNode cur = slow.next;
while(cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
//3.前后遍历
while(slow != head) {
if(slow.val != head.val){
return false;
}
slow = slow.next;
head = head.next;
}
return true;
}
}
接下来就是偶数情况了: 其实偶数情况很简单,我们只需要添加一小段代码即可解决问题
如图所示,当head与head的下一个节点相同的时候即可
if(head.next == slow) {
return true;
}
2)代码实现
public class PalindromeList {
public boolean chkPalindrome(ListNode head) {
if(head == null) {
return true;
}
//1.找中间节点
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//2.翻转
ListNode cur = slow.next;
while(cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
//3.前后遍历
while(slow != head) {
if(slow.val != head.val){
return false;
}
//偶数情况
if(head.next == slow) { //这里的if不能与上面的if调换位置
//一定是先判断值!
return true;
}
slow = slow.next;
head = head.next;
}
return true;
}
}
3.相交链表
首先,相交链表是x形还是y形?为什么?如果是x形的,那相交的这个结点就有两个next域了,所以相交链表是y形的!两个链表如下图:
我们只需要把值为10 的这个节点指向第一个链表里的任意一个节点,他们便相交了,如下图
那么这题应该怎么做呢?
解题思路:我们观察上图,可以发现其实相交点之后的节点其实都是一样的,也就相交点前是不一样的。 两个链表相交前的节点都是三个,我们可不可以让两个链表同时走?当他们走到相同的节点时,这个节点就是相交节点。
当然,有时候还会有这种情况:这也是一种相交!
那么我们可不可以让headA先走上一步,然后再和headB一起走?那么话说回来,我们怎么知道headA相交节点前有三个节点,headB相交节点前有两个节点呢?其实这个问题不难解决,因为相交链表是个y字形,headA所在的链表有6个节点,headB所在的链表有5个节点,而二者相交节点之后的节点都是一样的,所以二者的长度差一定差在相交节点前面!
所以解决这题,1.要求长度;2.要走差值步,然后一起走,相遇时就是相交节点
那么我们接下来求长度:
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//1.求长度
int lenA = 0;
int lenB = 0;
while(headA != null) {
lenA++;
headA = headA.next;
}
while(headB != null) {
lenB++;
headB = headB.next;
}
int len = lenA - lenB;
}
}
这么求有没有问题?我们怎么知道lenA和lenB谁大?len会不会等于负数?所以我先定义pl和ps,分别让他们指向较长的链表和较短的链表,最后让pl➖ps得到len,这时候len就是正数了。所以这里len的求值会麻烦点:
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//1.求长度
int lenA = 0;
int lenB = 0;
ListNode pl = headA;//pl永远指向较长的链表,
ListNode ps = headB;// ps永远指向较短的链表
while(pl!= null) {
lenA++;
pl = pl.next;
}
while(ps != null) {
lenB++;
ps = ps.next;
}
pl = headA;
ps = headB;
int len = lenA - lenB;
if(len < 0) {
pl = headB;
ps = headA;
len = lenB - lenA;
}
}
3)代码实现
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//1.求长度
int lenA = 0;
int lenB = 0;
ListNode pl = headA;//pl永远指向较长的链表,
ListNode ps = headB;// ps永远指向较短的链表
while(pl!= null) {
lenA++;
pl = pl.next;
}
while(ps != null) {
lenB++;
ps = ps.next;
}
pl = headA;
ps = headB;
int len = lenA - lenB;
if(len < 0) {
pl = headB;
ps = headA;
len = lenB - lenA;
}
//2.让pl先走len步
while(len != 0) {
pl = pl.next;
len--;
}
//3.一人走一步
while(pl != null && ps != null && pl != ps) {
pl = pl.next;
ps = ps.next;
}
if(pl == ps && pl == null) {
return null;
}
return pl;
}
}
4.环形链表
回环问题,其实是个数学问题!我们在一个回环链表中,可以定义一个fast和slow,让fast走快点,slow走慢点,当他们到一定距离就会相遇,当他们相遇,就说明这个链表是回环的,本题其实最主要是个思维问题,代码实现是很简单的。当我们让fast一次走两步,slow一次走一步时候这种时候两个人就不会错过,为什么呢?这就相当于如下图两个人在跑圈,极限情况下,slow跑完一圈,两人就已经相遇了!我们根据下图发挥想象,不难看出这个过程:slow跑到四分之一圈的时候,fast已经跑完二分之一圈了,当slow跑到二分之一圈时候,fast已经跑完一圈了,当slow跑完一圈的时候,fast也刚好跑完两圈,这个时候两个人就相遇了。所以在一个走一步,一个走两步的情况下是不会错过的!
那么,一个走两步,一个走三步会如何?根据下图,不难想象出,当二者在同一起点时候,他们会错过,当他们不在一个起点时候,二者会相遇
所以我们要确保二者相遇,那么我们就定义fast一次走两步,slow一次走一步
4)代码实现
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
return false;
}
}
文章来源:https://www.toymoban.com/news/detail-817410.html
希望对大家有所帮助,感谢阅读!!!文章来源地址https://www.toymoban.com/news/detail-817410.html
到了这里,关于力扣链表oj面试题,保姆级图解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!