刷了 LeetCode 的链表专题,我发现了一个秘密!

微信扫一扫,分享到朋友圈

刷了 LeetCode 的链表专题,我发现了一个秘密!

刷了LeetCode的链表专题,我发现了一个秘密!

引言



链表 是以节点(node)存储的 链式存储结构 ,一个node包含一个data域(存放数据)和一个next域(存放下一个node的指针),链表的各个节点不一定是连续的,它可以分为 带头结点 不带头结点 。头结点仅包含next域。





如果不熟悉链表的同学, 建议先看看我的一篇文章 。在这篇文章中,主要讲解使用链表的小技巧,如何使用这些技巧来解题,深入解析了 LeetCode 中具有 代表性 的链表题目,相信我,看了这篇文章,你再也不用担心关于链表的题目了。



1、链表的几个概念讲解



事实上,链表的结构比较简单,阻碍我们理解链表的常常是因为链表的 指针 边界问题 等,这有时会让我们很烦躁,不要慌,我们下面一一对这下概念解析,相信你看了会有收获。



1.1链表中的的指针是什么



我们学习C语言时,学过指针,它描述的是指向一个 内存地址 ,在Java语言中,是不存在指针的,但是我们可以把它理解为 引用



当我们将某个变量(对象)赋值给指针(引用),实际上就是将这个变量(对象)的地址赋值给指针(引用)。



p—>next = q;//表示p节点的后继指针存储了q节点的内存地址。
p—>next = p—>next—>next;//表示p节点的后继指针存储了p节点的下下个节点的内存地址。



1.1指针指向哪儿



我们写链表代码时,使用的指针的 指来指去 ,很快就把我们搞糊涂了,在这种情况下很容易发生 指针丢失 内存泄漏 。我们先普及下这两个概念:



指针丢失 :自己定义的指针不知道指到哪里了,没有明确的指向。



内存泄漏 :链表中的节点没有确切的指针判断,运行时会抛出空指针异常。



我们以 插入节点 删除结点 来分析指针丢失和内存泄漏的具体情况



  • 插入节点



在节点a和节点b之间插入节点x,b是a的下一节点,p指针指向节点a,



p—>next = x;
x—>next = p—>next;



这样的代码会造成指针丢失和内存泄漏,因为这会导致x节点的后继指针指向了自己本身。



正确代码应该为:



x—>next = p—>next;
p—>next = x;





  • 删除节点



同样的,在节点a和节点c之间删除节点b,b是a的下一节点,p指针指向节点a,正确的代码应该为:



p—>next = p—>next—>next;





在删除节点,考虑到删除的节点可能是链表中的第一个节点,我们通常在链表头部加入哨兵(头结点),这样可以使得删除链表的代码是一致的,不用再额外考虑是否是第一个节点的情况。



在链表加入哨兵的代码为



//定义一个哨兵作为传入链表的头结点
ListNode pre =newListNode(0);
pre.next=head;





1.3判断边界的条件



处理链表问题时,要充分考虑链表的 边界判断条件 ,通常情况下,我们经常使用以下几种判断条件:



  • 如果链表为空时,代码是否能正常工作?



  • 如果链表只包含一个结点时,代码是否能正常工作?



  • 如果链表只包含两个结点时,代码是否能正常工作?



  • 代码逻辑在处理头结点和尾结点的时候,是否能正常工作?



这些判断条件需要结合自己的实际场景来使用



2、必须掌握的几类题目



在上面的学习中,我们对链表的一些易错的概念进行了解析,下面,我们就真正的代码实践,我在LeetCode上刷题时发现,链表题目通常分为以下几类:



  • 单链表的反转(LeetCode206)

  • 链表中环的检测(LeetCode141)

  • 两个有序链表的合并(LeetCode21)

  • 删除链表(LeetCode18)

  • 删除链表倒数第n个结点(LeetCode19)

  • 求链表的中间结点(LeetCode876)



这几类链表题基本涵盖了 大部分知识点 ,在下面的学习中,我们将一一攻克它,相信掌握它们之后,在以后 笔试/面试 中,更能随心所欲。



2.1单链表反转(LeetCode206)



思路 :从前往后将每个节点的指针反向,即.next内的地址换成前一个节点的,但为了防止后面链表的丢失,在每次换之前需要先创建个指针指向下一个节点。



classSolution{
publicListNodereverseList(ListNode head){
if(head==null||head.next==null){
returnhead;
}
ListNode p1=head;
//用一个新的链表
ListNode p2=null;
while(p1!=null){
//每次更换指向之前都需要保存下一个节点
ListNode temp=p1.next;
p1.next=p2;
p2=p1;
p1=temp;
}
returnp2;
}
}



2.2链表中环的检测(LeetCode141)



思路 :定义两个指针,p1和p2,指针p1每次走一步,指针p2每次走两步,如果链表中存在环,则必然会在某个时刻满足p1==p2



publicclassSolution{
publicbooleanhasCycle(ListNode head){
if(head==null||head.next==null){
returnfalse;
}
ListNode slow=head;
ListNode fast=head.next;
while(fast!=null&&fast.next!=null){
if(slow==fast){
returntrue;
}
slow=slow.next;
fast=fast.next.next;
}
returnfalse;
}
}



NOTE :对于快指针来说,因为一次跳两步,如果要使用快指针作为判断条件,fast和fast.next都需要判断是否为空。( 不可跨级



2.3两个有序的链表合并(LeetCode21)



思路 :可以新创建一个链表用于合并后的结果,合并的条件如下



  • 两个链表都不为空



>定义一个指针,查找合适的节点并放入新创建链表的下一位置



  • 有一个链表为空



>将不为空的链表放入新创建链表的下一位置



classSolution{
publicListNodemergeTwoLists(ListNode l1, ListNode l2){
if(l1==null){
returnl2;
}
if(l2==null){
returnl1;
}
ListNode result=newListNode(0);
ListNode temp=result;
//两个链表都不为空
while(l1!=null&&l2!=null){
if(l1.val<=l2.val){
temp.next=l1;
temp=temp.next;
l1=l1.next;
}
else{
temp.next=l2;
temp=temp.next;
l2=l2.next;
}
}
//有一个链表为空
if(l1==null){
temp.next=l2;
}
else{
temp.next=l1;
}
returnresult.next;
}
}



2.4删除链表(LeetCode18)



思路 :可以在链表头加一个哨兵(头结点),删除链表时先找到删除链表的上一个位置,按照删除规则删除即可。



classSolution{
publicListNodedeleteNode(ListNode head,intval){
if(head==null){
returnnull;
}
//定义一个哨兵作为传入链表的头结点
ListNode pre =newListNode(0);
pre.next=head;
ListNode temp=pre;
while(temp!=null){
if(temp.next.val==val){
temp.next=temp.next.next;
break;
}
else{
temp=temp.next;
}
}
returnpre.next;
}
}



2.5删除链表倒数第 n 个结点(LeetCode19)



思路 :删除节点时要利用好 哨兵 (带头结点的链表)



>* 遍历数组的长度count

>* 找到要删除节点的前一个位置count-n-1

>* 删除节点



classSolution{
publicListNoderemoveNthFromEnd(ListNode head,intn){
ListNode pre=newListNode(0);
pre.next=head;
ListNode temp1=pre;
ListNode temp2=pre;
intcount=0;
while(temp1!=null){
temp1=temp1.next;
count++;
}
while(count-n-1>0){
temp2=temp2.next;
count--;
}
temp2.next=temp2.next.next;
returnpre.next;
}
}



2.6求链表的中间结点(LeetCode876)



思路 :找出链表中结点的个数count,然后count/2找出中间结点,删除即可。



classSolution{
publicListNodemiddleNode(ListNode head){
if(head==null)returnnull;
ListNode temp=head;
intcount=0;
while(temp!=null){
temp=temp.next;
count++;
}
intmid=count/2;
ListNode result=head;
while(mid>0){
result=result.next;
mid--;
}
returnresult;
}
}



Note :实践是检验真理的唯一标准,要真正的学好链表这个知识点,仅仅学理论是不可靠的,我们需要 多敲代码 多思考 多写多练 ,针对抽象的题目,可以 举例画图 ,来辅助的自己的思考。



3、学习链表的体会



1、 函数中需要移动链表时,最好 新建一个指针来移动 ,以免更改原始指针位置。



2、 单链表有 带头节点 不带头结点 的链表之分,一般做题 默认头结点是有值的



3、 链表的内存时 不连续 的,一个节点占一块内存,每块内存中有一块位置(next)存放下一节点的地址。



3、 链表中找 的思想: 快慢指针 ,创建两个指针, 一个快指针:一次走两步 一个慢指针:一次走一步 ,若相遇则有环,若指向null则无环。



4、 链表找 倒数第k个节点思想 :创建 两个指针 ,第一个指针查询链表中结点的个数 count ,然后 count-k 确定删除结点的位置,用第二个指针遍历链表到 count-n-1 个位置。



5、 反向链表思想: 从前往后 将每个节点的指针反向, 即next内的地址换成前一个节点的 ,但为了防止后面链表的丢失,在每次换之前需要 先创建个指针指向下一个节点



总结



无论学习任何一个知识点,我们都需要在掌握 术(使用方法) 的基础上,学习 道(本源) ,学习数据结构与算法也是一样,我们不仅要掌握 如何使用它 ,更要掌握 为什么要是用它 ,相比其它的方法, 它有什么优点 ,难道是 时间复杂度低 空间复杂度小 ,还是它的数据结构 适合这个场景等等



参考文献



[1]王争.数据结构与算法之美



[2]LeetCode中国网站



刷题组合拳推荐



笔者在过去的3个月时间里整理常用的 数据结构与算法 秒杀剑指offer ,公众号分别回复 数据结构与算法 秒杀剑指offer ,即可领取两套电子书,希望能够帮助大家。







我是 Simon郎 ,一个想要每天博学一点点的小青年,关注我,让我们一起进阶,一起博学。





微信扫一扫,分享到朋友圈

刷了 LeetCode 的链表专题,我发现了一个秘密!

想起去年双11买的电视还没到 广东女子查物流发现已被签收送人

上一篇

腾讯回应财付通小贷公司注册资本变更:10月已完成备案

下一篇

你也可能喜欢

刷了 LeetCode 的链表专题,我发现了一个秘密!

长按储存图像,分享给朋友