链表

何时需要虚拟头节点（Dummy Node）¶

核心判断标准：结果链表的头节点在逻辑执行前是否确定。

不需要 Dummy Node 的题型¶

这类题的操作对象是已有链表的指针调整，头节点身份明确：

题目	原因
反转链表	新头就是原链表尾节点，反转过程中明确追踪
判断回文	只做遍历与值比较，不修改结构
环形链表	只做指针追逐，不修改结构

需要 Dummy Node 的题型¶

这类题需要动态构建结果链表，第一个节点在执行前不确定：

题目	原因
合并两个有序链表	第一个节点可能来自 list1 也可能来自 list2
删除链表第 N 个节点	若删的是头节点，头会变
链表分隔、排序等	同上，结果头节点不固定

本质解释¶

没有 Dummy Node 时，你必须对头节点做特殊处理：

# 不用 dummy，合并两链表需要手动判断谁是头
if list1.val <= list2.val:
    head = list1
    list1 = list1.next
else:
    head = list2
    list2 = list2.next
# 后续逻辑还要再写一遍……重复且易错

用 Dummy Node 后，头节点的"特殊性"被消除，所有节点统一处理：

dummy = ListNode()   # 永远是第一个节点的前驱
head = dummy
# 之后无论谁是真正的头，逻辑完全一致
return dummy.next    # 真正的头在这里

总结一句话¶

凡是需要拼接/构建结果链表，且头节点不能提前确定的场景，就用 Dummy Node。与链表数量无关，一个链表的题（如"删除倒数第 N 个节点"）同样需要。

In [35]:

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 [36]:

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 [37]:

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)

206 反转链表¶

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

In [38]:

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 [3]:

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

headA = ListNode(1, ListNode(2, ListNode(3, ListNode(2, ListNode(1)))))
print(Solution().isPalindrome(headA))
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

headA = ListNode(1, ListNode(2, ListNode(3, ListNode(2, ListNode(1)))))
print(Solution().isPalindrome(headA))

True

141. 环形链表¶

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

提示：

链表中节点的数目范围是 [0, 104] -105 <= Node.val <= 105 pos 为 -1 或者链表中的一个有效索引。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

In [40]:

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 [41]:

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 [42]:

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 [43]:

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 [44]:

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 [45]:

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 [46]:

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 [47]:

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

In [ ]:

Copied!





class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

        def get_kth(node, k):
            while node and k:
                node = node.next
                k -= 1
            return node

        node0 = dummy = ListNode(next=head)
        node1 = dummy.next

        while True:
            nodeK = get_kth(node0, k)
            if not nodeK:
                break

            nodeK_next = nodeK.next

            # 标准反转：prev 从 node0 出发（与普通反转链表一致）
            prev = node0
            cur  = node1
            while cur != nodeK_next:
                nxt      = cur.next
                cur.next = prev   # 反转指针
                prev     = cur
                cur      = nxt
            # 反转结束：prev == nodeK，node1.next == node0（临时错误）

            # 显式重连（与两两交换完全对称）
            node0.next = nodeK       # 前驱接新头
            node1.next = nodeK_next  # 原头（现尾）接下一组

            # 推进窗口
            node0 = node1
            node1 = node1.next

        return dummy.next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

        def get_kth(node, k):
            while node and k:
                node = node.next
                k -= 1
            return node

        node0 = dummy = ListNode(next=head)
        node1 = dummy.next

        while True:
            nodeK = get_kth(node0, k)
            if not nodeK:
                break

            nodeK_next = nodeK.next

            # 标准反转：prev 从 node0 出发（与普通反转链表一致）
            prev = node0
            cur  = node1
            while cur != nodeK_next:
                nxt      = cur.next
                cur.next = prev   # 反转指针
                prev     = cur
                cur      = nxt
            # 反转结束：prev == nodeK，node1.next == node0（临时错误）

            # 显式重连（与两两交换完全对称）
            node0.next = nodeK       # 前驱接新头
            node1.next = nodeK_next  # 原头（现尾）接下一组

            # 推进窗口
            node0 = node1
            node1 = node1.next

        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 或指向链表中的节点。

为什么"随机链表的复制"并不简单？¶

这是一个非常好的问题，值得从根本上澄清。

普通遍历复制为何不够？¶

对于普通链表（只有 next 指针），遍历复制确实是平凡的——你从头到尾依次创建新节点，每个新节点的 next 指向刚刚创建的下一个节点，顺序天然保证了引用的正确性。

本题的核心难点在于 random 指针的"向前引用"问题。

设想如下链表：

节点0 → 节点1 → 节点2 → 节点3
              ↑
        节点3.random

当你在遍历到节点3、准备设置其副本的 random 指针时，你需要让它指向"节点1的副本"。但如果你此时只存储了原始节点1的地址，而没有任何机制记录"原节点1对应的新节点在哪里"，你就无法完成这个赋值。

更关键的是，random 可以向前指向任意已经遍历过的节点，也可以向后指向尚未创建的节点，单次线性遍历无法在当下解决所有引用。

与列表复制的本质区别¶

Python 列表的 copy() 或切片复制之所以简单，是因为列表本质上是一段连续的内存索引，元素之间的关系由数组下标隐式维护，复制时只需按位置逐一拷贝值即可，不存在"节点之间互相持有对方引用"的问题。

链表则完全不同——节点的关系完全由显式指针维护，而 random 指针构成了一张任意的有向图，节点之间形成了复杂的相互引用网络。你复制出来的新节点如果 random 仍然指向原链表的节点，就不是真正的深拷贝，两份链表在逻辑上依然耦合在一起。

一句话总结¶

本题的重点不是"遍历"，而是在创建新节点的同时，如何正确地将所有 random 指针也重定向到新链表内部的对应节点。哈希表的作用正是建立这张"原节点 → 新节点"的映射，以便在任意顺序下都能找到正确的引用目标。

只有 `next` 指针的链表复制¶

这种情况下，单次遍历即可完成，逻辑非常直接。

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def copy_linked_list(head: Node) -> Node:
    if not head:
        return None

    dummy = Node(0)
    cur_new = dummy
    cur_old = head

    while cur_old:
        new_node = Node(cur_old.val) # 创建新节点
        cur_new.next = new_node
        cur_new = cur_new.next
        cur_old = cur_old.next

    return dummy.head

之所以单次遍历就够，是因为 next 指针只会指向下一个节点，方向严格单向且与遍历顺序完全一致——当你创建当前节点的副本时，它的 next 所指向的目标尚不存在，但没有关系，下一轮循环自然会创建它并完成连接。整个过程中不存在任何"需要引用一个还不知道在哪里的节点"的情况。

这也从反面印证了 random 指针的特殊性：一旦指针可以指向链表中的任意位置，遍历顺序就无法保证引用目标已经被创建，必须引入额外的映射机制。

双向链表的复制¶

双向链表每个节点同时持有 prev 和 next 两个指针，但由于这两个指针的方向都是确定且有序的（prev 指向前一个，next 指向后一个），遍历顺序与指针方向完全对应，因此同样只需单次遍历即可完成，本质上与单向链表没有区别。

class Node:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

def copy_doubly_linked_list(head: Node) -> Node:
    if not head:
        return None

    dummy = Node(0)
    cur_old = head
    cur_new = dummy

    while cur_old:
        new_node = Node(cur_old.val) # 创建新节点
        cur_new.next = new_node      # 链接下一节点
        new_node.prev = cur_new      # 链接上一节点
        cur_new = new_node
        cur_old = cur_old.next

    return dummy.next

关键在于，当创建 new_node 并设置其 prev 时，前一个新节点已经存在（就是 cur_new），无需任何额外的映射机制。prev 和 next 都在遍历过程中被自然地、按序地补全。

这进一步说明了一个规律：指针能否在单次遍历中被正确赋值，取决于其目标节点在遍历顺序下是否已经存在。 单向链表、双向链表的指针目标始终是"当前节点的邻居"，因此不成问题；而 random 指针的目标是链表中的任意节点，才需要引入哈希表作为"提前登记"的手段。

在编程中，值相同并不等于对象相同。两个对象即便携带完全一致的数据，只要是通过独立的构造语句创建的，它们在内存中就是两个互不相干的实体。一旦程序的某处通过一个引用修改或关联了其中一个，另一个不会受到任何影响。因此，当你需要在多处引用"同一个对象"时，必须确保所有引用都指向同一次构造所产生的那个实例，而不是各自独立创建的"长相相同的副本"。

In [ ]:

Copied!





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]':
        if not head:
            return None

        # 第一次遍历：创建所有新节点，建立 old -> new 的映射
        old_to_new = {}
        cur = head
        while cur:
            old_to_new[cur] = Node(cur.val)
            cur = cur.next

        # 第二次遍历：补全 next 和 random 指针
        cur = head
        while cur:
            if cur.next:
                old_to_new[cur].next = old_to_new[cur.next]
            if cur.random:
                old_to_new[cur].random = old_to_new[cur.random]
            cur = cur.next

        return old_to_new[head]

# **复杂度：** 时间 O(n)，空间 O(n)（哈希表）。
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]':
        if not head:
            return None

        # 第一次遍历：创建所有新节点，建立 old -> new 的映射
        old_to_new = {}
        cur = head
        while cur:
            old_to_new[cur] = Node(cur.val)
            cur = cur.next

        # 第二次遍历：补全 next 和 random 指针
        cur = head
        while cur:
            if cur.next:
                old_to_new[cur].next = old_to_new[cur.next]
            if cur.random:
                old_to_new[cur].random = old_to_new[cur.random]
            cur = cur.next

        return old_to_new[head]

# **复杂度：** 时间 O(n)，空间 O(n)（哈希表）。

In [ ]:

Copied!





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]':
        if not head:
            return None

        # Step 1：将副本节点插入原节点之后
        cur = head
        while cur:
            new_node = Node(cur.val)
            new_node.next = cur.next
            cur.next = new_node
            cur = new_node.next

        # Step 2：设置副本节点的 random 指针
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next

        # Step 3：拆分链表，还原原链表
        old_head = head
        new_head = head.next
        cur_old, cur_new = old_head, new_head
        while cur_old:
            cur_old.next = cur_new.next
            cur_old = cur_old.next
            if cur_old:
                cur_new.next = cur_old.next
            cur_new = cur_new.next

        return new_head
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]':
        if not head:
            return None

        # Step 1：将副本节点插入原节点之后
        cur = head
        while cur:
            new_node = Node(cur.val)
            new_node.next = cur.next
            cur.next = new_node
            cur = new_node.next

        # Step 2：设置副本节点的 random 指针
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next

        # Step 3：拆分链表，还原原链表
        old_head = head
        new_head = head.next
        cur_old, cur_new = old_head, new_head
        while cur_old:
            cur_old.next = cur_new.next
            cur_old = cur_old.next
            if cur_old:
                cur_new.next = cur_old.next
            cur_new = cur_new.next

        return new_head

节点交织法的核心思想这种方法的本质是：利用物理位置替代哈希表，将"原节点 → 副本节点"的映射关系直接编码进链表的结构本身。具体而言，通过将每个副本节点紧接插入其对应原节点之后，使得任意一个原节点 node 的副本必然就是 node.next。这一相邻关系在整个操作过程中始终成立，因此在设置 random 指针时，无需借助任何外部数据结构，只需一句 cur.random.next 即可从原节点的 random 目标直接"跳到"该目标的副本。映射关系不是存储在哈希表里，而是隐含在链表自身的拓扑结构中。完成 random 指针的赋值后，再通过一次拆分遍历将两条链表分离，同时还原原链表，最终得到完整独立的深拷贝。

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 [49]:

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

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。
        """
        # 创建一个虚拟头节点，方便我们构建新的有序链表
        cur = dummy = ListNode(0)
        # 像拉拉链一样，比较 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)
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。
        """
        # 创建一个虚拟头节点，方便我们构建新的有序链表
        cur = dummy = ListNode(0)
        # 像拉拉链一样，比较 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)

<__main__.ListNode object at 0x000001B46B7CBD10>

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 [51]:

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

LRU 缓存基础知识¶

一、什么是缓存（Cache）¶

缓存是一块容量有限、访问极快的存储区域。当数据量超过容量时，必须淘汰一部分旧数据，腾出空间。

核心问题：该淘汰谁？ 这就是淘汰策略。

二、LRU 是什么¶

LRU = Least Recently Used（最近最少使用）

淘汰规则：最久没被使用的数据，优先淘汰。

生活类比：你的书桌只能放 3 本书，每次用完一本放回桌上。桌子满了需要放新书时，把最久没碰过的那本放回书架。

三、用示例手动模拟（容量=2）¶

put(1,1)          缓存：[1]          最近使用顺序：1（最新）
put(2,2)          缓存：[1, 2]       最近使用顺序：2（最新）→ 1
get(1)   → 1      缓存：[1, 2]       最近使用顺序：1（最新）→ 2   ← 1被访问，移到最新
put(3,3)          缓存满了！淘汰最久未用的 2
                  缓存：[1, 3]       最近使用顺序：3（最新）→ 1
get(2)   → -1     已被淘汰，不存在
put(4,4)          缓存满了！淘汰最久未用的 1
                  缓存：[3, 4]       最近使用顺序：4（最新）→ 3
get(1)   → -1     已被淘汰
get(3)   → 3      ✅
get(4)   → 4      ✅

四、O(1) 的难点在哪里¶

两个操作需要 O(1)：

操作	需要什么
`get(key)`	快速查找 key 是否存在 → 哈希表
维护使用顺序，淘汰最久未用	快速移动节点到"最新"位置，快速删除"最旧"节点 → 双向链表

单独用哈希表：查找 O(1)，但无法维护顺序。
单独用链表：顺序清晰，但查找 O(n)。
两者结合 = O(1) 全搞定。

五、数据结构设计¶

哈希表：key → 链表节点（直接定位）

双向链表：维护使用顺序
┌──────┐    ┌──────┐    ┌──────┐    ┌──────┐
│dummy │ ↔  │  3   │ ↔  │  1   │ ↔  │dummy │
│ head │    │(旧)  │    │(新)  │    │ tail │
└──────┘    └──────┘    └──────┘    └──────┘
  最久未用 ←──────────────────→ 最近使用

链表头部（head 右边）= 最久未用 → 淘汰这里
链表尾部（tail 左边）= 最近使用 → 每次访问/插入移到这里
两个 dummy 节点（头尾哨兵）：避免边界判断，与 swapPairs 的 dummy 同理

六、每个操作的动作¶

get(key)：

哈希表查 key → 不存在返回 -1
存在 → 把该节点移到链表尾部（标记为最近使用）→ 返回值

put(key, value)：

key 已存在 → 更新值，移到尾部
key 不存在：
- 新建节点插入尾部，哈希表记录
- 若超出容量 → 删除链表头部节点，同时从哈希表删除

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!





class Node:
    def __init__(self, key=0, val=0):
        self.key  = key
        self.val  = val
        self.prev = None
        self.next = None


class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap  = {}                  # key → Node

        # 两个哨兵节点，永远不存真实数据
        self.head = Node()                  # 最久未用端
        self.tail = Node()                  # 最近使用端
        self.head.next = self.tail
        self.tail.prev = self.head

    # ── 基础操作1：从链表中摘除某个节点 ──────────────────────
    def _remove(self, node: Node):
        node.prev.next = node.next
        node.next.prev = node.prev

    # ── 基础操作2：将节点插入链表尾部（标记为最近使用）────────
    def _push_to_tail(self, node: Node):
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev      = node

    # ── get ──────────────────────────────────────────────────
    def get(self, key: int) -> int:
        if key not in self.hashmap:
            return -1
        node = self.hashmap[key]
        self._remove(node)           # 从原位置摘除
        self._push_to_tail(node)     # 移到尾部 = 标记为最近使用
        return node.val

    # ── put ──────────────────────────────────────────────────
    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            node = self.hashmap[key]
            node.val = value
            self._remove(node)
            self._push_to_tail(node)
        else:
            node = Node(key, value)
            self.hashmap[key] = node
            self._push_to_tail(node)

            if len(self.hashmap) > self.capacity:
                # 淘汰链表头部（head 右边）= 最久未用
                lru_node = self.head.next
                self._remove(lru_node)
                del self.hashmap[lru_node.key]  # ← 注意：用 node.key 而不是 key


# 链表状态变化图
# 初始：
# head <-> tail

# put(1,1)：
# head <-> [1] <-> tail

# put(2,2)：
# head <-> [1] <-> [2] <-> tail

# get(1)：  → 1 移到尾部
# head <-> [2] <-> [1] <-> tail

# put(3,3)：容量满，淘汰 head 右边的 [2]
# head <-> [1] <-> [3] <-> tail

# del self.hashmap[lru_node.key]   # ✅ 用被淘汰节点自身的 key
# del self.hashmap[key]            # ❌ key 是本次 put 的新 key，完全不同
class Node:
    def __init__(self, key=0, val=0):
        self.key  = key
        self.val  = val
        self.prev = None
        self.next = None


class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap  = {}                  # key → Node

        # 两个哨兵节点，永远不存真实数据
        self.head = Node()                  # 最久未用端
        self.tail = Node()                  # 最近使用端
        self.head.next = self.tail
        self.tail.prev = self.head

    # ── 基础操作1：从链表中摘除某个节点 ──────────────────────
    def _remove(self, node: Node):
        node.prev.next = node.next
        node.next.prev = node.prev

    # ── 基础操作2：将节点插入链表尾部（标记为最近使用）────────
    def _push_to_tail(self, node: Node):
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev      = node

    # ── get ──────────────────────────────────────────────────
    def get(self, key: int) -> int:
        if key not in self.hashmap:
            return -1
        node = self.hashmap[key]
        self._remove(node)           # 从原位置摘除
        self._push_to_tail(node)     # 移到尾部 = 标记为最近使用
        return node.val

    # ── put ──────────────────────────────────────────────────
    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            node = self.hashmap[key]
            node.val = value
            self._remove(node)
            self._push_to_tail(node)
        else:
            node = Node(key, value)
            self.hashmap[key] = node
            self._push_to_tail(node)

            if len(self.hashmap) > self.capacity:
                # 淘汰链表头部（head 右边）= 最久未用
                lru_node = self.head.next
                self._remove(lru_node)
                del self.hashmap[lru_node.key]  # ← 注意：用 node.key 而不是 key


# 链表状态变化图
# 初始：
# head <-> tail

# put(1,1)：
# head <-> [1] <-> tail

# put(2,2)：
# head <-> [1] <-> [2] <-> tail

# get(1)：  → 1 移到尾部
# head <-> [2] <-> [1] <-> tail

# put(3,3)：容量满，淘汰 head 右边的 [2]
# head <-> [1] <-> [3] <-> tail

# del self.hashmap[lru_node.key]   # ✅ 用被淘汰节点自身的 key
# del self.hashmap[key]            # ❌ key 是本次 put 的新 key，完全不同

链表

何时需要虚拟头节点（Dummy Node）¶

不需要 Dummy Node 的题型¶

需要 Dummy Node 的题型¶

本质解释¶

总结一句话¶

相交链表（LeetCode 160）¶

206 反转链表¶

234. 回文链表¶

141. 环形链表¶

142. 环形链表 II¶

21合并两个有序链表¶

2. 两数相加¶

19. 删除链表的倒数第 N 个结点¶

24. 两两交换链表中的节点¶

25. K 个一组翻转链表¶

138. 随机链表的复制¶

为什么"随机链表的复制"并不简单？¶

普通遍历复制为何不够？¶

与列表复制的本质区别¶

一句话总结¶

只有 next 指针的链表复制¶

双向链表的复制¶

148. 排序链表¶

23. 合并 K 个升序链表¶

LRU 缓存基础知识¶

一、什么是缓存（Cache）¶

二、LRU 是什么¶

三、用示例手动模拟（容量=2）¶

四、O(1) 的难点在哪里¶

五、数据结构设计¶

六、每个操作的动作¶

146. LRU 缓存¶

只有 `next` 指针的链表复制¶