Python 数据结构 4.单向链表

惟愿春日不迟，相逢终有时

                                            —— 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, val=0, next=None):
#         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, val=0, next=None):
#         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, val=0, next=None):
#         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 head

---

3.面试题 02.01. 移除重复节点

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1：

 输入：[1, 2, 3, 3, 2, 1]
 输出：[1, 2, 3]

示例2：

 输入：[1, 1, 1, 1, 2]
 输出：[1, 2]

提示：

1. 链表长度在[0, 20000]范围内。
2. 链表元素在[0, 20000]范围内。

方法一、哈希表标记法

思路与算法

① 哈希表标记法​：利用数组模拟哈希表（大小20001），用于记录节点值是否已存在。数组下标对应节点值，元素值为1表示该值已出现过

② 双指针遍历：

        tmp指针：指向当前已去重链表的尾节点，用于连接新节点。

   curr指针：遍历原链表，检查当前节点是否重复。

③ 边界处理：​若链表为空直接返回；初始化时先将头节点加入哈希表，避免后续判空操作

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         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, val=0, next=None):
#         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游戏开发 —— AOI（Area of Interest）

简单来说，每个玩家只关心他周围的玩家的数据同步，而不关心整个世界的数据，有一种经典的实现方式：双向十字链表

所有玩家被串联在一个十字链表上，玩家移动其实就是链表上节点交换位置的过程，每个玩家想获取其他玩家的数据，只需要在十字链表上进行遍历即可，而服务器同步给客户端的数据，受AOI控制，所以可以根据客户端实际能够承受的性能，调整AOI的半径

通过有效的实现AOI技术，游戏开发中可以：

① 减少服务器负载 ② 降低网络延迟 ③ 提升游戏性能 ④ 增强玩家用户体验