链表
In [ ]:
Copied!
class ListNode:
"""
self.val 和 self.next 表示实例的属性
而val 和 next是参数名
通过 __init__ 方法初始化实例属性
通过 __str__ 和 __repr__ 方法定义实例的字符串表示
通过 show_chain 方法显示完整链表链
"""
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __str__(self):
return f"[{self.val}]"
def __repr__(self):
return f"ListNode({self.val})"
def show_chain(self):
"""显示完整链表链"""
result = []
current = self
while current:
result.append(str(current))
current = current.next
return " -> ".join(result) + " -> None"
# 创建链表
a = head = ListNode(1)
b = head.next = ListNode(2)
c = head.next.next = ListNode(3)
# 不同的显示方式
print(a) # [1]
print(repr(a)) # ListNode(1)
print(a.show_chain()) # [1] -> [2] -> [3] -> None
class ListNode:
"""
self.val 和 self.next 表示实例的属性
而val 和 next是参数名
通过 __init__ 方法初始化实例属性
通过 __str__ 和 __repr__ 方法定义实例的字符串表示
通过 show_chain 方法显示完整链表链
"""
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __str__(self):
return f"[{self.val}]"
def __repr__(self):
return f"ListNode({self.val})"
def show_chain(self):
"""显示完整链表链"""
result = []
current = self
while current:
result.append(str(current))
current = current.next
return " -> ".join(result) + " -> None"
# 创建链表
a = head = ListNode(1)
b = head.next = ListNode(2)
c = head.next.next = ListNode(3)
# 不同的显示方式
print(a) # [1]
print(repr(a)) # ListNode(1)
print(a.show_chain()) # [1] -> [2] -> [3] -> None
[1] ListNode(1) [1] -> [2] -> [3] -> None
相交链表（LeetCode 160）¶
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 NULL
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
In [ ]:
Copied!
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
from typing import List, Optional
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
"""
双指针法求相交链表
核心思想：
让两个指针分别遍历两条链表，当到达末尾时切换到另一条链表
由于总路径长度相同，必然会在相交点相遇（如果存在）
时间复杂度：O(m + n)
空间复杂度：O(1)
"""
# 边界情况：任一链表为空则不可能相交
if not headA or not headB:
return None
# 初始化两个指针
pointerA, pointerB = headA, headB
# 核心循环：当两指针不相等时继续移动
while pointerA != pointerB:
# 指针A：走完链表A后切换到链表B
pointerA = pointerA.next if pointerA else headB
# 指针B：走完链表B后切换到链表A
pointerB = pointerB.next if pointerB else headA
# 返回相交点（如果存在）或None（如果不相交）
return pointerA
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
from typing import List, Optional
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
"""
双指针法求相交链表
核心思想：
让两个指针分别遍历两条链表，当到达末尾时切换到另一条链表
由于总路径长度相同，必然会在相交点相遇（如果存在）
时间复杂度：O(m + n)
空间复杂度：O(1)
"""
# 边界情况：任一链表为空则不可能相交
if not headA or not headB:
return None
# 初始化两个指针
pointerA, pointerB = headA, headB
# 核心循环：当两指针不相等时继续移动
while pointerA != pointerB:
# 指针A：走完链表A后切换到链表B
pointerA = pointerA.next if pointerA else headB
# 指针B：走完链表B后切换到链表A
pointerB = pointerB.next if pointerB else headA
# 返回相交点（如果存在）或None（如果不相交）
return pointerA
In [ ]:
Copied!
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __repr__(self):
return f"ListNode({self.val})"
from typing import Optional
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
"""
双指针法求相交链表
核心思想：
让两个指针分别遍历两条链表，当到达末尾时切换到另一条链表
由于总路径长度相同，必然会在相交点相遇（如果存在）
时间复杂度：O(m + n)
空间复杂度：O(1)
"""
if not headA or not headB:
return None
pointerA, pointerB = headA, headB
while pointerA != pointerB:
pointerA = pointerA.next if pointerA else headB
pointerB = pointerB.next if pointerB else headA
return pointerA
intersection = ListNode(3, ListNode(4))
headA = ListNode(10, intersection)
headB = ListNode(22, intersection)
solution = Solution()
# 求解相交点
result = solution.getIntersectionNode(headA, headB)
print(f"求解的相交点: {result}")
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __repr__(self):
return f"ListNode({self.val})"
from typing import Optional
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
"""
双指针法求相交链表
核心思想：
让两个指针分别遍历两条链表，当到达末尾时切换到另一条链表
由于总路径长度相同，必然会在相交点相遇（如果存在）
时间复杂度：O(m + n)
空间复杂度：O(1)
"""
if not headA or not headB:
return None
pointerA, pointerB = headA, headB
while pointerA != pointerB:
pointerA = pointerA.next if pointerA else headB
pointerB = pointerB.next if pointerB else headA
return pointerA
intersection = ListNode(3, ListNode(4))
headA = ListNode(10, intersection)
headB = ListNode(22, intersection)
solution = Solution()
# 求解相交点
result = solution.getIntersectionNode(headA, headB)
print(f"求解的相交点: {result}")
求解的相交点: ListNode(3)
In [2]:
Copied!
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
"""
迭代双指针法反转链表
时间复杂度 O(N) ： 遍历链表使用线性大小时间。
空间复杂度 O(1) ： 变量 pre 和 cur 使用常数大小额外空间
"""
def reverseList(self, head: ListNode) -> ListNode:
cur, pre = head, None
while cur:
tmp = cur.next # 暂存后继节点 cur.next
cur.next = pre # 修改 next 引用指向
pre = cur # pre 暂存 cur
cur = tmp # cur 访问下一节点
return pre
# 构造链表A: 1 -> 4
headA = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
solution = Solution()
# 反转链表
reversed_head = solution.reverseList(headA)
print(f"反转后的链表头节点: {reversed_head.val}")
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
"""
迭代双指针法反转链表
时间复杂度 O(N) ： 遍历链表使用线性大小时间。
空间复杂度 O(1) ： 变量 pre 和 cur 使用常数大小额外空间
"""
def reverseList(self, head: ListNode) -> ListNode:
cur, pre = head, None
while cur:
tmp = cur.next # 暂存后继节点 cur.next
cur.next = pre # 修改 next 引用指向
pre = cur # pre 暂存 cur
cur = tmp # cur 访问下一节点
return pre
# 构造链表A: 1 -> 4
headA = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
solution = Solution()
# 反转链表
reversed_head = solution.reverseList(headA)
print(f"反转后的链表头节点: {reversed_head.val}")
反转后的链表头节点: 4
234. 回文链表¶
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表(回文序列是向前和向后读都相同的序列)。如果是，返回 true ；否则，返回 false 。
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
In [ ]:
Copied!
from typing import Optional
"""
利用 O(1) 额外空间判断单链表是否为回文链表
核心框架：
1. **找中点**：快慢指针（`middleNode`）。
2. **反转后半段**：原地反转（`reverseList`）。
3. **比对两半**：逐节点比较（`isPalindrome`）。
时间复杂度：O(n) — 所有步骤都只遍历链表一次级别
空间复杂度：O(1) — 只用到若干指针变量
"""
class ListNode:
def __init__(self, val: int = 0, next: "Optional[ListNode]" = None):
self.val = val
self.next = next
class Solution:
# ---------------- 1. 寻找链表中点 ----------------
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
"""
快慢指针法（Floyd 双指针）
slow 每次走 1 步，fast 每次走 2 步；当 fast 到达链尾时，slow 正好位于中点。
- **奇数长度**：slow 落在真正的中心节点
- **偶数长度**：slow 落在两个中间节点的第二个节点，符合后续「反转后半段」的需要
时间复杂度：O(n)（一次遍历）
空间复杂度：O(1)（常数指针）
"""
slow = fast = head
while fast and fast.next:
slow = slow.next # 走 1 步
fast = fast.next.next # 走 2 步
return slow # 返回中点（或下中点）
# ---------------- 2. 原地反转链表 ----------------
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
"""
迭代法反转单链表
依次把当前节点 `cur` 的 next 指向前驱 `pre`，并向前推进
时间复杂度：O(n)
空间复杂度：O(1)
"""
pre, cur = None, head
while cur:
nxt = cur.next # 暂存后继
cur.next = pre # 反转指向
pre = cur
cur = nxt
return pre # 新的表头
# ---------------- 3. 回文判定主函数 ----------------
def isPalindrome(self, head: Optional[ListNode]) -> bool:
"""
判断链表是否为回文
步骤
① 找到中点 `mid`。
② 将 `mid` 及其后的链表反转，得到新链表头 `head2`。
③ 用两个指针同步遍历原链表前半段 (`head`) 与反转后的后半段 (`head2`)，逐节点比较值。
④ 若全部相等则为回文；否则返回 False。
时间复杂度：O(n)
空间复杂度：O(1)
"""
# ① 找中点
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
from typing import Optional
"""
利用 O(1) 额外空间判断单链表是否为回文链表
核心框架：
1. **找中点**：快慢指针（`middleNode`）。
2. **反转后半段**：原地反转（`reverseList`）。
3. **比对两半**：逐节点比较（`isPalindrome`）。
时间复杂度：O(n) — 所有步骤都只遍历链表一次级别
空间复杂度：O(1) — 只用到若干指针变量
"""
class ListNode:
def __init__(self, val: int = 0, next: "Optional[ListNode]" = None):
self.val = val
self.next = next
class Solution:
# ---------------- 1. 寻找链表中点 ----------------
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
"""
快慢指针法（Floyd 双指针）
slow 每次走 1 步，fast 每次走 2 步；当 fast 到达链尾时，slow 正好位于中点。
- **奇数长度**：slow 落在真正的中心节点
- **偶数长度**：slow 落在两个中间节点的第二个节点，符合后续「反转后半段」的需要
时间复杂度：O(n)（一次遍历）
空间复杂度：O(1)（常数指针）
"""
slow = fast = head
while fast and fast.next:
slow = slow.next # 走 1 步
fast = fast.next.next # 走 2 步
return slow # 返回中点（或下中点）
# ---------------- 2. 原地反转链表 ----------------
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
"""
迭代法反转单链表
依次把当前节点 `cur` 的 next 指向前驱 `pre`，并向前推进
时间复杂度：O(n)
空间复杂度：O(1)
"""
pre, cur = None, head
while cur:
nxt = cur.next # 暂存后继
cur.next = pre # 反转指向
pre = cur
cur = nxt
return pre # 新的表头
# ---------------- 3. 回文判定主函数 ----------------
def isPalindrome(self, head: Optional[ListNode]) -> bool:
"""
判断链表是否为回文
步骤
① 找到中点 `mid`。
② 将 `mid` 及其后的链表反转，得到新链表头 `head2`。
③ 用两个指针同步遍历原链表前半段 (`head`) 与反转后的后半段 (`head2`)，逐节点比较值。
④ 若全部相等则为回文；否则返回 False。
时间复杂度：O(n)
空间复杂度：O(1)
"""
# ① 找中点
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. 环形链表¶
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
提示：
链表中节点的数目范围是 [0, 104] -105 <= Node.val <= 105 pos 为 -1 或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
In [ ]:
Copied!
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
# 1. 初始化两个指针都指向 head
slow, fast = head, head
# 2. 循环条件：只有当 fast 和 fast.next 都存在时，才继续循环
# 这个条件优雅地处理了所有边界情况（空链表、单节点、偶数/奇数长度链表）
while fast and fast.next:
slow = slow.next # slow 走一步
fast = fast.next.next # fast 走两步
# 3. 如果相遇，说明有环
if slow == fast:
return True
# 4. 如果循环正常结束，说明 fast 走到了尽头，没有环
return False
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
# 1. 初始化两个指针都指向 head
slow, fast = head, head
# 2. 循环条件：只有当 fast 和 fast.next 都存在时，才继续循环
# 这个条件优雅地处理了所有边界情况（空链表、单节点、偶数/奇数长度链表）
while fast and fast.next:
slow = slow.next # slow 走一步
fast = fast.next.next # fast 走两步
# 3. 如果相遇，说明有环
if slow == fast:
return True
# 4. 如果循环正常结束，说明 fast 走到了尽头，没有环
return False
142. 环形链表 II¶
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
In [ ]:
Copied!
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
from typing import Optional
class Solution:
def detectCycle(self, head: Optional['ListNode']) -> Optional['ListNode']:
"""
环形链表 II —— 双指针法
解题思路：
1. 使用快慢指针（fast 和 slow）从链表头部出发。
2. 若链表有环，则快慢指针会在环内相遇。否则 fast 会先走到 None，说明无环。
3. 第一次相遇后，让 fast 指针重置到链表头，fast 和 slow 同时每轮走一步。
4. 第二次相遇时，即为环的入口节点。
原理分析：
- 假设从链表头到环入口有 a 个节点，环长度为 b。
- 第一次相遇时：fast = 2s, slow = s, 且 fast 比 slow 多走了 n 圈，即 fast = s + nb。
- 推导得：s = nb，fast 和 slow 走了 2n 圈和 n 圈。此时对于slow来说，当他走到入口处时，则走了a+nb 步。
- 所以令 fast 从头再走 a 步，slow 从当前 nb 继续走 a 步，两者将在入口处相遇。
时间复杂度：O(n)
空间复杂度：O(1)
"""
if not head or not head.next:
return None
# 第一次相遇：判断是否有环
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
# 无环，直接返回
return None
# 第二次相遇：寻找环的入口
fast = head
while fast != slow:
fast = fast.next
slow = slow.next
return slow # 或 fast，指向环的入口节点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
from typing import Optional
class Solution:
def detectCycle(self, head: Optional['ListNode']) -> Optional['ListNode']:
"""
环形链表 II —— 双指针法
解题思路：
1. 使用快慢指针（fast 和 slow）从链表头部出发。
2. 若链表有环，则快慢指针会在环内相遇。否则 fast 会先走到 None，说明无环。
3. 第一次相遇后，让 fast 指针重置到链表头，fast 和 slow 同时每轮走一步。
4. 第二次相遇时，即为环的入口节点。
原理分析：
- 假设从链表头到环入口有 a 个节点，环长度为 b。
- 第一次相遇时：fast = 2s, slow = s, 且 fast 比 slow 多走了 n 圈，即 fast = s + nb。
- 推导得：s = nb，fast 和 slow 走了 2n 圈和 n 圈。此时对于slow来说，当他走到入口处时，则走了a+nb 步。
- 所以令 fast 从头再走 a 步，slow 从当前 nb 继续走 a 步，两者将在入口处相遇。
时间复杂度：O(n)
空间复杂度：O(1)
"""
if not head or not head.next:
return None
# 第一次相遇：判断是否有环
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
# 无环，直接返回
return None
# 第二次相遇：寻找环的入口
fast = head
while fast != slow:
fast = fast.next
slow = slow.next
return slow # 或 fast，指向环的入口节点
21合并两个有序链表¶
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
In [ ]:
Copied!
# Definition for singly‑linked list.
# class ListNode:
# def __init__(self, val: int = 0, next: 'ListNode | None' = None):
# self.val = val
# self.next = next
from typing import Optional
class Solution:
def mergeTwoLists(self,
list1: Optional['ListNode'],
list2: Optional['ListNode']) -> Optional['ListNode']:
"""
合并两个升序链表（LeetCode 21）
核心思想（迭代＋虚拟头节点）
--------------------------------------------------
1. 新建一个虚拟头节点 dummy，创建工作指针 cur 指向 dummy。
2. 用双指针 L1、L2 分别遍历两条链表：
‑ 若 L1.val ≤ L2.val，则把 L1 节点接到 cur 之后，L1 后移；
‑ 否则把 L2 节点接到 cur 之后，L2 后移。
每次接入节点后，cur 前移一格。
3. 当其中一条链表遍历完毕后，将另一条链表剩余部分整体接到 cur.next。
4. 返回 dummy.next 即合并后链表的头节点。
复杂度分析
--------------------------------------------------
• 时间复杂度：O(m + n)
— 每个链表的每个节点都只被遍历一次，其中 m、n 分别为两链表长度。
• 空间复杂度：O(1)
— 仅使用常数级额外指针；链表节点本身被原地复用，无需额外存储。
:param list1: 升序链表 1
:param list2: 升序链表 2
:return: 合并后的升序链表头节点
"""
# 初始化虚拟头节点与工作指针
dummy = ListNode(0)
cur = dummy
L1, L2 = list1, list2
# 主循环：同时遍历两条链表
while L1 and L2:
if L1.val <= L2.val:
cur.next = L1
L1 = L1.next
else:
cur.next = L2
L2 = L2.next
cur = cur.next # 工作指针前移
# 某一条链表已结束，直接拼接剩余链表
cur.next = L1 if L1 else L2
return dummy.next
# Definition for singly‑linked list.
# class ListNode:
# def __init__(self, val: int = 0, next: 'ListNode | None' = None):
# self.val = val
# self.next = next
from typing import Optional
class Solution:
def mergeTwoLists(self,
list1: Optional['ListNode'],
list2: Optional['ListNode']) -> Optional['ListNode']:
"""
合并两个升序链表（LeetCode 21）
核心思想（迭代＋虚拟头节点）
--------------------------------------------------
1. 新建一个虚拟头节点 dummy，创建工作指针 cur 指向 dummy。
2. 用双指针 L1、L2 分别遍历两条链表：
‑ 若 L1.val ≤ L2.val，则把 L1 节点接到 cur 之后，L1 后移；
‑ 否则把 L2 节点接到 cur 之后，L2 后移。
每次接入节点后，cur 前移一格。
3. 当其中一条链表遍历完毕后，将另一条链表剩余部分整体接到 cur.next。
4. 返回 dummy.next 即合并后链表的头节点。
复杂度分析
--------------------------------------------------
• 时间复杂度：O(m + n)
— 每个链表的每个节点都只被遍历一次，其中 m、n 分别为两链表长度。
• 空间复杂度：O(1)
— 仅使用常数级额外指针；链表节点本身被原地复用，无需额外存储。
:param list1: 升序链表 1
:param list2: 升序链表 2
:return: 合并后的升序链表头节点
"""
# 初始化虚拟头节点与工作指针
dummy = ListNode(0)
cur = dummy
L1, L2 = list1, list2
# 主循环：同时遍历两条链表
while L1 and L2:
if L1.val <= L2.val:
cur.next = L1
L1 = L1.next
else:
cur.next = L2
L2 = L2.next
cur = cur.next # 工作指针前移
# 某一条链表已结束，直接拼接剩余链表
cur.next = L1 if L1 else L2
return dummy.next
2. 两数相加¶
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
提示：
每个链表中的节点数在范围 [1, 100] 内 0 <= Node.val <= 9 题目数据保证列表表示的数字不含前导零
In [2]:
Copied!
from typing import Optional
class ListNode:
def __init__(self, val: int = 0, next: 'ListNode | None' = None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self,
l1: Optional[ListNode],
l2: Optional[ListNode]) -> Optional[ListNode]:
"""
链表模拟大整数加法
核心思想：
- 每一位的和 = l1.val + l2.val + 上一位进位 carry
- 用一个哑节点 (dummy) 方便返回结果链表头
- 指针 cur 始终指向结果链表尾；carry 保存当前进位
- 当 l1、l2 均遍历完且无进位时结束循环
伪流程：
1. 初始化 dummy、cur、carry = 0
2. 进入循环，只要 l1、l2、carry 任何一个仍存在：
├─ 若 l1 不为空，加上 l1.val 并 l1 = l1.next
├─ 若 l2 不为空，加上 l2.val 并 l2 = l2.next
├─ 结果位 = carry % 10，进位 = carry // 10
├─ 将结果位封装为新节点接到 cur.next，cur 前移
3. 返回 dummy.next 即结果链表头
时间复杂度：O(max(m, n)) — 需遍历两条链表一次
空间复杂度：O(1) — 除输出链表外仅用常数额外变量
"""
cur = dummy = ListNode() # 哑节点 + 尾指针
carry = 0 # 进位初始化
# 主循环：任一链表未结束或仍有进位
while l1 or l2 or carry:
if l1: # 加上 l1 当前位
carry += l1.val
l1 = l1.next
if l2: # 加上 l2 当前位
carry += l2.val
l2 = l2.next
cur.next = ListNode(carry % 10) # 生成当前结果位
carry //= 10 # 更新进位
cur = cur.next # 尾指针前移
return dummy.next # 返回结果链表
# 示例测试
l1 = ListNode(2, ListNode(4, ListNode(3))) # 表示 342
l2 = ListNode(5, ListNode(6, ListNode(4))) # 表示 465
result = Solution().addTwoNumbers(l1, l2) # 结果应为 807 → 7→0→8
print(result.val, result.next.val, result.next.next.val) # 7 0 8
from typing import Optional
class ListNode:
def __init__(self, val: int = 0, next: 'ListNode | None' = None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self,
l1: Optional[ListNode],
l2: Optional[ListNode]) -> Optional[ListNode]:
"""
链表模拟大整数加法
核心思想：
- 每一位的和 = l1.val + l2.val + 上一位进位 carry
- 用一个哑节点 (dummy) 方便返回结果链表头
- 指针 cur 始终指向结果链表尾；carry 保存当前进位
- 当 l1、l2 均遍历完且无进位时结束循环
伪流程：
1. 初始化 dummy、cur、carry = 0
2. 进入循环，只要 l1、l2、carry 任何一个仍存在：
├─ 若 l1 不为空，加上 l1.val 并 l1 = l1.next
├─ 若 l2 不为空，加上 l2.val 并 l2 = l2.next
├─ 结果位 = carry % 10，进位 = carry // 10
├─ 将结果位封装为新节点接到 cur.next，cur 前移
3. 返回 dummy.next 即结果链表头
时间复杂度：O(max(m, n)) — 需遍历两条链表一次
空间复杂度：O(1) — 除输出链表外仅用常数额外变量
"""
cur = dummy = ListNode() # 哑节点 + 尾指针
carry = 0 # 进位初始化
# 主循环：任一链表未结束或仍有进位
while l1 or l2 or carry:
if l1: # 加上 l1 当前位
carry += l1.val
l1 = l1.next
if l2: # 加上 l2 当前位
carry += l2.val
l2 = l2.next
cur.next = ListNode(carry % 10) # 生成当前结果位
carry //= 10 # 更新进位
cur = cur.next # 尾指针前移
return dummy.next # 返回结果链表
# 示例测试
l1 = ListNode(2, ListNode(4, ListNode(3))) # 表示 342
l2 = ListNode(5, ListNode(6, ListNode(4))) # 表示 465
result = Solution().addTwoNumbers(l1, l2) # 结果应为 807 → 7→0→8
print(result.val, result.next.val, result.next.next.val) # 7 0 8
7 0 8
19. 删除链表的倒数第 N 个结点¶
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1： 输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2： 输入：head = [1], n = 1 输出：[]
示例 3： 输入：head = [1,2], n = 1 输出：[1]
提示： 链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
In [11]:
Copied!
from typing import Optional
class ListNode:
def __init__(self, val: int = 0, next: 'ListNode | None' = None):
self.val = val
self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
"""
一趟扫描删除链表倒数第 n 个结点（双指针）
核心思想：
1. **哨兵节点**：在链表头前加一个 dummy，可统一处理 “删除头节点” 等边界情况。
2. **快慢指针（right / left）**：
- 先让 right 指针向前走 n 步，确保两个指针之间间隔为 n。
- 接着 right 与 left 同步前进，直到 right 指向链表尾结点；
此时 left 正好位于目标结点的前驱位置。
3. **删除操作**：将 `left.next` 指向 `left.next.next` 即可删除倒数第 n 个结点。
时间复杂度：O(L) ，L 为链表长度，仅一次遍历
空间复杂度：O(1) ，仅使用常数级指针变量
"""
# 1. 建立哨兵节点，避免删除头结点时的特殊判断
dummy = ListNode(next=head)
left = right = dummy
# 2. 快指针先走 n 步，拉开间距
for _ in range(n):
right = right.next
# 3. 快慢指针同步前进，right 到尾时 left 在目标前驱
while right.next:
left = left.next
right = right.next
# 4. 删除倒数第 n 个结点
left.next = left.next.next
return dummy.next
from typing import Optional
class ListNode:
def __init__(self, val: int = 0, next: 'ListNode | None' = None):
self.val = val
self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
"""
一趟扫描删除链表倒数第 n 个结点（双指针）
核心思想：
1. **哨兵节点**：在链表头前加一个 dummy，可统一处理 “删除头节点” 等边界情况。
2. **快慢指针（right / left）**：
- 先让 right 指针向前走 n 步，确保两个指针之间间隔为 n。
- 接着 right 与 left 同步前进，直到 right 指向链表尾结点；
此时 left 正好位于目标结点的前驱位置。
3. **删除操作**：将 `left.next` 指向 `left.next.next` 即可删除倒数第 n 个结点。
时间复杂度：O(L) ，L 为链表长度，仅一次遍历
空间复杂度：O(1) ，仅使用常数级指针变量
"""
# 1. 建立哨兵节点，避免删除头结点时的特殊判断
dummy = ListNode(next=head)
left = right = dummy
# 2. 快指针先走 n 步，拉开间距
for _ in range(n):
right = right.next
# 3. 快慢指针同步前进，right 到尾时 left 在目标前驱
while right.next:
left = left.next
right = right.next
# 4. 删除倒数第 n 个结点
left.next = left.next.next
return dummy.next
24. 两两交换链表中的节点¶
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1： 输入：head = [1,2,3,4] 输出：[2,1,4,3]
提示：
链表中节点的数目在范围 [0, 100] 内 0 <= Node.val <= 100
In [ ]:
Copied!
from typing import Optional
class ListNode:
def __init__(self, val: int = 0, next: 'ListNode | None' = None):
self.val = val
self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
"""
两两交换链表中的结点
核心思想（迭代 + 原地交换）：
1. **哑节点 dummy**
- 在链表头部前插入一个哑节点，便于处理交换到头结点的情况，统一逻辑。
2. **四指针滑动窗口**
- `node0` 指向上一对结点的前驱（初始为 dummy）。
- `node1`、`node2` 代表当前要交换的两个结点。
- `node3` 保存下一对结点的起点（`node2.next`），用于后续连接。
- 交换步骤：
```
node0 -> node1 -> node2 -> node3
交换后：
node0 -> node2 -> node1 -> node3
```
3. **循环推进**
- 每完成一次交换，将 `node0` 移到 `node1`（新的前驱），
`node1 = node0.next` 进入下一对；循环直至链表末尾或剩余结点不足 2 个。
复杂度分析：
- **时间复杂度**：O(L)，L 为链表长度，每个结点最多访问一次。
- **空间复杂度**：O(1)，仅使用常数级指针变量。
"""
node0 = dummy = ListNode(next=head) # 哑节点 + node0 初始指向 dummy
node1 = node0.next # node1 指向第一对的第 1 个结点
# 只要剩余结点数量 ≥ 2 就继续交换
while node1 and node1.next:
node2 = node1.next # 当前对的第 2 个结点
node3 = node2.next # 下一对的起始结点
# 1) 前驱指向 node2
node0.next = node2
# 2) node1 指向 node3（接回后续链表
node1.next = node3
# 3) node2 指向 node1（完成交换）
node2.next = node1
# 移动窗口：node0 跳到已交换对的尾部 node1
node0 = node1
node1 = node1.next # 下一对的第 1 个结点
return dummy.next # 返回真正的链表头
from typing import Optional
class ListNode:
def __init__(self, val: int = 0, next: 'ListNode | None' = None):
self.val = val
self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
"""
两两交换链表中的结点
核心思想（迭代 + 原地交换）：
1. **哑节点 dummy**
- 在链表头部前插入一个哑节点，便于处理交换到头结点的情况，统一逻辑。
2. **四指针滑动窗口**
- `node0` 指向上一对结点的前驱（初始为 dummy）。
- `node1`、`node2` 代表当前要交换的两个结点。
- `node3` 保存下一对结点的起点（`node2.next`），用于后续连接。
- 交换步骤：
```
node0 -> node1 -> node2 -> node3
交换后：
node0 -> node2 -> node1 -> node3
```
3. **循环推进**
- 每完成一次交换，将 `node0` 移到 `node1`（新的前驱），
`node1 = node0.next` 进入下一对；循环直至链表末尾或剩余结点不足 2 个。
复杂度分析：
- **时间复杂度**：O(L)，L 为链表长度，每个结点最多访问一次。
- **空间复杂度**：O(1)，仅使用常数级指针变量。
"""
node0 = dummy = ListNode(next=head) # 哑节点 + node0 初始指向 dummy
node1 = node0.next # node1 指向第一对的第 1 个结点
# 只要剩余结点数量 ≥ 2 就继续交换
while node1 and node1.next:
node2 = node1.next # 当前对的第 2 个结点
node3 = node2.next # 下一对的起始结点
# 1) 前驱指向 node2
node0.next = node2
# 2) node1 指向 node3（接回后续链表
node1.next = node3
# 3) node2 指向 node1（完成交换）
node2.next = node1
# 移动窗口：node0 跳到已交换对的尾部 node1
node0 = node1
node1 = node1.next # 下一对的第 1 个结点
return dummy.next # 返回真正的链表头
25. K 个一组翻转链表¶
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1： 输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]
In [ ]:
Copied!
from typing import Optional
# Definition for singly-linked list
class ListNode:
def __init__(self, val: int = 0, next: 'ListNode | None' = None):
self.val = val
self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
"""
每 k 个一组翻转链表
解题思路：
1. 首先遍历链表统计总长度 n，用于判断有多少组完整的 k 个节点可翻转；
2. 使用 dummy 节点简化头节点的处理，p0 是每组开始前的前置节点；
3. 当剩余节点数量 n ≥ k 时：
- 用循环对 k 个节点进行原地反转，使用 pre 和 cur 指针完成；
- 反转后通过 p0 连接新头 pre；
- 用保存的原组头节点（翻转后是尾）nxt 连接剩下未反转部分；
- 将 p0 移动到新尾部，为下一组翻转做准备；
4. 剩余不足 k 个节点的部分保持原顺序；
时间复杂度：O(n)，每个节点只访问和修改一次；
空间复杂度：O(1)，使用常数级辅助指针。
"""
# 1. 统计链表长度
n = 0
cur = head
while cur:
n += 1
cur = cur.next
# 2. 初始化辅助节点
dummy = ListNode(next=head)
p0 = dummy # p0 指向每组开始前的位置
pre = None # pre 用于反转过程中的头指针
cur = head # cur 指向当前要处理的节点
# 3. 循环反转每一组长度为 k 的子链表
while n >= k:
n -= k
# 3.1 反转当前 k 个节点
pre = None
for i in range(k):
nxt = cur.next # 暂存下一个节点
cur.next = pre # 当前节点指向前一个
pre = cur # pre 前移
cur = nxt # cur 前移
# 3.2 完成一组的连接工作
trail = p0.next # 保存原组头（反转后是尾）
trail.next = cur # 反转后尾连接剩余链表部分
p0.next = pre # 前一段链表连接新头
p0 = trail # p0 移动到当前组尾部，为下一组准备
return dummy.next # 返回新链表的头节点
# 示例测试
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
k = 2
result = Solution().reverseKGroup(head, k)
print(result.val, result.next.val, result.next.next.val, result.next.next.next.val, result.next.next.next.next.val) # 2 1 4 3 5
from typing import Optional
# Definition for singly-linked list
class ListNode:
def __init__(self, val: int = 0, next: 'ListNode | None' = None):
self.val = val
self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
"""
每 k 个一组翻转链表
解题思路：
1. 首先遍历链表统计总长度 n，用于判断有多少组完整的 k 个节点可翻转；
2. 使用 dummy 节点简化头节点的处理，p0 是每组开始前的前置节点；
3. 当剩余节点数量 n ≥ k 时：
- 用循环对 k 个节点进行原地反转，使用 pre 和 cur 指针完成；
- 反转后通过 p0 连接新头 pre；
- 用保存的原组头节点（翻转后是尾）nxt 连接剩下未反转部分；
- 将 p0 移动到新尾部，为下一组翻转做准备；
4. 剩余不足 k 个节点的部分保持原顺序；
时间复杂度：O(n)，每个节点只访问和修改一次；
空间复杂度：O(1)，使用常数级辅助指针。
"""
# 1. 统计链表长度
n = 0
cur = head
while cur:
n += 1
cur = cur.next
# 2. 初始化辅助节点
dummy = ListNode(next=head)
p0 = dummy # p0 指向每组开始前的位置
pre = None # pre 用于反转过程中的头指针
cur = head # cur 指向当前要处理的节点
# 3. 循环反转每一组长度为 k 的子链表
while n >= k:
n -= k
# 3.1 反转当前 k 个节点
pre = None
for i in range(k):
nxt = cur.next # 暂存下一个节点
cur.next = pre # 当前节点指向前一个
pre = cur # pre 前移
cur = nxt # cur 前移
# 3.2 完成一组的连接工作
trail = p0.next # 保存原组头（反转后是尾）
trail.next = cur # 反转后尾连接剩余链表部分
p0.next = pre # 前一段链表连接新头
p0 = trail # p0 移动到当前组尾部，为下一组准备
return dummy.next # 返回新链表的头节点
# 示例测试
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
k = 2
result = Solution().reverseKGroup(head, k)
print(result.val, result.next.val, result.next.next.val, result.next.next.next.val, result.next.next.next.next.val) # 2 1 4 3 5
2 1 4 3 5
In [ ]:
Copied!
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
node = head
n = 0
while node:
n += 1
node = node.next
dummy = p0 = ListNode(0, head)
node0 = None
node1 = head
while n>= k:
n -= k
for _ in range(k):
node2 = node1.next
node1.next = node0
node0 = node1
node1 = node2
# 1.得到反转后链表的尾节点，将尾节点与下一组反转的链表连接
# 2.更新整个链表的头节点p0.next = node0
# 3.将p0更新为下一组链表的头节点的前一个，相当与上一组的尾节点
trail = p0.next
trail.next = node1
p0.next = node0
p0 = trail
return dummy.next
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
node = head
n = 0
while node:
n += 1
node = node.next
dummy = p0 = ListNode(0, head)
node0 = None
node1 = head
while n>= k:
n -= k
for _ in range(k):
node2 = node1.next
node1.next = node0
node0 = node1
node1 = node2
# 1.得到反转后链表的尾节点，将尾节点与下一组反转的链表连接
# 2.更新整个链表的头节点p0.next = node0
# 3.将p0更新为下一组链表的头节点的前一个，相当与上一组的尾节点
trail = p0.next
trail.next = node1
p0.next = node0
p0 = trail
return dummy.next
138. 随机链表的复制¶
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]
提示：
0 <= n <= 1000 -104 <= Node.val <= 104 Node.random 为 null 或指向链表中的节点。
In [1]:
Copied!
# 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]':
"""
三趟遍历 + O(1) 额外空间深拷贝随机链表
算法概要
------------------------------------------------------------------
① **插入克隆节点**：
对每个原节点 A 生成克隆 A' 并紧随其后 → 形成为 A→A'→B→B'…
② **复制 random 指针**：
若 A.random = R，则 A'.random = R.next（即 R 的克隆）
因为 A' 就在 A.next，R' 就在 R.next。
③ **拆分链表**：
只保留克隆节点之间的连接，得到独立的 A'→B'→C'…
（原链表是否恢复无关紧要，题目只要求返回克隆链表）
复杂度
------------------------------------------------------------------
- 时间：三次完整遍历 → **O(n)**
- 空间：仅若干指针变量 → **O(1)**（输出链表本身不计入）
"""
# ① 边界：空链表直接返回
if head is None:
return None
# ---------- 第一趟：插入克隆节点 ----------
cur = head
while cur:
clone = Node(cur.val, cur.next) # 创建克隆节点
cur.next = clone # 插入克隆节点到原节点后
cur = clone.next # 跳到下一个原节点
# ---------- 第二趟：复制 random ----------
cur = head
while cur:
if cur.random:
clone = cur.next # 取当前克隆节点
clone.random = cur.random.next # 克隆节点的 random 指向原 random 的克隆,注意克隆点只能指向克隆点，所以这里不是cur.random，而是 cur.random.next
cur = cur.next.next # 仍跳两步走原节点,注意cur = clone.next会报错，因为当cur.random= None时，clone未被创建
# ---------- 第三趟：拆分克隆链表 ----------
clone = head.next # cur 指向第一个克隆节点
while clone.next: # cur.next 指向下一个原节点
clone.next = clone.next.next # 直接连到下一个克隆节点
clone = clone.next # 移动到下一个克隆节点
# 返回克隆链表头结点
return head.next
# 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]':
"""
三趟遍历 + O(1) 额外空间深拷贝随机链表
算法概要
------------------------------------------------------------------
① **插入克隆节点**：
对每个原节点 A 生成克隆 A' 并紧随其后 → 形成为 A→A'→B→B'…
② **复制 random 指针**：
若 A.random = R，则 A'.random = R.next（即 R 的克隆）
因为 A' 就在 A.next，R' 就在 R.next。
③ **拆分链表**：
只保留克隆节点之间的连接，得到独立的 A'→B'→C'…
（原链表是否恢复无关紧要，题目只要求返回克隆链表）
复杂度
------------------------------------------------------------------
- 时间：三次完整遍历 → **O(n)**
- 空间：仅若干指针变量 → **O(1)**（输出链表本身不计入）
"""
# ① 边界：空链表直接返回
if head is None:
return None
# ---------- 第一趟：插入克隆节点 ----------
cur = head
while cur:
clone = Node(cur.val, cur.next) # 创建克隆节点
cur.next = clone # 插入克隆节点到原节点后
cur = clone.next # 跳到下一个原节点
# ---------- 第二趟：复制 random ----------
cur = head
while cur:
if cur.random:
clone = cur.next # 取当前克隆节点
clone.random = cur.random.next # 克隆节点的 random 指向原 random 的克隆,注意克隆点只能指向克隆点，所以这里不是cur.random，而是 cur.random.next
cur = cur.next.next # 仍跳两步走原节点,注意cur = clone.next会报错，因为当cur.random= None时，clone未被创建
# ---------- 第三趟：拆分克隆链表 ----------
clone = head.next # cur 指向第一个克隆节点
while clone.next: # cur.next 指向下一个原节点
clone.next = clone.next.next # 直接连到下一个克隆节点
clone = clone.next # 移动到下一个克隆节点
# 返回克隆链表头结点
return head.next
148. 排序链表¶
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1： 输入：head = [4,2,1,3] 输出：[1,2,3,4]
示例 2： 输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]
示例 3： 输入：head = [] 输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 104] 内 -105 <= Node.val <= 105
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
In [ ]:
Copied!
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
slow, fast = head, head.next
while fast and fast.next:
fast = fast.next.next
slow = slow.next
right = slow.next
slow.next = None
left = head
sort_left = self.sortList(left)
sort_right = self.sortList(right)
return self.mergelist(sort_left, sort_right)
def mergelist(self, l1, l2):
dummy = ListNode()
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
if l1:
cur.next = l1
if l2:
cur.next = l2
return dummy.next
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
slow, fast = head, head.next
while fast and fast.next:
fast = fast.next.next
slow = slow.next
right = slow.next
slow.next = None
left = head
sort_left = self.sortList(left)
sort_right = self.sortList(right)
return self.mergelist(sort_left, sort_right)
def mergelist(self, l1, l2):
dummy = ListNode()
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
if l1:
cur.next = l1
if l2:
cur.next = l2
return dummy.next
-1 0 3 4
In [ ]:
Copied!
from typing import Optional
class ListNode:
def __init__(self, val:int = 0, next: 'ListNode|None' = None):
self.val = val
self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# --- 递归的终止条件 ---
# 如果链表为空，或者只有一个节点，那么它已经是有序的了
if not head or not head.next:
return head
# --- 1. 分割 (Divide)：找到中点并切分链表 ---
# 使用快慢指针法找到链表中点
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 循环结束后，slow 指向的是链表的中点（或者是中点前一个，取决于实现）
# 我们在这里将链表断开
mid = slow.next # mid 是右半部分链表的头节点
slow.next = None # 从中点断开
# 现在我们有了两个子链表：
left_half = head
right_half = mid
# --- 2. 解决 (Conquer)：递归地排序左右两个子链表 ---
sorted_left = self.sortList(left_half)
sorted_right = self.sortList(right_half)
# --- 3. 合并 (Merge)：将排序好的两个子链表合并 ---
return self._merge(sorted_left, sorted_right)
def _merge(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
"""
辅助函数：合并两个已排序的链表 l1 和 l2。
"""
# 创建一个虚拟头节点，方便我们构建新的有序链表
dummy = ListNode(0)
# `cur` 指针用于在-新链表上移动
cur = dummy
# 像拉拉链一样，比较 l1 和 l2 的头节点，把较小的那个串到新链表上
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
# 移动 curr 指针
cur = cur.next
# 循环结束后，l1 或 l2 中最多还有一个还有剩余节点
# 直接将剩下的部分全部接到新链表的末尾
cur.next = l1 if l1 else l2
# dummy 节点是虚拟的，它的下一个节点才是新链表的真正头节点
return dummy.next
# --- 使用示例 ---
# 假设我们有这样一个链表: 4 -> 2 -> 1 -> 3
head = ListNode(4, ListNode(2, ListNode(1, ListNode(3))))
solver = Solution()
sorted_head = solver.sortList(head)
print(sorted_head)
# 打印 sorted_head 会得到: 1 -> 2 -> 3 -> 4
from typing import Optional
class ListNode:
def __init__(self, val:int = 0, next: 'ListNode|None' = None):
self.val = val
self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# --- 递归的终止条件 ---
# 如果链表为空，或者只有一个节点，那么它已经是有序的了
if not head or not head.next:
return head
# --- 1. 分割 (Divide)：找到中点并切分链表 ---
# 使用快慢指针法找到链表中点
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 循环结束后，slow 指向的是链表的中点（或者是中点前一个，取决于实现）
# 我们在这里将链表断开
mid = slow.next # mid 是右半部分链表的头节点
slow.next = None # 从中点断开
# 现在我们有了两个子链表：
left_half = head
right_half = mid
# --- 2. 解决 (Conquer)：递归地排序左右两个子链表 ---
sorted_left = self.sortList(left_half)
sorted_right = self.sortList(right_half)
# --- 3. 合并 (Merge)：将排序好的两个子链表合并 ---
return self._merge(sorted_left, sorted_right)
def _merge(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
"""
辅助函数：合并两个已排序的链表 l1 和 l2。
"""
# 创建一个虚拟头节点，方便我们构建新的有序链表
dummy = ListNode(0)
# `cur` 指针用于在-新链表上移动
cur = dummy
# 像拉拉链一样，比较 l1 和 l2 的头节点，把较小的那个串到新链表上
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
# 移动 curr 指针
cur = cur.next
# 循环结束后，l1 或 l2 中最多还有一个还有剩余节点
# 直接将剩下的部分全部接到新链表的末尾
cur.next = l1 if l1 else l2
# dummy 节点是虚拟的，它的下一个节点才是新链表的真正头节点
return dummy.next
# --- 使用示例 ---
# 假设我们有这样一个链表: 4 -> 2 -> 1 -> 3
head = ListNode(4, ListNode(2, ListNode(1, ListNode(3))))
solver = Solution()
sorted_head = solver.sortList(head)
print(sorted_head)
# 打印 sorted_head 会得到: 1 -> 2 -> 3 -> 4
<__main__.ListNode object at 0x000002505043EDD0>
23. 合并 K 个升序链表¶
给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1： 输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6]
示例 2： 输入：lists = [] 输出：[]
示例 3： 输入：lists = [[]] 输出：[]
提示：
k == lists.length 0 <= k <= 10^4 0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4 lists[i] 按 升序 排列 lists[i].length 的总和不超过 10^4
In [ ]:
Copied!
from typing import Optional, List
class ListNode:
def __init__(self, val:int = 0, next: Optional[ListNode] = None):
self.val = val
self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]):
"""
分治：两两合并链表
- 若 lists 为空或全是空链表，直接返回 None
- 每一轮把相邻两条链表合并成一条，lists 的长度会减半
"""
if not lists:
return None
# 过滤掉 None，避免无意义的合并（可选，不写也对）
lists = [head for head in lists if head]
if not lists:
return None
# 不断两两合并，直到只剩一条
while len(lists) > 1:
merged_round = []
# 步长为2，成对合并
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i+1] if i + 1 < len(lists) else None
merged_round.append(self._merge_two_lists(l1, l2))
lists = merged_round
return lists[0]
def _merge_two_lists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
"""
合并两个已升序的链表，返回升序结果
经典拉链法：每次取较小节点接到新链表后面
"""
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
# 接上剩余部分
cur.next = l1 if l1 else l2
return dummy.next
from typing import Optional, List
class ListNode:
def __init__(self, val:int = 0, next: Optional[ListNode] = None):
self.val = val
self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]):
"""
分治：两两合并链表
- 若 lists 为空或全是空链表，直接返回 None
- 每一轮把相邻两条链表合并成一条，lists 的长度会减半
"""
if not lists:
return None
# 过滤掉 None，避免无意义的合并（可选，不写也对）
lists = [head for head in lists if head]
if not lists:
return None
# 不断两两合并，直到只剩一条
while len(lists) > 1:
merged_round = []
# 步长为2，成对合并
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i+1] if i + 1 < len(lists) else None
merged_round.append(self._merge_two_lists(l1, l2))
lists = merged_round
return lists[0]
def _merge_two_lists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
"""
合并两个已升序的链表，返回升序结果
经典拉链法：每次取较小节点接到新链表后面
"""
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
# 接上剩余部分
cur.next = l1 if l1 else l2
return dummy.next
146. LRU 缓存¶
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类： LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例：
输入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出 [null, null, null, 1, null, -1, null, -1, 3, 4]
解释 LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 3000 0 <= key <= 10000 0 <= value <= 105 最多调用 2 * 105 次 get 和 put
In [ ]:
Copied!