算法小抄8--链表
创始人
2025-05-31 08:52:38
0

定义

链表(指单链表)是一个由头部节点引导的,通过节点指针连接在一起的数据结构,它的形状如下:

 

链表中的节点代码定义如下:

 class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next

相对于线性表,链表的优势在于快速的插入和删除中间的元素(这里要说明的是,如果是对于尾部元素的插入与删除,线性表其实比链表要快),两者的删除操作如下图所示:

顺序表删除:

链表删除:

 是不是发现链表删除以后2的next仍然指向3,看起来和链表内部似乎还有联系?但是从逻辑上我们已经无法通过遍历的方式在链表中查找到2了,所以2已经算是被删除了

链表的基本操作

遍历操作

head为链表的头节点cur=head //我们创建一个cur引用指向头节点
//只要链表当前值不为空
while (cur!=null){//具体操作
...//移动cur指针cur=cur.next
}

可以看到,我们这里创建了一个cur引用指向了head,为什么不直接使用head进行遍历呢?对于一个存储1,2,3,4的链表,它的形状如下,head指针最开始是指向1的

 如果我们直接使用head指针进行遍历操作,遍历操作完以后链表情况如下,我们发现head指向了空节点,如果我们还想对当前链表进行遍历操作怎么办呢?此时已经无法从头开始遍历查找了,因为head已经指向了空

 而如果使用cur指针,我们遍历完以后,链表的形状是这样的,这次是cur指向空,而head依旧还指向头节点,我们依然可以进行遍历操作:

删除某个节点

删除某个节点我们在上面已经画过图了,这里直接贴下来,其实一行代码就可以达到一下的效果,pre.next=cur.next, 删除的对象是2,pre代表删除对象的前一个对象,是不是被这些next绕晕了,我们来分析一下, =号左边是进行赋值的域,也就是我们要对pre的next指针进行赋值操作,在这个例子中我们要对1的next进行赋值操作,而=号的右边是要附上的值,cur.next代表的是3这个节点

所以我们需要先找到待删除节点的前一个节点,其实我们也不需要用到cur指针,而是采用pre.next来代替cur指针的使用,代码如下:

cur = head
//注意看循环条件,因为我们在循环中使用了cur.next
//为了避免空指针异常,while条件中也不能写cur!=null
while(cur.next!=null){//cur.next为目标删除节点,那么cur是否就是pre了if(cur.next==target){//注意看这里cur现在是pre//等号右边的cur.next是否就是我们分析的cur//这个代码是否就等价于pre.next=cur.nextcur.next=cur.next.next}cur=cur.next
}

思考一下,如果链表过短的话,cur.next.next操作是否会引发空指针呢?

答案是不会哈,空指针异常的发生条件是当一个对象本来就是空,我们还要继续访问它的一些属性,也就是我们访问了null.null才会导致空指针,而我们的循环条件是cur,next!=null,这就保证了我们至少访问的是value.null,这个操作时不会导致空指针滴

插入某个节点

插入节点与删除某个节点类似都需要找到待操作位置的前一个节点,其伪代码如下:

定义insert为待插入节点
pre为插入位置的前置节点insert.next=pre.next
pre.next=insert

思考一下这两行代码能否反过来写呢?答案是不行的嗷,例子如下对于1,3,4这个链表,如果我们要在中间插入2这个节点,若先执行pre.next=insert会发生什么呢?

先执行pre.next=insert语句,=号左边对1节点的next域进行赋值, 即1.next=2

而后执行insert.next=pre.next语句,pre依旧指向1,我们要对2.next这个域进行赋值,本来进行插入操作insert.next应该被赋值为3才对,而现在由于pre.next被我们覆盖替换为了1,导致了2.next=1,形成了链表环路

基础操作熟悉了,现在就要开始上强度了,看看链表题有什么骚操作吧

题一:反转链表

题目链接

 我们先理一下思路,看看怎么操作才能把整个链表反过来,用画图来表示的话应该是这样式的:

反转链表:
pre    cur   next1  ->  2  ->  3  ->  4  ->  5pre   cur   next1  <-  2      3  ->  4  ->  5pre    cur    next1  <-  2  <-  3      4  ->  5pre    cur    next1  <-  2  <-  3  <-  4      5pre    cur  next       1  <-  2  <-  3  <-  4  <-  5pre    cur  next       1  <-  2  <-  3  <-  4  <-  5

试着根据这个图来还原一下代码吧:

class Solution:def reverseList(self, head: ListNode) -> ListNode:pre, cur = None, headwhile cur:nxt = cur.next  # 记录当前节点的下一个节点cur.next = pre  # 然后将当前节点指向prepre = cur  # pre和cur节点都前进一位cur = nxtreturn pre

题二:寻找链表的中点

题目链接

第一种简单的思路是,先通过遍历一次,找到链表有多少个节点,然后再遍历一次找到链表的中点进行返回,其代码如下:

class Solution:def middleNode(self, head: ListNode) -> ListNode:n, cur = 0, head"""第一次遍历"""while cur:n += 1cur = cur.next"""第二次遍历"""k, cur = 0, headwhile k < n // 2:k += 1cur = cur.nextreturn cur

第二种思路比较难想到啦,但是是必须要掌握的一个方法,我们运用两个指针slow和fast,slow每次走一步,fast每次走两步,当fast走到结尾的时候,slow是否就刚好到了中点的位置呢?通过这个方法我们可以通过一次遍历就找到链表的中点

class Solution:def middleNode(self, head: ListNode) -> ListNode:slow = fast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextreturn slow

注意注意:

这里对于偶数我们返回的是两个节点中的后一个节点,循环里写的条件是fast and fast.next不为空,如果我们要返回两个节点中的前一个节点循环条件该如何写呢?

答案是 while fast.next and fast.next.next 羊羊可以自己举个例子还原一下

题三:检查回文链表

题一和题二都是链表题中必须掌握的操作哦,因为有时他们还能打出梦幻的combo,比如下面这题:

题目链接

 回文是力扣题的一个常用概念,例如12344321这样的对称的数被称为回文的数字串,那么如何检查一个链表是否是回文链表呢,先思考一下,如何利用题一和题二来解决

  • 题一中我们学会了如何翻转链表,题二中我们学会了找到链表的中点
  • 我们先查找到链表的中点,断开链表后,对后续的链表进行翻转操作,然后一个一个对比,是否就能判断该链表是否回文了呢?
  • 在判断完之后,链表已经被我们断开并且翻转了,为了链表以后还能正确使用,我们是否应该还原链表呢?

先自己写再看最后的答案哦

class Solution:def isPalindrome(self, head: ListNode) -> bool:if head is None:return True# 找到前半部分链表的尾节点并反转后半部分链表first_half_end = self.end_of_first_half(head)second_half_start = self.reverse_list(first_half_end.next)# 判断是否回文result = Truefirst_position = headsecond_position = second_half_startwhile result and second_position is not None:if first_position.val != second_position.val:result = Falsefirst_position = first_position.nextsecond_position = second_position.next# 还原链表并返回结果first_half_end.next = self.reverse_list(second_half_start)return result    #找到链表的中点,如果为偶数是找前一个def end_of_first_half(self, head):fast = headslow = headwhile fast.next is not None and fast.next.next is not None:fast = fast.next.nextslow = slow.nextreturn slow#翻转链表def reverse_list(self, head):previous = Nonecurrent = headwhile current is not None:next_node = current.nextcurrent.next = previousprevious = currentcurrent = next_nodereturn previous

相关内容

热门资讯

安卓系统和oppo系统哪个流畅... 你有没有想过,手机系统哪个更流畅呢?安卓系统和OPPO系统,这两个名字听起来就让人心动。今天,咱们就...
安卓怎么用微软系统,利用微软系... 你是不是也和我一样,对安卓手机上的微软系统充满了好奇?想象那熟悉的Windows界面在你的安卓手机上...
安卓系统如何安装nfc,安卓系... 你有没有想过,用手机刷公交卡、支付账单,是不是比掏出钱包来得酷炫多了?这就得归功于NFC技术啦!今天...
ios系统可以转安卓,跨平台应... 你有没有想过,你的iPhone手机里的那些宝贝应用,能不能搬到安卓手机上继续使用呢?没错,今天就要来...
iOSapp移植到安卓系统,i... 你有没有想过,那些在iOS上让你爱不释手的app,是不是也能在安卓系统上大放异彩呢?今天,就让我带你...
现在安卓随便换系统,探索个性化... 你知道吗?现在安卓手机换系统简直就像换衣服一样简单!没错,就是那种随时随地、随心所欲的感觉。今天,就...
安卓系统安装按钮灰色,探究原因... 最近发现了一个让人头疼的小问题,那就是安卓手机的安装按钮突然变成了灰色,这可真是让人摸不着头脑。你知...
安卓7.1.1操作系统,系统特... 你知道吗?最近我在手机上发现了一个超级酷的新玩意儿——安卓7.1.1操作系统!这可不是什么小打小闹的...
安卓os系统怎么设置,并使用`... 你有没有发现,你的安卓手机有时候就像一个不听话的小孩子,有时候设置起来真是让人头疼呢?别急,今天就来...
安卓降低系统版本5.1,探索安... 你知道吗?最近安卓系统又来了一次大动作,竟然把系统版本给降到了5.1!这可真是让人有点摸不着头脑,不...
解放安卓系统被保护,解放安卓系... 你有没有想过,你的安卓手机其实可以更加自由地呼吸呢?是的,你没听错,我说的就是解放安卓系统被保护的束...
校务帮安卓系统下载,便捷校园生... 你有没有想过,你的手机里装了一个神奇的助手——校务帮安卓系统下载?没错,就是那个能让你轻松管理学校事...
安卓系统没有拼多多,拼多多崛起... 你知道吗?最近我在手机上发现了一个小小的秘密,那就是安卓系统里竟然没有拼多多这个应用!这可真是让我大...
甜城麻将安卓系统,解锁全新麻将... 你有没有听说过那个超级火的甜城麻将安卓系统?没错,就是那个让无数麻将爱好者为之疯狂的软件!今天,就让...
安卓系统卸载的软件,深度揭秘卸... 手机里的软件越来越多,是不是感觉内存不够用了?别急,今天就来教你怎么在安卓系统里卸载那些不再需要的软...
安卓系统推荐好游戏,畅享指尖乐... 手机里的游戏可是咱们休闲娱乐的好伙伴,尤其是安卓系统的用户,选择面那可是相当广呢!今天,就让我来给你...
王者安卓系统怎么卖,揭秘如何轻... 你有没有听说最近王者安卓系统的火爆程度?没错,就是那个让无数玩家沉迷其中的王者荣耀!今天,我就来给你...
安卓开发系统内置证书,基于安卓... 你有没有想过,你的安卓手机里那些神秘的内置证书,它们到底是个啥玩意儿?别急,今天就来给你揭秘这些隐藏...
荣耀安装安卓原生系统,深度体验... 你知道吗?最近荣耀手机界可是掀起了一股热潮,那就是——荣耀安装安卓原生系统!这可不是什么小打小闹,而...
安卓13小米系统,创新功能与流... 你知道吗?最近安卓13系统可谓是风头无两,各大手机厂商纷纷推出自家的新版系统,其中小米的安卓13系统...