陕西网站开发哪家好,酒店网站开发程序员,企业网站建设文章,网站一定要服务器吗1、现在再看链表问题#xff0c;发现之前对傻傻分不清的cur.next有了更清晰的理解了#xff1a;以cur变量表示当前节点#xff0c;cur.next为当前节点的指针或下个节点#xff0c;以上两个含义是一个意思#xff0c;但在实际代码里选择其中一个进行理解会在逻辑上更清晰 2… 1、现在再看链表问题发现之前对傻傻分不清的cur.next有了更清晰的理解了以cur变量表示当前节点cur.next为当前节点的指针或下个节点以上两个含义是一个意思但在实际代码里选择其中一个进行理解会在逻辑上更清晰 2、cur.next ! None出现在if或while的条件位置时按照下个节点理解 3、cur.next xxxxx即cur.next放在等号左侧时按照给当前节点的指针赋值理解 4、xxxxx cur.next即cur.next放在等号右侧时按照指向或操作下个节点理解 5、本文针对的总结题型为建立虚拟头节点解决的问题这类问题在进行对头节点的操作时与其它节点会不一致因此建立虚拟头节点使得所有节点的操作一致最后返回dummyHead.next 203. 移除链表元素 链表的基本操作删除当前节点需要获取上个节点因此cur指向当前节点对下个节点cur.next进行访问和操作此时提前创建虚拟头节点 方便删除头节点时不用额外判断 from typing import Optional203. 移除链表元素
题目描述给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点.
示例 1:输入head [1,2,6,3,4,5,6], val 6输出[1,2,3,4,5]
题眼无。
思路删除当前节点需要获取上个节点因此cur指向当前节点对下个节点cur.next进行访问和操作此时提前创建虚拟头节点 方便删除头节点时不用额外判断
# define singly-linked list
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextclass Solution:def removeElement(self, head: Optional[ListNode], val: int) - Optional[ListNode]:# 情况1、链表为空if head None:return None# 情况2、链表非空# 思路、删除当前节点需要获取上个节点因此cur指向当前节点对下个节点cur.next进行访问和操作dummyHead ListNode() # 虚拟头节点方便删除头节点时不用额外判断dummyHead.next headcur dummyHead# 接下来的操作节点为cur.next即当前节点的下个节点while cur.next ! None:# 只有cur.next不为None时才有属性val和nextif cur.next.val val:cur.next cur.next.next # 删除操作else: # 注意非删除操作时才会更新cur否则会刚好跳过刚删除节点后的节点的判断cur cur.nexthead dummyHead.nextreturn headif __name__ __main__:obj Solution()while True:try:in_line input().strip().split()nums []if in_line[1].split([)[1].split(])[0] ! :nums [int(n) for n in in_line[1].split([)[1].split(])[0].split(,)]val int(in_line[2])print(nums, val)# 创建链表dummyHead ListNode() # 定义一个虚拟头节点cur dummyHead # cur用来遍历建立链表for n in nums:cur.next ListNode(n)cur cur.nexthead dummyHead.nextresult obj.removeElement(head, val)# 输出链表ans []cur resultwhile cur ! None:ans.append(cur.val)cur cur.nextprint(ans)except EOFError:break24. 两两交换链表中的节点 两两交换 删除后一个节点再插入后一个节点到前一个节点之前 from typing import Optional24. 两两交换链表中的节点
题目描述给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。
示例 1:输入head [1,2,3,4]输出[2,1,4,3]
题眼两两交换节点 不修改节点内部的值
思路两两交换 删除后一个节点再插入后一个节点到前一个节点之前
# define singly-linked list
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextclass Solution:def swapPairs(self, head: Optional[ListNode]) - Optional[ListNode]:# 情况1、链表为空或链表节点数为1没有任何操作if head None or head.next None:return head# 情况2、链表节点数大于等于2dummyHead ListNode() # 创建虚拟头节点使得对头节点的操作与其它节点一致dummyHead.next headcur dummyHeadwhile cur.next ! None and cur.next.next ! None: # 参与交换的两个节点均不为空# 1、删除后一个节点temp cur.next.next # 标记后一个节点cur.next.next cur.next.next.next# 2、再插入后一个节点到前一个节点之前temp.next cur.nextcur.next temp# 更新循环条件cur cur.next.nextreturn dummyHead.nextif __name__ __main__:obj Solution()while True:try:in_line input().strip().split([)[-1].split(])[0]if in_line :head Noneprint([])else:nums [int(n) for n in in_line.split(,)]head ListNode(nums[0], None) # 创建头节点cur headfor i in nums[1:]: # 添加链表元素newNode ListNode(i, None)cur.next newNodecur cur.next# 输出原始链表cur headwhile cur ! None:print(cur.val, end )cur cur.nextprint()# 调用函数result obj.swapPairs(head)# 输出结果链表cur resultwhile cur ! None:print(cur.val, end )cur cur.nextprint()except EOFError:break92. 反转链表 II 1、一次遍历对[left, right]内的节点执行“206. 反转链表”操作并对left节点及前一个节点标记 2、这道题不像上两个题让cur等于dummyHead进行遍历以使得对所有节点的操作一致而是设置pre等于dummyHead算是达到了等价的效果不然无法在对head有操作时最后返回dummyHead.next作为答案 from typing import Optional92. 反转链表 II
题目描述给你单链表的头指针 head 和两个整数left 和 right 其中left right 。
请你反转从位置 left 到位置 right 的链表节点返回 反转后的链表 。
示例 1:输入head [1,2,3,4,5], left 2, right 4输出[1,4,3,2,5]
题眼反转链表
思路一次遍历对[left, right]内的节点执行“206. 反转链表”操作并对left节点及前一个节点标记
# define singly-linked list
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextclass Solution:def reverseBetween(self, head: Optional[ListNode], left: int, right: int) - Optional[ListNode]:# 注意链表的节点数从1开始算起dummyHead ListNode()dummyHead.next head # 创建虚拟头节点方便left1即为头节点时 的操作 与其它节点一致pre, cur dummyHead, head # 类似“206. 反转链表”赋值pre为NoneleftPre, leftCur None, None # 对left节点及前一个节点标记for i in range(1, right 1):if i left:if i left:leftPre, leftCur pre, cur # 记录left前一个节点和left节点post cur.nextcur.next prepre, cur cur, postelse:pre, cur cur, cur.nextleftPre.next pre # 此时pre指向第right个节点leftCur.next cur # 此时cur指向right后一个节点return dummyHead.nextif __name__ __main__:while True:try:in_line input().strip().split()nums [int(n) for n in in_line[1].split([)[1].split(])[0].split(,)]left int(in_line[2].split(,)[0])right int(in_line[3])# print(nums, left, right)# 创建链表dummyHead ListNode()cur dummyHeadfor n in nums:cur.next ListNode(n, None)cur cur.nexthead dummyHead.next# 打印链表result headans []cur resultwhile cur ! None:ans.append(cur.val)cur cur.nextprint(ans)except EOFError:break
