新建网站怎么做,wordpress和ss一起,做ps找图的网站,山东省住建厅官网二建查询链表
链表类型#xff1a; 单链表#xff08;可以访问后面的一个节点#xff09; 双链表#xff08;可以访问前后节点#xff09; 循环链表#xff08;最后一个节点指向首节点#xff09;
在Python中定义单链表节点#xff1a;
class ListNode:def __init__(self, v…链表
链表类型 单链表可以访问后面的一个节点 双链表可以访问前后节点 循环链表最后一个节点指向首节点
在Python中定义单链表节点
class ListNode:def __init__(self, val, nextNone):self.val valself.next next移除链表元素 203.
#链表删除 #哑节点 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。
为了统一处理删除操作在head节点前添加一个哑节点。
class Solution:def removeElements(self, head: Optional[ListNode], val: int) - Optional[ListNode]:dummy ListNode(0, head)pre dummycur dummy.nextwhile cur:if cur.val val:pre.next cur.next cur cur.nextelse:pre pre.nextcur cur.nextreturn dummy.nextPython有垃圾回收不需要手动删除节点。 设计链表 707.
你可以选择使用单链表或者双链表设计并实现自己的链表。
单链表中的节点应该具备两个属性val 和 next 。val 是当前节点的值next 是指向下一个节点的指针/引用。
class Node:def __init__(self, val0, nextNone):self.val valself.next nextclass MyLinkedList:def __init__(self):self.dummy Node(-1, None)self.max_index -1 def get(self, index: int) - int:if index 0 or index self.max_index:return -1cur self.dummy.next for i in range(index):cur cur.nextreturn cur.valdef addAtHead(self, val: int) - None:self.dummy.next Node(val, self.dummy.next)self.max_index 1def addAtTail(self, val: int) - None:cur self.dummywhile cur.next:cur cur.nextcur.next Node(val)self.max_index 1def addAtIndex(self, index: int, val: int) - None:if index 0 or index self.max_index 1:return cur self.dummyi 0for i in range(index):cur cur.nextcur.next Node(val, cur.next)self.max_index 1def deleteAtIndex(self, index: int) - None:if index 0 or index self.max_index:return cur self.dummyfor i in range(index):cur cur.nextcur.next cur.next.next self.max_index - 1反转链表 206.
给你单链表的头节点 head 请你反转链表并返回反转后的链表。 #双指针 使用temp保存cur.next 因为反转后cur.next就改变了无法再访问原来的下一个元素了。 class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:pre Nonecur headwhile cur:temp cur.next # 下一个节点cur.next pre # 反转next方向pre curcur temp # 去下一个return pre 两两交换链表中的节点 24.
#哑节点 给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。 有些题解里很多cur.next.next.next看起来很麻烦。 用临时节点记录一下似乎就不用那么多next了。而且也不用考虑.next赋值的顺序了。 class Solution:def swapPairs(self, head: Optional[ListNode]) - Optional[ListNode]:dummy ListNode(0, head)cur dummy# 交换cur后面的两个节点while cur.next and cur.next.next:node1 cur.next node2 node1.next node3 node2.next # cur-node1-node2--node3(node2.next) ---- cur-node2-node1--node3(node2.next) cur.next node2 node2.next node1 node1.next node3cur node1 return dummy.next删除链表的倒数第N个节点 19.
#双指针 #哑节点 双指针的应用。快指针fast先走n步当快指针到达倒数第1个节点时慢指针slow到达倒数n1个节点删除slow的下一个节点。 哑节点对简化删除操作很有用如果不用哑节点删除head就要特殊处理。
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:dummy ListNode(0, head)fast dummyslow dummy# 当fast 到达倒数第1个节点 slow到达倒数第n1个节点for i in range(n):fast fast.nextwhile fast.next :fast fast.nextslow slow.nextslow.next slow.next.next return dummy.next 链表相交 面试题 02.07. 同 160
#双指针 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回 null 。
两个链表如果有相同的节点则从相同节点开始一直到末尾都是相同的。 让较长的链表先走 abs(lengthA-lengthB)个节点然后比较两个链表。
class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode:def getLength(head):length 0while head:head head.nextlength 1return lengthlengthA getLength(headA)lengthB getLength(headB) Long, Short (headA, headB) if lengthA lengthB else (headB, headA)for _ in range (abs(lengthA- lengthB)):Long Long.nextwhile Short:if Short Long:return Shortelse:Short Short.nextLong Long.nextreturn None
环形链表II 142.
#集合 #双指针
直接用set记录访问过的节点再次遇到则表明出现了环。
class Solution:def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]:visited set()pos headwhile pos:if pos in visited:return poselse:visited.add(pos)pos pos.nextreturn None双指针。快指针fast一次走两步慢指针slow一次走一步。如果有环两个指针一定会遇到。 而找到环的入口比较难需要推导一下。这个不太好理解推荐看代码随想录的视频
相遇时slow指针走过的节点数是 xy, fast走过的节点数是 xy n(yz) ,n1 fast一次走两个节点所以走过的节点数是slow的两倍即 xyn(yz) 2xy)。 化简一下得到 x (n-1)(yz) z n 1时 x z 也就是说一个指针index1从slow与fast相遇点出发一个指针index2从头节点出发会在入口节点相遇。 n大于1时和n为1的时候 效果是一样的一样可以通过这个方法找到 环形的入口节点只不过index1 指针在环里 多转了(n-1)圈然后再遇到index2相遇点依然是环形的入口节点 class Solution:def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]:fast headslow headwhile fast and fast.next:slow slow.nextfast fast.next.nextif slow fast:index1 fastindex2 headwhile index1 ! index2:index1 index1.nextindex2 index2.nextreturn index2return None链表小结
哑节点对简化链表操作很有用。添加一个哑节点对头节点的处理会和其他节点一样。 双指针是常用的方法可以用来判断链表是否有环找到链表倒数第n个元素。
