淘客手机网站模板,微信小程序下载app,wordpress+用户前台,北京市网站设计公司网址目录#xff1a;
目的
思路
复杂度
记忆秘诀
python代码 目的 1→1→2→3→3 删除重复后变成2。 思路 这个任务是删除链表里重复的节点包含本身。可以看成是一个抽奖活动的系统升级。某人通过多种方式报名#xff08;节点不同#xff09;#xff0c;后台数据检测到这些…目录
目的
思路
复杂度
记忆秘诀
python代码 目的 1→1→2→3→3 删除重复后变成2。 思路 这个任务是删除链表里重复的节点包含本身。可以看成是一个抽奖活动的系统升级。某人通过多种方式报名节点不同后台数据检测到这些人其实是同一个人节点值相同。为了公平抽奖并且惩罚该人系统删除该用户的所有报名记录所有重复节点只保留那些唯一的报名用户。 准备检查
创建了一个临时记录dummy 设置一个临时记录方便从头开始管理避免对第一个报名者的特殊处理。dummy.next head 表示临时记录指向实际第一个用户节点。系统管理员prev 负责指引哪些记录有效哪些需要删除。在开始时prev 指向临时记录 dummy准备去处理实际用户。正在被检查的用户current 系统正在检查的报名信息逐一遍历确保没有重复的报名。 开始检查 系统检查当前记录点和下一个记录是否重复 如果发现当前记录和下一个记录重复 if current.next and current.val current.next.val:系统就开始一个内循环while current.next and current.val current.next.val:继续跳过所有重复的报名记录current current.next直到所有相同的记录都被跳过。比如某个用户通过不同方式多次报名系统会一直跳过他们直到没有更多重复记录为止。管理员操作 有重复的情况 当我们跳过了所有重复的记录后系统管理员会删除当前重复的所有记录prev.next current.next。具体操作是让 prev即最后一个不重复的报名记录指向 current 后面唯一的一个不重复的记录也就是跳过所有重复的报名记录。没有重复的情况 管理员会把继续准备检查下一条记录prev prev.next。系统继续检查下一个用户 无论当前记录是否重复系统都会继续检查下一个记录current current.next。 检查结束
从第一个报名记录开始检查一直检查到所有记录都处理完为止。最后系统返回去掉所有重复报名记录后的链表dummy.next 就是去除重复节点后的实际链表头。 复杂度 时间复杂度O(n 只检查了一次报名表链表被遍历一次n 是链表中节点的数量。 空间复杂度O(1) 只使用了常数级别的额外空间。 记忆秘诀 虚拟头节点避免处理链表头部的特殊情况。内外循环配合内循环跳过重复节点外循环更新链表。返回结果返回去重后的实际链表dummy.next。 python代码
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next None
#
# 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可
#
#
# param head ListNode类
# return ListNode类
#
class Solution:def deleteDuplicates(self, head: ListNode) - ListNode:# 创建一个虚拟头节点方便处理边界情况dummy ListNode(0)dummy.next headprev dummy # prev指向当前不重复元素的前一个节点current head # current指向当前节点while current:# 检查当前节点是否有重复if current.next and current.val current.next.val:# 找到所有重复的节点while current.next and current.val current.next.val:current current.next # 跳过重复节点# 将prev的下一个指向当前节点的下一个即删除重复节点prev.next current.nextelse:# 如果没有重复prev指向当前节点prev prev.next# 移动到下一个节点current current.nextreturn dummy.next # 返回去掉重复元素后的链表头节点 * 欢迎大家探讨新思路能够更好的理解和记忆
