建设银行对公打不开网站,痘痘如何去除效果好,枣庄网站制作费用,本网站建设中目录 一、单向链表的基本概念 1.单向链表的概念 2.单向链表的元素插入 元素插入的步骤 3.单向链表的元素删除 元素删除的步骤 4.单向链表的元素查找 元素查找的步骤 5.单向链表的元素索引 元素索引的步骤 6.单向链表的元素修改 元素修改的步骤 二、Python中的单向链表 编辑 三… 目录 一、单向链表的基本概念 1.单向链表的概念 2.单向链表的元素插入 元素插入的步骤 3.单向链表的元素删除 元素删除的步骤 4.单向链表的元素查找 元素查找的步骤 5.单向链表的元素索引 元素索引的步骤 6.单向链表的元素修改 元素修改的步骤 二、Python中的单向链表 编辑 三、单向链表实战 1.面试题 02.02. 返回倒数第 k 个节点 快慢指针法 思路与算法 2.83. 删除排序链表中的重复元素 方法一 双指针判断 方法二 一次遍历进行判断 3.面试题 02.01. 移除重复节点 方法一、哈希表标记法 方法二、字典 四、单向链表的应用 MMO游戏开发 —— AOIArea of Interest 惟愿春日不迟相逢终有时 —— 25.3.2 一、单向链表的基本概念
1.单向链表的概念 对于顺序存储的结构最大的缺点就是插入 和 删除 的时候需要移动大量的元素所以基于前人的智慧他们发明了链表。 链表是由一个个结点组成每个结点之间通过链接关系串联起来每个结点都有一个后继结点最后一个结点的后继结点为空结点如图所示 由链接关系 A -B 组织起来的两个结点B 被称为 A的后继结点A 被称为 B 的前驱结点。链表分为单向链表、双向链表、循环链表等等。 一个链表结点由两部分组成数据域 和 指针域。数据可以是任意类型由编码的人自行指定。指针域 指向 后继结点 的地址。一个结点包含的两部分如下图所示 2.单向链表的元素插入 单向链表的元素插入就是指给定一个索引 i 和一个元素 data生成一个值为 data 的结点并且插入到第i个位置上。
元素插入的步骤
第1步判断插入位置是否合法如果不合法则抛出异常比如:原本只有5个元素给定的索引是100那显然这个位置是不合法的
第2步对给定的元素生成一个链表结点。
第3步如果插入位置是 0则直接把生成的结点的后继结点设置为当前的链表头结点并且把生成的结点设置为新的链表头
第4步如果插入位置不是 0则遍历到插入位置的前一个位置把生成的结点插入进来
第5步更新链表的大小即对链表的元素执行加一操作。 3.单向链表的元素删除 单向链表的元素删除就是指给定一个索引 i将从链表头开始数到的第 i 个结点删除。
元素删除的步骤
第1步判断删除位置是否合法如果不合法则抛出异常。
第2步如果删除位置为首个结点直接把链表头更新为它的后继结点
第3步如果删除位置非首个结点则遍历到要删除位置的前一个结点并且把前一个结点的后继结点设置为它后继的后继。
第4步更新链表的大小也就是将链表的大小执行减一操作。 4.单向链表的元素查找 单向链表的元素查找是指在链表中查找指定元素 x 是否存在如果存在则返回该结点否则返回 null。由于需要遍历整个链表进行元素对比所以查找的时间复杂度为 (n)。
元素查找的步骤
第1步遍历整个链表对链表中的每个元素和指定元素进行比较如果相等则返回当前遍历到的结点;
第2步如果遍历完整个链表都没有找到相等的元素则返回 NULL; 5.单向链表的元素索引 单向链表的元素索引是指给定一个索引值 i从链表头结点开始数数到第 i 个结点并且返回它时间复杂度 O(n)。
元素索引的步骤
第1步首先判断给定的索引是否合法不合法就抛出异常
第2步直接通过索引访问即可获得对应的元素; 6.单向链表的元素修改 单向链表的元素修改是指将链表中指定索引的元素更新为新的值。
元素修改的步骤
第1步直接通过索引访问即可获得对应的结点修改成指定的值; 二、Python中的单向链表
class ListNode:def __init__(self, x):self.val xself.next Noneclass LinkedList:def __init__(self):self.head Noneself.len 0def size(self):return self.lendef insert(self, pos, val):if pos 0 or pos self.len:raise ValueError(index out of range)new_node ListNode(val)if pos 0:new_node.next self.headself.head new_nodeelse:prev self.headfor _ in range(pos - 1):prev prev.nextnew_node.next prev.nextprev.next new_nodeself.len 1def delete(self, pos):if pos 0 or pos self.size():raise ValueError(index out of range)if pos 0:self.head self.head.nextelse:prev self.headfor _ in range(pos - 1):prev prev.nextprev.next prev.next.nextself.len - 1def update(self, pos, val):if pos 0 or pos self.size():raise ValueError(index out of range)curr self.headfor _ in range(pos):curr curr.nextcurr.val valdef search(self, val):curr self.headwhile curr:if curr.val val:return currcurr curr.nextreturn Nonedef index(self, val):index 0curr self.headwhile curr:if curr.val val:return indexcurr curr.nextindex 1return -1def print(self):curr self.headwhile curr:print(curr.val, end - )curr curr.nextprint(None)def Test():list LinkedList()list.insert(0, 1)list.print()list.insert(1, 1)list.print()list.insert(2, 4)list.print()list.insert(0, 1)list.print()list.insert(1, 1)list.print()list.insert(2, 4)list.print()list.update(2, 5)list.print()list.delete(2)list.print()list.insert(2, 4)list.print()list.update(4, 1)list.print()node list.search(4)if node:print(Node found:, node.val)else:print(Node not found)x list.index(4)print(Index of 4:, x)x list.index(5)print(Index of 5:, x)Test() 三、单向链表实战
1.面试题 02.02. 返回倒数第 k 个节点 实现一种算法找出单向链表中倒数第 k 个节点。返回该节点的值。 注意本题相对原题稍作改动 示例 输入 1-2-3-4-5 和 k 2
输出 4 说明 给定的 k 保证是有效的。 快慢指针法
思路与算法
① 初始化两个指针fast 和 slow它们都指向链表的头节点 head。
② 移动快指针让 fast 指针先向前移动 k 步。
③ 同步移动快慢指针当 fast 指针移动到链表的末尾时slow 指针正好指向倒数第 k 个节点。
④ 返回结果返回 slow 指针所指向节点的值。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def kthToLast(self, head: Optional[ListNode], k: int) - int:fast headslow headwhile k 0:fast fast.nextk - 1while fast:fast fast.nextslow slow.nextreturn slow.val 2.83. 删除排序链表中的重复元素 给定一个已排序的链表的头 head 删除所有重复的元素使每个元素只出现一次 。返回 已排序的链表 。 示例 1 输入head [1,1,2]
输出[1,2]示例 2 输入head [1,1,2,3,3]
输出[1,2,3]提示 链表中节点数目在范围 [0, 300] 内-100 Node.val 100题目数据保证链表已经按升序 排列 方法一 双指针判断
思路与算法
① 初始化指针curr 指针从链表的头节点 head 开始。prev 指针初始化为 None用于记录当前节点的前一个节点。
② 遍历链表外层 while 循环用于遍历整个链表直到 curr 为 None。内层 while 循环用于处理当前节点 curr 与前一个节点 prev 值相同的情况。如果发现重复则将 prev.next 指向 curr.next从而跳过重复的节点。
③ 更新指针如果没有发现重复则更新 prev 为当前节点 curr并将 curr 移动到下一个节点。
④ 返回结果最终返回处理后的链表头节点 head。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]:curr headprev Nonewhile curr:while prev ! None and curr.val prev.val:prev.next curr.nextcurr prev.nextif curr None:breakif curr None:breakprev currcurr curr.nextreturn head 方法二 一次遍历进行判断
思路与算法
① 初始化curr指针指向链表的头节点head。
② 空链表处理如果链表为空curr None直接返回head。
③ 遍历链表如果当前节点的值curr.val与下一个节点的值curr.next.val相同则通过curr.next curr.next.next删除下一个节点。如果值不相同则移动curr指针到下一个节点。
④ 返回结果最终返回处理后的链表头节点head。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]:curr headif curr None:return headwhile curr.next:if curr.val curr.next.val:curr.next curr.next.nextelse:curr curr.nextreturn head3.面试题 02.01. 移除重复节点 编写代码移除未排序链表中的重复节点。保留最开始出现的节点。 示例1 输入[1, 2, 3, 3, 2, 1]输出[1, 2, 3]示例2 输入[1, 1, 1, 1, 2]输出[1, 2]提示 链表长度在[0, 20000]范围内。链表元素在[0, 20000]范围内。 方法一、哈希表标记法
思路与算法
① 哈希表标记法利用数组模拟哈希表大小20001用于记录节点值是否已存在。数组下标对应节点值元素值为1表示该值已出现过
② 双指针遍历 tmp指针指向当前已去重链表的尾节点用于连接新节点。 curr指针遍历原链表检查当前节点是否重复。
③ 边界处理若链表为空直接返回初始化时先将头节点加入哈希表避免后续判空操作
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeDuplicateNodes(self, head: Optional[ListNode]) - Optional[ListNode]:if head None:return None# 哈希表hash [0 for i in range(20001)]tmp headcurr head.nexthash[head.val] 1while curr:if hash[curr.val] 0:hash[curr.val] 1tmp.next currtmp tmp.nextcurr curr.nexttmp.next Nonereturn head 方法二、字典
思路与算法
① 初始化字典首先代码创建了一个空字典 dict用于存储已经出现过的节点值。如果链表为空head None则直接返回 None因为空链表不需要去重。
② 处理头节点将头节点的值 head.val 存入字典表示该值已经出现过。
③ 遍历链表使用 curr 指针遍历链表初始时 curr 指向头节点。在遍历过程中检查 curr.next 的值是否已经存在于字典中如果 curr.next.val 不在字典中说明该值尚未出现过将其存入字典并将 curr 指针移动到下一个节点。如果 curr.next.val 已经在字典中说明该值是重复的跳过该节点即将 curr.next 指向 curr.next.next从而删除重复节点。
④ 返回结果遍历结束后返回去重后的链表头节点 head。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeDuplicateNodes(self, head: Optional[ListNode]) - Optional[ListNode]:dict {}if head None:return Nonedict[head.val] 1curr headwhile curr.next:if curr.next.val not in dict:dict[curr.next.val] 1curr curr.nextelse:curr.next curr.next.next return head 四、单向链表的应用
链表相比于顺序表的优点在于对于给定的结点删除操作优于顺序表
MMO游戏开发 —— AOIArea of Interest
简单来说每个玩家只关心他周围的玩家的数据同步而不关心整个世界的数据有一种经典的实现方式双向十字链表
所有玩家被串联在一个十字链表上玩家移动其实就是链表上节点交换位置的过程每个玩家想获取其他玩家的数据只需要在十字链表上进行遍历即可而服务器同步给客户端的数据受AOI控制所以可以根据客户端实际能够承受的性能调整AOI的半径
通过有效的实现AOI技术游戏开发中可以 ① 减少服务器负载 ② 降低网络延迟 ③ 提升游戏性能 ④ 增强玩家用户体验
