做网站要写多少行代码,找外包做网站要多久,网站调用wordpress,建设工程造价信息网官网2.链表#xff08;代码随想录——python版本#xff09;
链表的概念#xff1a;
链表是由指针串联在一起的线性结构#xff0c;一个节点#xff08;node#xff09;由两部分组成#xff1a;
数据域——用来存储数据#xff1b;指针域——用来指向下一个节点#xf…2.链表代码随想录——python版本
链表的概念
链表是由指针串联在一起的线性结构一个节点node由两部分组成
数据域——用来存储数据指针域——用来指向下一个节点如果是双指针另一个指向前一个结点最后一个节点的指针指向null空。
链表的入口节点称为链表的头节点。
我们发现在Python中是没有链表这样的数据类型的所以我们需要自己定义链表类
class listnode(object):# 这是一个单链表类型。def __init__(self,num 0, next None):self.num numself.next next如果我们建立了一个链表节点head并将其赋值给了tmp那么它们操作的便是同一份链表tmp对链表的操作也会影响到head对链表的访问。 链表的类型
单链表
上文所写的就是单链表。
双链表
每一个node有两个指针一个指向前node一个指向后node可以向前查找也可以向后查找。单链表只能够向后查找。
循环列表
链表的首尾相连用来解决约瑟夫环问题。 链表的存储
与数组不同其内存空间并不是连续的只是靠着指针将它们结合起来。也就是说物理上是不连续的仅仅在逻辑上连续。 基础操作
删除一个节点
找到要删除的节点的前一个节点将next指向后一个节点即可。python中有自己的内存回收机制不用我们手动去回收单要是C的话是需要的。
class listnode(object):def __init__(self, num, nextNone):self.num numself.next nexthead listnode(1)
head.next listnode(2)
head.next.next listnode(3)
print(head.num,head.next.num,head.next.next.num,head.next.next.next)head.next head.next.next
print(head.num,head.next.num,head.next.next)下面我们试着将其封装一个函数
203. 移除链表元素 - 力扣LeetCode
不设置虚拟节点不建议那么写因为真的很麻烦。。。特别是判断head是否为空需要判断多次我将错误代码也附加在下面代码随想录中并没有这样的实现若有更好的想法欢迎交流
思路
首先判断head是否为空若为空直接返回head然后判断head是否需要删除若需要将head变为head的后一个节点 如果更新后的head为空一定要及时退出不然会报我下面贴出来的错误。 然后创建一个tmp指向head由于已经保证了head不会再被删除所以直接比较tmp.next.val的值就可以了若要删除将tmp.next的值更新为tmp.next.next否则tmp变为tmp.next为下一次循环做准备。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeElements(self, head: Optional[ListNode], val: int) - Optional[ListNode]:if head None:return headelse:# 先考虑头节点位置怎么删除while head.val val:head head.nexttmp headwhile tmp.next:# 现在我们其实已经确保了起始位置的val不会是val了if tmp.next.val val:tmp.next tmp.next.nextelse:tmp tmp.nextreturn head
报错信息如下
AttributeError: NoneType object has no attribute val^^^^^^^^while head.val val:
Line 12 in removeElements (Solution.py)^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ret Solution().removeElements(param_1, param_2)
Line 54 in _driver (Solution.py)_driver()
Line 69 in module (Solution.py)正确的代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeElements(self, head: Optional[ListNode], val: int) - Optional[ListNode]:if head None:return headelse:# 先考虑头节点位置怎么删除while head.val val:head head.nextif head None:return headtmp headwhile tmp.next:# 现在我们其实已经确保了起始位置的val不会是val了if tmp.next.val val:tmp.next tmp.next.nextelse:tmp tmp.nextreturn head
设置一个虚节点
设置一个虚节点让我们可以使用一个相同的规则去删除节点。
这是怎么做到的呢我们创建一个虚拟的头节点dummy_node其next指向head这样我们的所有删除都是和上文删除tmp一样的了需要注意的是返回的值应该为dummy_node.next。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeElements(self, head: Optional[ListNode], val: int) - Optional[ListNode]:# 建立一个临时的虚拟头节点tmp_head ListNode(next head)# current为循环要用的为什么不直接用tmp_head因为我们要返回新的头节点不应该变动虚拟头节点的位置current指向的也是和虚拟头节点指向的链表current tmp_headwhile current.next ! None:# 为什么直接比较next.val的值呢因为最开始的位置是虚拟头节点而不是头节点if current.next.val val:# 指向原来节点的后一个节点的current.next current.next.nextelse:# 将当前节点变为下一个节点为循环做准备current current.next# 返回虚拟头节点的next指向就是新的头节点return tmp_head.next小结
虚拟节点的概念
增加一个节点
创建一个节点然后将要插入部位的前一个node的next指向它它的next指向原位置的元素。
我们可以发现如果我们在head处插入是非常方便的O(1)要是想要从末尾添加一个node则需要先遍历原链表一次才能够实现这是非常麻烦的O(n)。
这里不给出代码啦因为下面的题目会全部写一遍~
设计一个链表
707. 设计链表 - 力扣LeetCode
链表类节点类
class ListNode:def __init__(self,val 0, next None):self.val valself.next nextMyLinkedList类
class MyLinkedList:def __init__(self):# 先需要创建一个虚拟头节点self.dummy_head ListNode()self.size 0def get(self, index: int) - int:def addAtHead(self, val: int) - None:self.dummy_head.next ListNode(val, self.dummy_head.next)size 1def addAtTail(self, val: int) - None:def addAtIndex(self, index: int, val: int) - None:def deleteAtIndex(self, index: int) - None:# Your MyLinkedList object will be instantiated and called as such:
# obj MyLinkedList()
# param_1 obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)反转链表
206. 反转链表 - 力扣LeetCode
双指针
设定两个指针pre表示前一个节点cur表示当前节点将pre初始化为Nonecur初始化为headcur和pre一起向前移动这样就能一直更改指向顺序实现反向但是我们发现如果更改完顺序后我们没有办法遍历原链表的顺序了所以要使用tmp变量去暂存cur.next的值。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:pre Nonecur headwhile cur:# 由于我们之后要将cur后的next反向所以要在赋值前将cur.next的值保存下来tmp cur.next# 将cur指向pre前一个节点cur.next pre# 更新pre和cur的位置pre, cur cur, tmp# 返回pre即为头节点return pre递归
思路还是双指针。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:# 定义递归def recur(cur, pre):# 和双指针法一样指定当cur为None为退出条件if cur None: return preelse:# 一样需要记录cur.nexttmp cur.nextcur.next pre# 记住一定要return否则程序运行会有问题在新一轮递归中tmp为curpre为curreturn recur(tmp, cur)return recur(head, None)小结
要牢记双指针改变顺寻交换递归的运用。 两两交换链表的节点
24. 两两交换链表中的节点 - 力扣LeetCode
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def swapPairs(self, head: Optional[ListNode]) - Optional[ListNode]:dummy_head ListNode(next head)# cur和dummy_head指向的是同一个链表cur dummy_head# 保证至少还有两个元素在链表内while cur.next and cur.next.next:# 暂存第一个节点因为会改变虚拟节点的指向tmp1 cur.next# 暂存第三个节点因为会改变第二个节点的指向tmp2 cur.next.next.nextcur.next, cur.next.next,cur.next.next.next cur.next.next,tmp1,tmp2cur cur.next.nextreturn dummy_head.next小结
要注意循环结束的条件画图进行交换的分析确定哪些节点需要暂存起来 删除链表中的倒数第n个节点
19. 删除链表的倒数第 N 个结点 - 力扣LeetCode
关键在于找到倒数第n个节点的位置在哪要删除倒数第n个节点那么操作指针要指向上一个节点。
方法
使用虚拟头节点不需要对操作的节点是不是头节点进行特殊操作使用双指针法两个指针先都指向dummy_head让快指针先移动n步然后再让快慢指针一起移动直到快指针指向了None处慢指针就找到了倒数第n个此时慢指针便找到了倒数第n个节点的位置但我们要做的是删除所以快指针应该先走n1步。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:dummy_node ListNode(next head)fast dummy_nodeslow dummy_nodefor i in range(n1):fast fast.nextwhile fast:fast fast.nextslow slow.nextslow.next slow.next.nextreturn dummy_node.next
双指针法倒数第n交换反序难点在于如何找到倒数第n个元素在哪让快指针比慢指针先走n步慢指针所在的位置就是倒数第n个节点的位置清楚删除节点是要找到删除节点的前一个元素。 链表相交
面试题 02.07. 链表相交 - 力扣LeetCode
说实话本来以为就是遍历链表找到值相同的就能够返回了但没想到居然是找节点相同的虽然还是没搞明白示例的1为什么不对但看下面评论貌似是被给定的值给限制死了但是代码里也没有体现啊喂而且先给出图再问有没有相交是否有点。。。
首先循环遍历两个链表得出两个链表的长度然后找出较长的那一端将其指针往后挪动多的长度的位数这样之后curA和curB就可以一起进行移动并判断是否相等了只要curAcurB指针域相同数值域也相同就认为找到交点了。写的有点啰嗦实则可以进行优化可以优化的部分注明在下面的代码中。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode:curA headAcurB headBlenA, lenB 0, 0while curA:curA curA.nextlenA 1while curB:curB curB.nextlenB 1curA, curB headA, headB# 这边是可以优化的写成lenAlenB然后将lenAlenB以及curA和curB互换位置之后的代码便都是一样的了。if lenA lenB:x lenA - lenBfor i in range(x):curA curA.nextwhile curA:if curA curB:return curAelse:curA, curB curA.next,curB.nextelse:x lenB - lenAfor i in range(x):curB curB.nextwhile curA:if curA curB:return curAelse:curA, curB curA.next,curB.nextreturn None环形列表
142. 环形链表 II - 力扣LeetCode
题目要求比较多不仅要判断是不是环形还要判断入口在哪说实话有种无从落笔的感觉。。。
判断是不是环形
首先我们使用双指针法实话没想到看了随想录的视频讲解才明白。设定快慢指针都指向头节点然后让慢节点一个节点一个节点的更新快节点则以两个节点的速度更新在环上就是以一个节点的速度接近慢节点以免丢失。同时需要对快节点和其下一个节点是否为空进行判断若是空说明不是环直接退出若有节点则继续由于循环次数不固定所以使用while循环。
判断入口在哪
这是一个数学问题首先设定head到节点的长度为x快慢节点相遇的位置慢节点顺时针走过的距离为y剩下的圆环路径值为z慢指针走过的长度为xy快指针走过的长度为xyn(yz);
由于快指针的速度是慢指针的两倍
2(xy) xyn(yz)——x (n-1)(yz)z
从这个式子我们好像得不出说明东西那我们让n1发现x z让n2发现 x yz z规律就是一定会走过一个z和n-1个环的长度和x是一样的那么将一个指针挪回head另一个指针停留在原位置以一个单位的速度一起往后移动相遇的位置就是入口。
为什么慢指针走不了一圈呢
假设在进入时两个指针都在起点位置过了一圈那么快慢指针刚好会在入口位置相遇这样最远的位置都只有一圈其他位置就更不用说了。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]:# 双指针法fast,slow head, head# 判断当前快指针和快指针的下一个节点是否存在若不存在说明不存在环while fast and fast.next:# 慢指针以1个单位的速度前进slow slow.next# 快指针以两个单位的速度前进即以一个单位的速度逼近快指针保证不会错过慢指针fast fast.next.next# 若两个相遇了说明存在环if fast slow:# x n (y z) - y (n-1)(yz) z—— # x为起点到入口的距离y为慢指针走过的环的距离不到一圈z为剩余的环的距离# 将其中的一个指针挪到起点另一个保留在原位置都以一个单位的速度前进直至相遇slow headwhile slow ! fast:slow slow.nextfast fast.next# 返回相遇点就是入口return slowreturn None
小结
对快慢指针的认识还是太浅了对如何判断环有了基本认识感觉链表问题基本都是双指针问题。 链表小结
虚拟头节点的方法很常用需要牢记链表的许多问题都可以转换为双指针问题没有思路的时候可以试试将head赋值给多给不同的指针这些指针操作的都是一个链表创建节点时能够一步到位就一步到位不要太啰嗦我容易犯的毛病
过完第一遍感觉只是有了一个大致的印象后面好像代码随想录会有双指针法的专栏依然会坚持学习的。估计可能会5-6刷整个代码随想录后期熟练之后刷题应该会很快毕竟我才研0还有很多时间~
