Leetcode Top100答案和解释 -- Python版本（链表）
160. 相交链表
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
p, q = headA, headB
while p is not q:
if p:
p = p.next
else:
p = headB
if q:
q = q.next
else:
q = headA
return q
-
初步思路标题（哈希集合法）：
最直接的解法是遍历第一个链表，将所有节点存入哈希集合，然后遍历第二个链表检查是否有节点在集合中。这种方法虽然直观，但需要O(m)或O(n)的额外空间，不符合空间复杂度O(1)的要求。 -
优化思路标题（双指针交替遍历法）：
-
优化方向1：利用两个指针分别从两个链表头开始遍历，当指针到达末尾时，将其重定向到另一个链表的头部
-
优化方向2：通过这种交替遍历的方式，两个指针最终会在相交节点相遇，或者同时到达末尾（null）
-
-
关键策略优势：
-
策略带来的具体好处1：无需额外存储空间，空间复杂度降为O(1)
-
策略带来的具体好处2：通过消除长度差，确保两个指针在第二次遍历时能够同步到达相交点
-
策略带来的具体好处3：代码简洁，只需要简单的指针操作即可实现
-
-
具体实现：
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
p, q = headA, headB
# 当两个指针不相遇时继续遍历
while p is not q:
# p指针移动到下一个节点，如果到达末尾则从headB开始
if p:
p = p.next
else:
p = headB
# q指针移动到下一个节点，如果到达末尾则从headA开始
if q:
q = q.next
else:
q = headA
# 返回相遇节点（如果没有相交，则返回null）
return q
206. 反转链表
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
p = None
c = head
while c:
n = c.next
c.next = p
p = c
c = n
return p-
初步思路标题（借助外部数组法）：
最直观的解法是遍历链表将所有节点值存入数组，然后反向遍历数组重新构建链表。这种方法虽然易于理解，但需要O(n)的额外空间存储节点值，且破坏了原链表的结构，不符合题目对原地反转的隐含要求。 -
优化思路标题（迭代指针反转法）：
-
优化方向1：使用三个指针（前驱p、当前c、后继n）在遍历过程中逐步反转每个节点的指向
-
优化方向2：通过保存当前节点的下一个节点，防止在改变指向后丢失后续节点的访问能力
-
-
关键策略优势：
-
策略带来的具体好处1：只需遍历一次链表，时间复杂度为O(n)
-
策略带来的具体好处2：仅使用三个指针变量，空间复杂度为O(1)，实现真正的原地反转
-
策略带来的具体好处3：能够正确处理空链表和单节点链表的边界情况
-
-
具体实现：
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
p = None # 前驱指针，初始为None
c = head # 当前指针，从链表头开始
while c: # 当当前节点不为空时继续遍历
n = c.next # 保存下一个节点，防止丢失
c.next = p # 将当前节点的next指向前驱，完成反转
p = c # 前驱指针移动到当前节点
c = n # 当前指针移动到下一个节点
return p # 返回新的头节点（原链表的最后一个节点）
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
n = self.reverseList(head.next)
head.next.next = head
head.next = None
return n-
初步思路标题（迭代指针反转法）：
常规解法是使用三个指针迭代遍历链表，逐个反转节点的指向。这种方法直观且高效，但需要手动维护指针关系，代码相对繁琐。 -
优化思路标题（递归回溯反转法）：
-
优化方向1：利用递归调用栈天然的后进先出特性，先递归到链表末尾，然后在回溯过程中逐步反转指针方向
-
优化方向2：将问题分解为"反转当前节点之后的链表"这一子问题，通过递归调用解决子问题后再处理当前节点
-
-
关键策略优势：
-
策略带来的具体好处1：代码极其简洁优雅，只需几行就能实现完整功能
-
策略带来的具体好处2：递归思路更符合数学归纳法的思维方式，易于理解和证明正确性
-
策略带来的具体好处3：虽然使用调用栈（空间复杂度O(n)），但在链表反转的场景中通常也是可接受的
-
-
具体实现：
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 递归终止条件：空链表或只有一个节点
if not head or not head.next:
return head
# 递归反转后续链表，返回新的头节点
n = self.reverseList(head.next)
# 关键步骤：将当前节点的下一个节点的next指向当前节点
# 例如：原链表 ... -> head -> next -> ...
# 反转后变为 ... -> next -> head -> ...
head.next.next = head
head.next = None # 防止形成环
return n
234. 回文链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleaNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
s = f = head
while f and f.next:
s = s.next
f = f.next.next
return s
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
p, c = None, head
while c:
n = c.next
c.next = p
p = c
c = n
return p
def isPalindrome(self, head: Optional[ListNode]) -> bool:
mid = self.middleaNode(head)
head2 = self.reverseList(mid)
while head2:
if head.val != head2.val:
return False
head = head.next
head2 = head2.next
return True-
直观解法及其局限性：最容易想到的是遍历链表将节点值存入数组，然后使用双指针判断回文。这种方法时间复杂度O(n)可以接受，但空间复杂度O(n)不满足进阶要求。
-
快慢指针与反转链表优化思路：
-
优化方向1：使用快慢指针找到链表中点，将问题转化为比较前半部分和反转后的后半部分
-
优化方向2：在原链表上直接反转后半部分，实现空间复杂度O(1)
-
-
关键策略优势：
-
策略带来的具体好处1：通过快慢指针一次遍历即可找到中点，无需预先知道链表长度
-
策略带来的具体好处2：原地反转后半部分链表，不占用额外空间
-
策略带来的具体好处3：反转后直接比较节点值，逻辑清晰简洁
-
-
具体实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 快慢指针找中点
s = f = head
while f and f.next:
s = s.next
f = f.next.next
return s
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 迭代反转链表
p, c = None, head
while c:
n = c.next
c.next = p
p = c
c = n
return p
def isPalindrome(self, head: Optional[ListNode]) -> bool:
# 找到中点
mid = self.middleNode(head)
# 反转后半部分
head2 = self.reverseList(mid)
# 比较前后两部分
while head2:
if head.val != head2.val:
return False
head = head.next
head2 = head2.next
return True
141. 环形链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
s = f = head
while f and f.next:
s = s.next
f = f.next.next
if f is s:
return True
return False
-
初步思路标题（哈希表记录法）：
最直观的解法是遍历链表，使用哈希表（或集合）记录每个访问过的节点。每次访问新节点时，检查该节点是否已经在哈希表中。如果在，说明存在环；如果遍历到空指针（None），说明链表无环。这种方法时间复杂度O(n)，空间复杂度O(n)，需要额外的存储空间。 -
优化思路标题（快慢双指针法/Floyd判圈算法）：
-
优化方向1：使用两个指针，慢指针每次移动一步，快指针每次移动两步，利用"追及问题"的原理
-
优化方向2：如果链表中有环，快指针最终一定会追上慢指针（两者相遇）；如果无环，快指针会先到达链表末尾
-
-
关键策略优势：
-
策略带来的具体好处1：空间复杂度降为O(1)，只需要两个指针变量，不需要额外的哈希表存储
-
策略带来的具体好处2：时间复杂度保持O(n)，且实现代码简洁，只需几行就能完成判断
-
策略带来的具体好处3：能够处理链表长度很长的情况，不会因为哈希冲突而影响性能
-
-
具体实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
# 初始化快慢指针，都指向头节点
s = f = head
# 快指针每次移动两步，需要确保当前节点和下一个节点都不为空
while f and f.next:
# 慢指针移动一步
s = s.next
# 快指针移动两步
f = f.next.next
# 如果快慢指针相遇，说明存在环
if f is s:
return True
# 快指针到达链表末尾，说明无环
return False
142. 环形链表 II
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
s = f = head
while f and f.next:
s = s.next
f = f.next.next
if s is f:
while s is not head:
s = s.next
head = head.next
return s
return None -
初步思路标题（哈希表记录法）：
最直接的解法是遍历链表，使用哈希表（或集合）记录每个访问过的节点。当第一次遇到已经存在于哈希表中的节点时，该节点即为环的入口。这种方法可以准确找到环的入口，但空间复杂度为 O(n)，需要额外的存储空间来记录已访问节点。 -
优化思路标题（快慢双指针 + 数学推导法）：
-
优化方向1：首先使用快慢指针判断是否存在环（与环形链表 I 相同的方法）
-
优化方向2：当快慢指针相遇后，利用数学关系找到环的入口：将其中一个指针重置到头节点，两个指针同时以相同速度移动，相遇点即为环的入口
-
优化方向3：基于几何原理：设头节点到环入口距离为 a，环入口到相遇点距离为 b，相遇点到环入口距离为 c，则快指针走过的路程是慢指针的 2 倍，推导出 a = c，从而确定重置指针后再次相遇的位置即为环入口
-
-
关键策略优势：
-
策略带来的具体好处1：空间复杂度降为 O(1)，仅使用两个指针变量，不需要额外的哈希表存储
-
策略带来的具体好处2：时间复杂度为 O(n)，且只需一次遍历找到相遇点，第二次遍历找到入口点
-
策略带来的具体好处3：利用数学推导保证算法的正确性，无需额外判断边界情况
-
-
具体实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 初始化快慢指针，都指向头节点
s = f = head
# 第一阶段：使用快慢指针判断是否存在环
while f and f.next:
# 慢指针移动一步
s = s.next
# 快指针移动两步
f = f.next.next
# 如果快慢指针相遇，说明存在环
if s is f:
# 第二阶段：找到环的入口
# 将慢指针（或快指针）重置到头节点
# 两个指针每次都移动一步，相遇点即为环的入口
while s is not head:
s = s.next
head = head.next
return s
# 没有环，返回 None
return None
21. 合并两个有序链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
cur = d = ListNode()
while list1 and list2:
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
cur.next = list1 or list2
return d.next-
初步思路标题（迭代遍历法）：
最直接的解法是创建一个新的链表，使用两个指针分别遍历两个原始链表，每次比较两个指针所指节点的值，将较小的节点添加到新链表中，然后移动相应指针。这种方法需要依次处理所有节点，但实现起来逻辑清晰。 -
优化思路标题（哨兵节点 + 双指针迭代法）：
-
优化方向1：引入一个虚拟头节点（哨兵节点），简化边界条件的处理，避免单独处理空链表的情况
-
优化方向2：使用双指针分别遍历两个链表，每次比较当前节点的值，将较小的节点接到结果链表后面
-
优化方向3：当一个链表遍历完成后，直接将另一个链表的剩余部分接到结果链表末尾，无需逐个节点处理
-
-
关键策略优势：
-
策略带来的具体好处1：使用哨兵节点作为头节点，统一了所有节点的插入操作，无需特殊处理第一个节点的添加
-
策略带来的具体好处2：时间复杂度为 O(m + n)，其中 m 和 n 分别为两个链表的长度，只需遍历每个节点一次
-
策略带来的具体好处3：空间复杂度为 O(1)，只使用了常数额外空间（哨兵节点和几个指针变量）
-
策略带来的具体好处4：代码简洁，逻辑清晰，利用 Python 的短路运算
list1 or list2优雅地处理剩余节点
-
-
具体实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
# 创建哨兵节点（虚拟头节点），简化边界处理
cur = d = ListNode()
# 当两个链表都还有节点时，进行合并
while list1 and list2:
# 比较当前节点的值，将较小的节点接到结果链表
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
# 移动结果链表的当前指针
cur = cur.next
# 将剩余未处理完的链表直接接上
# 使用短路运算：list1 非空则接 list1，否则接 list2
cur.next = list1 or list2
# 返回哨兵节点的下一个节点，即合并后链表的真正头节点
return d.next
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if list1 is None: return list2
if list2 is None: return list1
if list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
list2.next = self.mergeTwoLists(list1, list2.next)
return list2-
初步思路标题（递归法）：
合并两个有序链表的问题具有最优子结构特征：每次比较两个链表的头节点，选择较小的节点作为当前节点，然后递归地合并剩余的部分。这种递归思路符合分治思想，代码表达直观且简洁。 -
优化思路标题（递归分治法）：
-
优化方向1：定义递归的基本情况——当任一链表为空时，直接返回另一个链表
-
优化方向2：比较两个链表当前头节点的值，选择较小的节点作为当前结果节点
-
优化方向3：将当前节点的 next 指针指向递归合并后剩余部分的返回结果，形成递归调用
-
-
关键策略优势：
-
策略带来的具体好处1：代码极其简洁，逻辑清晰，完美体现了递归的思想
-
策略带来的具体好处2：时间复杂度为 O(m + n)，与迭代法相同，每个节点被处理一次
-
策略带来的具体好处3：利用递归函数的调用栈来隐式管理节点连接过程，无需显式维护指针
-
策略带来的具体好处4：递归方式天然地体现了问题的分解过程，符合函数式编程思维
-
-
具体实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
# 基本情况：如果其中一个链表为空，直接返回另一个链表
if list1 is None:
return list2
if list2 is None:
return list1
# 比较当前头节点的值
if list1.val < list2.val:
# list1 的当前节点较小，将其 next 指向递归合并剩余部分的结果
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
# list2 的当前节点较小或相等，将其 next 指向递归合并剩余部分的结果
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
2. 两数相加
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
cur = d = ListNode()
c = 0
while l1 or l2 or c:
if l1:
c += l1.val
l1 = l1.next
if l2:
c += l2.val
l2 = l2.next
cur.next = ListNode(c % 10)
c //= 10
cur = cur.next
return d.next-
初步思路：直接转换为整数相加：
-
最初可能想到将两个链表分别遍历，将每个链表表示的数字转换为整数，然后相加，最后再将结果转换回链表形式。
-
这种方法的局限性在于：当链表长度很长时（例如超过Python整数能表示的范围），会导致整数溢出或性能问题，且需要额外的空间来存储中间转换结果，时间复杂度为O(3n)，不够优雅。
-
-
优化思路：逐位相加并处理进位：
-
优化方向1：原地模拟加法过程：将问题转化为模拟小学加法竖式计算的过程，从两个链表的最低有效位（即链表头部）开始逐位相加，避免了数字转换的开销，直接操作链表节点。
-
优化方向2：使用哑节点和进位变量：引入哑节点（dummy node）简化链表创建逻辑，使用进位变量
c记录每次相加的进位，通过一个循环同时遍历两个链表，当某个链表先结束时，只处理另一个链表剩余的节点与进位。
-
-
关键策略优势：
-
策略带来的具体好处1：一次遍历完成计算：只需遍历两个链表一次，时间复杂度为O(max(m, n))，其中m和n分别为两个链表的长度，比先转换再转换的方式更高效。
-
策略带来的具体好处2：空间复杂度优化：除了结果链表所需的空间外，仅使用常量级别的额外空间（哑节点指针、当前指针、进位变量），避免了创建中间数据结构。
-
策略带来的具体好处3：优雅处理边界条件：循环条件
while l1 or l2 or c同时考虑了链表未遍历完和最终进位的情况，无需额外判断，代码简洁且不易出错。
-
-
具体实现：
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# 创建哑节点作为结果链表的头节点前驱
cur = d = ListNode()
# 进位变量，初始为0
c = 0
# 当任一链表未遍历完或存在进位时，继续循环
while l1 or l2 or c:
# 如果l1当前节点存在，将其值加入进位，并移动指针
if l1:
c += l1.val
l1 = l1.next
# 如果l2当前节点存在，将其值加入进位，并移动指针
if l2:
c += l2.val
l2 = l2.next
# 创建新节点，值为当前和的个位数
cur.next = ListNode(c % 10)
# 更新进位为当前和的十位数
c //= 10
# 移动当前指针
cur = cur.next
# 返回结果链表的头节点（跳过哑节点）
return d.next
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], c = 0) -> Optional[ListNode]:
if l1 is None and l2 is None and c == 0:
return None
s = c
if l1:
s += l1.val
l1 = l1.next
if l2:
s += l2.val
l2 = l2.next
return ListNode(s % 10, self.addTwoNumbers(l1, l2, s //10))-
初步思路：迭代逐位相加：
-
最初可能想到使用循环遍历两个链表，逐位计算和并处理进位，通过维护当前指针构建结果链表。
-
这种方法的局限性在于：需要显式管理哑节点、当前指针和循环条件，代码虽然直观但需要仔细处理边界情况，且对于习惯递归思维的开发者不够简洁。
-
-
优化思路：递归模拟加法过程：
-
优化方向1：利用递归简化链表遍历：将问题转化为递归形式，每次处理当前位的计算，递归调用处理剩余部分，利用递归调用栈天然地处理了链表的递进关系。
-
优化方向2：使用函数参数传递进位：将进位作为递归函数的参数传递，避免了在迭代中维护额外的进位变量，使得进位信息在递归调用链中自然流动。
-
优化方向3：递归基的巧妙设计：将终止条件设为
l1、l2和进位c同时为空，此时返回None，简洁地处理了所有边界情况。
-
-
关键策略优势：
-
策略带来的具体好处1：代码简洁优雅：相比迭代版本，递归实现仅需8行核心代码，逻辑清晰，将加法过程与链表构建自然地结合在一起，可读性极高。
-
策略带来的具体好处2：天然处理不同长度链表：递归调用时，当某个链表为
None，后续递归仅处理另一个链表和进位，无需额外的判断逻辑，由递归结构自动处理。 -
策略带来的具体好处3：递归深度与链表长度对应：递归深度恰好等于较长链表的长度，空间复杂度为O(max(m, n))，与迭代版本使用栈空间一致，但代码表达更简洁。
-
策略带来的具体好处4：参数默认值的灵活运用：通过为进位参数设置默认值0，使得首次调用时无需显式传递进位，保持了良好的API设计。
-
-
具体实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], c = 0) -> Optional[ListNode]:
# 递归基：当两个链表都为空且没有进位时，返回None
if l1 is None and l2 is None and c == 0:
return None
# 计算当前位的和（包括进位）
s = c
if l1:
s += l1.val
l1 = l1.next
if l2:
s += l2.val
l2 = l2.next
# 创建当前节点，值为和的个位数
# 递归构建后续节点，传入更新后的l1、l2和进位（和的十位数）
return ListNode(s % 10, self.addTwoNumbers(l1, l2, s // 10))
19. 删除链表的倒数第 N 个结点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
left = right = d = ListNode(next = head)
for _ in range(n):
right = right.next
while right.next:
left = left.next
right = right.next
left.next = left.next.next
return d.next-
初步思路：两次遍历法：
-
最初可能想到先遍历一次链表得到总长度L，然后计算要删除的节点是正数第(L - n + 1)个节点，再第二次遍历找到该节点的前驱进行删除。
-
这种方法的局限性在于：需要两次遍历链表，时间复杂度为O(2L)，虽然仍然是线性复杂度，但不够优雅，且需要额外存储链表长度信息。
-
-
优化思路：双指针一次遍历：
-
优化方向1：利用快慢指针制造固定间隔：使用两个指针
left和right，让right先向前移动n步，此时两个指针之间相隔n个节点。然后同时移动两个指针，当right到达链表末尾时，left恰好指向待删除节点的前驱节点。 -
优化方向2：引入哑节点处理边界情况：在链表头部之前添加一个哑节点（dummy node），使得删除头节点的操作可以统一处理，无需特殊判断
head是否为待删除节点的情况。
-
-
关键策略优势：
-
策略带来的具体好处1：一次遍历完成操作：仅需遍历链表一次，时间复杂度为O(L)，相比两次遍历法效率更高，尤其适用于链表长度较大或需要多次操作的场景。
-
策略带来的具体好处2：优雅处理边界情况：通过哑节点的引入，当需要删除原链表的头节点时，
left会指向哑节点，删除操作left.next = left.next.next依然正确，无需额外的条件判断。 -
策略带来的具体好处3：空间复杂度为O(1)：仅使用了两个指针变量和一个哑节点，没有使用额外的数据结构，空间效率最优。
-
策略带来的具体好处4：指针间隔固定：通过让
right先走n步，保证了left和right之间始终保持n个节点的距离，这是算法的核心技巧，使得right到达末尾时left正好指向目标位置。
-
-
具体实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
# 创建哑节点，其next指向原链表头，方便处理删除头节点的情况
left = right = d = ListNode(next=head)
# 让right指针先移动n步，使left和right之间相隔n个节点
for _ in range(n):
right = right.next
# 同时移动left和right，直到right到达链表最后一个节点
while right.next:
left = left.next
right = right.next
# 此时left指向待删除节点的前驱节点，执行删除操作
left.next = left.next.next
# 返回原链表的头节点（跳过哑节点）
return d.next
24. 两两交换链表中的节点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
node0 = d = ListNode(next = head)
node1 = head
while node1 and node1.next:
node2 = node1.next
node3 = node2.next
node0.next = node2
node2.next = node1
node1.next = node3
node0 = node1
node1 = node3
return d.next思考过程：
-
递归与迭代的初步思考：
-
最初想到的简单解法是使用递归：每次交换前两个节点，然后递归处理剩余链表。这种方法直观易懂，但存在函数调用栈开销，对于超长链表可能导致栈溢出。
-
另一种简单思路是直接遍历链表，每次交换相邻节点，但需要谨慎处理指针指向，容易出错。
-
-
迭代指针操作的优化思路：
-
优化方向1：使用虚拟头节点简化边界处理：通过在链表头部添加一个虚拟节点（dummy node），将头节点的交换统一到循环逻辑中，避免单独处理头节点的特殊情况。
-
优化方向2：利用多指针记录关键位置：使用三个指针（node0、node1、node2）分别指向当前待交换节点对的前一个节点、第一个节点和第二个节点，配合node3记录后续链表头，实现精准的指针重定向。
-
-
关键策略优势：
-
策略带来的具体好处1：统一处理逻辑：虚拟头节点的使用使得所有节点交换（包括头节点）都遵循相同的指针操作模式，无需额外的条件判断。
-
策略带来的具体好处2：空间复杂度优化：迭代解法只使用常数级别的额外空间（O(1)），相比递归的O(n)栈空间更优，避免了栈溢出风险。
-
策略带来的具体好处3：指针操作的可读性：通过node0、node1、node2、node3的命名清晰表达了各自角色，使复杂的指针重定向变得易于理解和维护。
-
-
具体实现：
class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: # 创建虚拟头节点，方便处理头节点交换的情况 # node0初始指向虚拟头节点，node1指向原头节点 node0 = d = ListNode(next=head) node1 = head # 循环条件：至少有两个节点可以交换 while node1 and node1.next: # 记录关键节点位置 node2 = node1.next # 第二个节点（待交换对中的后一个） node3 = node2.next # 第三个节点（下一对的起始节点） # 执行节点交换的核心指针操作 # 步骤1: 让前一个节点指向第二个节点 node0.next = node2 # 步骤2: 让第二个节点指向第一个节点 node2.next = node1 # 步骤3: 让第一个节点指向后续节点 node1.next = node3 # 移动指针到下一对节点的前驱和起始位置 node0 = node1 # node0移动到当前交换对的第一节点（即将成为下一对的前驱） node1 = node3 # node1移动到下一对的起始节点 # 返回虚拟头节点的下一个节点，即交换后的链表头 return d.next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
node1 = head
node2 = node1.next
node3 = node2.next
node2.next = node1
node1.next = self.swapPairs(node3)
return node2思考过程：
-
递归法的直接实现：最初想到通过迭代方式遍历链表，使用多个指针进行节点交换，但迭代方法需要处理复杂的指针更新逻辑，特别是需要维护前驱节点信息，容易在边界条件（如奇数个节点）时出现错误。
-
递归优化思路：
-
优化方向1：问题分解与递归：将问题转化为重复的子问题——每两个节点为一组进行交换，剩余部分作为更小规模的相同问题。递归函数
swapPairs只需要处理当前两个节点的交换，并递归处理剩余链表，无需维护外部状态。 -
优化方向2：递归栈与回溯：利用递归调用栈天然的后进先出特性，让深层递归先处理末尾节点对，然后逐层返回时完成交换，确保链表连接正确，避免迭代方法中需要多次遍历的问题。
-
-
关键策略优势：
-
逻辑清晰简洁：将复杂的链表指针操作拆分为三个明确步骤——保存第三个节点、交换前两个节点、递归处理剩余部分，代码结构清晰易懂。
-
自动处理边界：递归终止条件（
head is None or head.next is None）统一处理了空链表和奇数个节点的特殊情况，无需额外判断。 -
避免指针丢失：通过在交换前保存
node3（即node2.next），确保递归调用时能够正确传入剩余链表的头节点，防止链表断裂。
-
-
具体实现：
class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: # 递归终止条件：空链表或只有一个节点，无需交换 if head is None or head.next is None: return head # 定位当前需要交换的两个节点及其后续节点 node1 = head # 第一个节点 node2 = node1.next # 第二个节点 node3 = node2.next # 第三个节点（下一组的开始） # 核心交换逻辑： # 1. 将第二个节点指向第一个节点 node2.next = node1 # 2. 将第一个节点指向递归处理后的后续链表 node1.next = self.swapPairs(node3) # 返回新的头节点（原第二个节点） return node2
25. K 个一组翻转链表
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
n = 0
cur = head
while cur:
n += 1
cur = cur.next
p0 = dummy = ListNode(next=head)
pre = None
cur = head
while n >= k:
n -= k
for _ in range(k):
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
nxt = p0.next
nxt.next = cur
p0.next = pre
p0 = nxt
return dummy.next思考过程：
-
初步思路：逐段翻转，每次查找剩余节点：
最初想到的简单解法是遍历链表，每遇到 k 个节点就进行一次翻转。这种方法的局限性在于，为了判断剩余节点是否足够 k 个，需要每次在翻转前都进行一次遍历计数，导致时间复杂度较高，或者代码结构变得复杂。 -
优化思路：预计算长度 + 迭代翻转：
-
优化方向1：如何转化问题、降低复杂度或提高效率：
首先，通过一次完整的遍历计算出链表的总长度n。这样，在后续的翻转过程中，我们只需要知道当前还剩余多少节点（n每次减去k），即可快速判断是否还有足够的节点进行下一轮翻转，避免了每次翻转前的重复计数。 -
优化方向2：使用了什么关键数据结构或算法思想：
本题的核心是链表的原地翻转算法。使用了 虚拟头节点 (Dummy Node) 来简化边界处理，特别是当head节点本身也需要被翻转时。同时，采用 迭代法 实现局部链表的反转，并通过指针p0来连接每一段翻转后的链表。
-
-
关键策略优势：
-
策略带来的具体好处1：去重与简化：
使用dummy虚拟头节点，使得第一个分组（k 个节点）的翻转操作可以与后续分组保持完全一致的代码逻辑，无需特殊处理头指针的变化，大大降低了编码难度和出错概率。 -
策略带来的具体好处2：查找加速与逻辑清晰：
通过预先计算链表长度n，我们将“判断剩余节点是否足够”这个操作从 O(k) 的时间复杂度降为 O(1)。这使得主循环的逻辑非常清晰：只要n >= k，就执行一次翻转，然后n减k，继续下一次循环。
-
-
具体实现
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 1. 第一步：计算链表总长度
n = 0
cur = head
while cur:
n += 1
cur = cur.next
# 2. 初始化指针
# dummy 是虚拟头节点，指向原链表的头，方便处理头节点的变化
# p0 是上一段翻转后链表的最后一个节点，初始指向 dummy
p0 = dummy = ListNode(next=head)
# pre 用于局部翻转时的前驱节点，初始为 None
pre = None
# cur 是当前正在处理的节点，初始指向原链表头
cur = head
# 3. 主循环：当剩余节点数大于等于 k 时，继续翻转
while n >= k:
# 每处理一组，剩余节点数减少 k
n -= k
# 3.1 翻转当前 k 个节点
# 注意：翻转时，cur 指向的是本组的第一个节点，pre 是前一组翻转后的尾节点（初始为None）
for _ in range(k):
nxt = cur.next # 保存下一个节点
cur.next = pre # 反转当前节点的指向
pre = cur # pre 移动到当前节点
cur = nxt # cur 移动到下一个节点
# 3.2 将翻转后的链表重新连接回主链表
# 此时：
# pre 指向的是本组翻转后的头节点
# cur 指向的是下一组的第一个节点（如果存在）
# p0 指向的是上一组的尾节点（初始为 dummy）
# nxt 是上一组尾节点的下一个节点，即本组翻转前的头节点，也是翻转后的尾节点
# 获取上一组尾节点的下一个节点（即翻转后本组的尾节点）
nxt = p0.next
# 将本组的尾节点（nxt）连接到下一组的头节点（cur）
nxt.next = cur
# 将上一组的尾节点（p0）连接到本组的新头节点（pre）
p0.next = pre
# 移动 p0 到本组的尾节点（即 nxt），为下一轮翻转做准备
p0 = nxt
# 返回虚拟头节点的下一个节点，即真正的链表头
return dummy.next
138. 复制带随机指针的链表
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
node1 = head
while node1:
node1.next = Node(node1.val, node1.next)
node1 = node1.next.next
node2 = head
while node2:
if node2.random:
node2.next.random = node2.random.next
node2 = node2.next.next
tail = d = Node(0, head)
cur = head
while cur:
copy = cur.next
tail.next = copy
cur.next = copy.next
cur = cur.next
tail = tail.next
return d.next思考过程：
-
初步思路：两次遍历 + 哈希表映射：
最初想到的简单解法是使用哈希表来存储原节点到新节点的映射关系。第一次遍历创建所有新节点并建立映射，第二次遍历根据原节点的random指针，通过哈希表找到对应的新节点进行连接。这种方法的局限性在于需要额外的 O(n) 空间来存储哈希表，空间复杂度较高。 -
优化思路：原地复制 + 拆分链表：
-
优化方向1：如何转化问题、降低复杂度或提高效率：
将问题转化为三步操作：首先在原链表中每个节点后插入一个复制节点，然后利用原节点的random关系设置复制节点的random指针，最后将复制节点从原链表中拆分出来形成新链表。这样避免了使用额外的哈希表空间。 -
优化方向2：使用了什么关键数据结构或算法思想：
本题的核心是链表的原地复制和拆分技巧。通过将复制节点插入到原节点之后，建立了一种隐式的映射关系（原节点与复制节点相邻），这样在设置random指针时，可以直接通过原节点.random.next找到对应的复制节点，无需哈希表。最后通过三指针分离法将原链表和复制链表分离。
-
-
关键策略优势：
-
策略带来的具体好处1：空间优化：
将空间复杂度从 O(n) 降低到 O(1)，只使用了常数级别的额外空间（几个指针变量），完全避免了哈希表的开销。 -
策略带来的具体好处2：逻辑清晰：
将复杂问题分解为三个独立的步骤（插入、设置 random、拆分），每一步的职责都非常明确，易于理解和实现，降低了出错概率。
-
-
具体实现
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
# 处理空链表的情况
if not head:
return None
# 第一步：在原链表的每个节点后面插入一个复制节点
# 例如：原链表 A -> B -> C
# 插入后：A -> A' -> B -> B' -> C -> C'
node1 = head
while node1:
# 创建复制节点，值为原节点的值，next 指向原节点的下一个节点
node1.next = Node(node1.val, node1.next)
# 移动到下一个原节点（跳过刚插入的复制节点）
node1 = node1.next.next
# 第二步：设置复制节点的 random 指针
node2 = head
while node2:
# 如果原节点的 random 指针不为空
if node2.random:
# 复制节点的 random 应该指向原节点 random 的复制节点
# 由于我们在每个原节点后都插入了复制节点，所以 node2.random.next 就是原节点 random 的复制节点
node2.next.random = node2.random.next
# 移动到下一个原节点
node2 = node2.next.next
# 第三步：将原链表和复制链表分离
# 使用虚拟头节点 dummy 简化新链表的构建
# tail 指向新链表的最后一个节点，d 是虚拟头节点
tail = d = Node(0, head)
cur = head
while cur:
# 获取当前节点的复制节点
copy = cur.next
# 将复制节点连接到新链表
tail.next = copy
# 恢复原链表：将原节点的 next 指向复制节点的下一个节点（即下一个原节点）
cur.next = copy.next
# 移动 cur 到下一个原节点
cur = cur.next
# 移动 tail 到新链表的最后一个节点
tail = tail.next
# 返回新链表的头节点
return d.next
148. 排序链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def getLength(self, head:Optional[ListNode]) -> int:
l = 0
while head:
l += 1
head = head.next
return l
def split(self, head: Optional[ListNode], size: int) -> Optional[ListNode]:
for _ in range(size - 1):
if head is None:
break
head = head.next
if head is None or head.next is None:
return None
next_head = head.next
head.next = None
return next_head
def merge(self, head1: Optional[ListNode], head2: Optional[ListNode]) -> Optional[ListNode]:
cur = d = ListNode()
while head1 and head2:
if head1.val < head2.val:
cur.next = head1
head1 = head1.next
else:
cur.next = head2
head2 = head2.next
cur = cur.next
cur.next = head1 or head2
while cur.next:
cur = cur.next
return d.next, cur
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
length = self.getLength(head)
d = ListNode(next = head)
step = 1
while step < length:
new_tail = d
cur = d.next
while cur:
head1 = cur
head2 = self.split(head1, step)
cur = self.split(head2, step)
head, tail = self.merge(head1, head2)
new_tail.next = head
new_tail = tail
step *= 2
return d.next思考过程：
-
初步思路：递归归并排序：
最初想到的简单解法是使用递归的归并排序：找到链表的中点，将链表分成两半，递归排序左右两部分，然后合并。这种方法的局限性在于递归需要 O(log n) 的栈空间，并且每次找中点都需要 O(n) 的遍历，整体时间复杂度为 O(n log n)，空间复杂度为 O(log n)。 -
优化思路：自底向上的归并排序（迭代法）：
-
优化方向1：如何转化问题、降低复杂度或提高效率：
将递归的归并排序转化为迭代的自底向上归并排序。从步长为 1 开始，每次将链表中相邻的两个长度为 step 的有序子链表合并，然后步长加倍，直到步长大于等于链表总长度。这样避免了递归带来的额外栈空间开销。 -
优化方向2：使用了什么关键数据结构或算法思想：
本题的核心是链表的自底向上归并排序算法。使用了虚拟头节点 (Dummy Node) 来简化头节点的处理，通过步长倍增的策略逐步扩大有序子链表的长度。关键操作包括：-
split函数：将链表从指定位置切分，返回剩余部分的头节点 -
merge函数：合并两个有序链表，返回合并后的头节点和尾节点 -
主循环：按步长遍历链表，两两合并相邻的有序子链表
-
-
-
关键策略优势：
-
策略带来的具体好处1：空间优化：
将空间复杂度从递归的 O(log n) 降低到 O(1)，只使用了常数级别的额外空间（几个指针变量），完全避免了递归栈的开销。 -
策略带来的具体好处2：逻辑清晰且高效：
通过步长倍增的方式，每一轮处理都会将有序子链表的长度翻倍，总共需要 O(log n) 轮。每一轮中需要遍历整个链表一次，因此总时间复杂度为 O(n log n)，与递归归并排序相同，但常数更小且不存在栈溢出风险。
-
-
具体实现
class Solution:
def getLength(self, head: Optional[ListNode]) -> int:
"""获取链表的长度"""
l = 0
while head:
l += 1
head = head.next
return l
def split(self, head: Optional[ListNode], size: int) -> Optional[ListNode]:
"""
将链表从指定位置切分
参数:
head: 当前链表的头节点
size: 需要保留的节点数量
返回:
切分后剩余部分的头节点（如果剩余部分不存在则返回 None）
"""
# 移动到第 size 个节点（保留 size 个节点）
for _ in range(size - 1):
if head is None:
break
head = head.next
# 如果没有剩余节点，返回 None
if head is None or head.next is None:
return None
# 记录剩余部分的头节点，并将当前部分的尾部断开
next_head = head.next
head.next = None
return next_head
def merge(self, head1: Optional[ListNode], head2: Optional[ListNode]) -> tuple:
"""
合并两个有序链表
参数:
head1: 第一个有序链表的头节点
head2: 第二个有序链表的头节点
返回:
(合并后链表的头节点, 合并后链表的尾节点)
"""
# 使用虚拟头节点简化合并过程
cur = d = ListNode()
# 两路归并
while head1 and head2:
if head1.val < head2.val:
cur.next = head1
head1 = head1.next
else:
cur.next = head2
head2 = head2.next
cur = cur.next
# 连接剩余部分
cur.next = head1 or head2
# 移动到新链表的尾部
while cur.next:
cur = cur.next
return d.next, cur
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
"""
自底向上的归并排序（迭代法）
参数:
head: 原链表的头节点
返回:
排序后链表的头节点
"""
# 获取链表总长度
length = self.getLength(head)
# 虚拟头节点，简化边界处理
d = ListNode(next=head)
# 当前归并的步长（每个有序子链表的长度）
step = 1
# 当步长小于总长度时，继续归并
while step < length:
# new_tail 指向当前轮次已经归并完成的部分的尾节点
new_tail = d
# cur 指向当前轮次要处理的起始节点
cur = d.next
# 遍历整个链表，按步长两两归并
while cur:
# 第一个有序子链表的头节点
head1 = cur
# 切分出第二个有序子链表的头节点（长度为 step）
head2 = self.split(head1, step)
# 切分出下一对子链表的起始节点（跳过当前的两个子链表）
cur = self.split(head2, step)
# 合并两个有序子链表
head, tail = self.merge(head1, head2)
# 将合并后的链表连接到结果链表中
new_tail.next = head
# 更新 new_tail 到当前合并后链表的尾部
new_tail = tail
# 步长加倍，进入下一轮归并
step *= 2
# 返回排序后的链表头节点
return d.next
23. 合并 K 个升序链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def merge(self, head1: Optional[ListNode], head2: Optional[ListNode]) -> Optional[ListNode]:
cur = d = ListNode()
while head1 and head2:
if head1.val < head2.val:
cur.next = head1
head1 = head1.next
else:
cur.next = head2
head2 = head2.next
cur = cur.next
cur.next = head1 or head2
return d.next
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
m = len(lists)
if m == 0:
return None
step = 1
while step < m:
for i in range(0, m - step, step * 2):
lists[i] = self.merge(lists[i], lists[i + step])
step *= 2
return lists[0]思考过程：
-
初步思路：顺序合并：
最初想到的简单解法是维护一个结果链表，然后依次将每个链表与结果链表进行两两合并。这种方法的局限性在于时间复杂度较高，假设总节点数为 N，第一个链表与结果合并需要 O(N₁)，第二个合并需要 O(N₁+N₂)，依此类推，总时间复杂度为 O(kN)，其中 k 是链表个数。 -
优化思路：两两配对归并（分治思想）：
-
优化方向1：如何转化问题、降低复杂度或提高效率：
将问题转化为多轮的两两归并过程。第一轮将第 0 个和第 1 个合并，第 2 个和第 3 个合并，...；第二轮将第一轮的结果再两两合并；重复直到只剩一个链表。这样每一轮参与合并的链表数量减半，总共需要 O(log k) 轮。 -
优化方向2：使用了什么关键数据结构或算法思想：
本题的核心是自底向上的分治归并算法（也称为多路归并的分治版本）。使用了原地合并的策略，将合并结果存储在原数组的起始位置（lists[i]），避免了额外的空间开销。关键操作包括：-
merge函数：标准的两个有序链表合并算法 -
主循环：通过步长倍增的方式控制每一轮需要合并的链表对
-
-
-
关键策略优势：
-
策略带来的具体好处1：时间复杂度优化：
将时间复杂度从顺序合并的 O(kN) 降低到 O(N log k)。其中 N 是所有链表的总节点数，k 是链表个数。这是因为每层归并需要处理全部 N 个节点，总共 log k 层。 -
策略带来的具体好处2：空间效率高：
空间复杂度为 O(1)（不考虑递归栈）或 O(log k)（如果考虑递归则使用递归分治）。本实现采用迭代方式，只使用了常数级别的额外空间（几个指针变量和临时变量），无需使用优先队列（堆）所需的 O(k) 空间。
-
-
具体实现
class Solution:
def merge(self, head1: Optional[ListNode], head2: Optional[ListNode]) -> Optional[ListNode]:
"""
合并两个有序链表（标准的两路归并）
参数:
head1: 第一个有序链表的头节点
head2: 第二个有序链表的头节点
返回:
合并后链表的头节点
"""
# 使用虚拟头节点简化边界处理
cur = d = ListNode()
# 同时遍历两个链表，每次取较小的节点
while head1 and head2:
if head1.val < head2.val:
cur.next = head1
head1 = head1.next
else:
cur.next = head2
head2 = head2.next
cur = cur.next
# 连接剩余部分（其中一个链表已经为空）
cur.next = head1 or head2
# 返回虚拟头节点的下一个节点（真正的头节点）
return d.next
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
"""
合并 K 个升序链表（自底向上的分治归并）
参数:
lists: 包含 K 个链表头节点的列表
返回:
合并后链表的头节点
"""
m = len(lists)
# 边界情况：空列表
if m == 0:
return None
# step 表示当前轮次中，每对合并的链表之间的间隔（步长）
# 初始步长为 1，即合并相邻的两个链表
step = 1
# 当步长小于总链表数时，继续归并
while step < m:
# 遍历列表，两两合并
# i 的步长是 step * 2，因为每对合并后会跳过两个步长
# 注意：range 的结束条件是 m - step，确保 i + step 不越界
for i in range(0, m - step, step * 2):
# 将第 i 个链表与第 i+step 个链表合并
# 合并结果存回 lists[i]（原地存储，节省空间）
lists[i] = self.merge(lists[i], lists[i + step])
# 步长翻倍，进入下一轮归并
step *= 2
# 最终所有链表归并到 lists[0] 中
return lists[0]
146. LRU 缓存
class Node:
__slots__ = 'prev', 'next', 'key', 'value'
def __init__(self, key=0, value=0):
self.key = key
self.value = value
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.dummy = Node()
self.dummy.prev = self.dummy
self.dummy.next = self.dummy
self.key_to_node = {}
def get(self, key: int) -> int:
node = self.get_node(key)
return node.value if node else -1
def put(self, key: int, value: int) -> None:
node = self.get_node(key)
if node:
node.value = value
return
self.key_to_node[key] = node = Node(key, value)
self.push_front(node)
if len(self.key_to_node) > self.capacity:
back_node = self.dummy.prev
del self.key_to_node[back_node.key]
self.remove(back_node)
def get_node(self, key: int) -> Optional[Node]:
if key not in self.key_to_node:
return None
node = self.key_to_node[key]
self.remove(node)
self.push_front(node)
return node
def remove(self, x: Node) -> None:
x.prev.next = x.next
x.next.prev = x.prev
def push_front(self, x: Node) -> None:
x.prev = self.dummy
x.next = self.dummy.next
x.prev.next = x
x.next.prev = x思考过程：
-
初步思路：使用有序字典（如 Python 的 OrderedDict）：
最初想到的简单解法是直接使用 Python 标准库中的OrderedDict或collections.OrderedDict，它能够保持键值对的插入顺序。get操作时访问后需要将键值对移动到末尾，put操作时如果容量超限则删除开头的元素。这种方法的局限性在于虽然代码简洁，但无法体现 LRU 缓存的核心实现原理，且依赖语言特性，不适合在面试或底层实现场景中使用。 -
优化思路：双向链表 + 哈希表：
-
优化方向1：如何转化问题、降低复杂度或提高效率：
将问题拆解为两个核心需求：快速查找（O(1) 时间）和快速维护访问顺序（O(1) 时间）。使用哈希表来存储键到节点的映射，实现 O(1) 的查找；使用双向链表来维护节点的访问顺序，实现 O(1) 的节点移动和删除。双向链表比单向链表的优势在于删除节点时不需要知道前驱节点。 -
优化方向2：使用了什么关键数据结构或算法思想：
本题的核心是双向链表 + 哈希表的组合数据结构。使用虚拟头尾节点（哨兵节点） 来简化边界处理，避免空指针判断。LRU 策略的实质是：最近使用的节点移动到链表头部（最热数据），最久未使用的节点自然沉淀到链表尾部，淘汰时直接删除尾部节点即可。
-
-
关键策略优势：
-
策略带来的具体好处1：所有操作 O(1) 时间复杂度：
get和put操作的时间复杂度均为 O(1)。哈希表提供 O(1) 的查找，双向链表的插入、删除、移动操作也都是 O(1) 的。 -
策略带来的具体好处2：使用 slots 优化内存：
Node类中使用了__slots__ = 'prev', 'next', 'key', 'value'，这可以显著减少每个节点对象的内存占用（不再需要__dict__），提高性能，在缓存容量较大时效果明显。 -
策略带来的具体好处3：哨兵节点简化边界：
使用虚拟头节点dummy，并将其prev和next都指向自身来初始化空链表。这样在插入和删除操作时无需判断链表是否为空，代码更简洁且不易出错。
-
-
具体实现
class Node:
# 使用 __slots__ 减少内存占用，提高访问速度
__slots__ = 'prev', 'next', 'key', 'value'
def __init__(self, key=0, value=0):
self.key = key
self.value = value
# prev 和 next 在插入时由 LRUCache 的方法设置
class LRUCache:
def __init__(self, capacity: int):
"""
初始化 LRU 缓存
参数:
capacity: 缓存的最大容量
"""
self.capacity = capacity
# 哨兵节点（虚拟头节点），简化边界处理
# 初始时，dummy.prev 指向尾部（最久未使用），dummy.next 指向头部（最近使用）
self.dummy = Node()
self.dummy.prev = self.dummy
self.dummy.next = self.dummy
# 哈希表：key -> Node，实现 O(1) 查找
self.key_to_node = {}
def get(self, key: int) -> int:
"""
获取缓存中的值
参数:
key: 键
返回:
如果 key 存在则返回对应的值，否则返回 -1
"""
node = self.get_node(key)
return node.value if node else -1
def put(self, key: int, value: int) -> None:
"""
插入或更新缓存
参数:
key: 键
value: 值
"""
# 尝试获取节点（如果存在，get_node 会将其移动到链表头部）
node = self.get_node(key)
if node:
# key 已存在，更新值即可
node.value = value
return
# key 不存在，创建新节点
self.key_to_node[key] = node = Node(key, value)
# 将新节点插入到链表头部（最近使用的位置）
self.push_front(node)
# 如果超出容量，淘汰最久未使用的节点（链表尾部）
if len(self.key_to_node) > self.capacity:
# 尾部节点即 dummy.prev
back_node = self.dummy.prev
# 从哈希表中删除
del self.key_to_node[back_node.key]
# 从链表中删除
self.remove(back_node)
def get_node(self, key: int) -> Optional[Node]:
"""
获取节点并将其移动到链表头部（标记为最近使用）
参数:
key: 键
返回:
对应的节点，如果不存在则返回 None
"""
if key not in self.key_to_node:
return None
node = self.key_to_node[key]
# 先从当前位置移除
self.remove(node)
# 再插入到头部
self.push_front(node)
return node
def remove(self, x: Node) -> None:
"""
从链表中移除节点 x
参数:
x: 待移除的节点
"""
# 将 x 的前驱和后继连接起来
x.prev.next = x.next
x.next.prev = x.prev
def push_front(self, x: Node) -> None:
"""
将节点 x 插入到链表头部（dummy 之后）
参数:
x: 待插入的节点
"""
# 将 x 插入到 dummy 和 dummy.next 之间
x.prev = self.dummy
x.next = self.dummy.next
# 更新相邻节点的指针
x.prev.next = x
x.next.prev = x
这里是“一人公司”的成长家园。我们提供从产品曝光、技术变现到法律财税的全栈内容，并连接云服务、办公空间等稀缺资源，助你专注创造，无忧运营。
更多推荐
4
0- 0
已为社区贡献1条内容
所有评论(0)