LeetCode 热题100 链表

LeetCode 热题100 中链表的题目分析和总结

链表的基础介绍

链表的概念

链表是一种常见的线性数据结构。与数组不同，链表中的元素（称为节点 Node）在内存中并不是连续存储的。每个节点通常包含两部分信息：

数据域 (Data)：用于存储实际的数据。
指针域 (Pointer/Reference)：用于存储指向下一个（或上一个）节点的内存地址。

通过这种“指针”的链接方式，零散的内存块被串联成了一个有序的序列。

链表的优缺点

优点：
- 动态大小：不需要在创建时预先分配固定大小的内存，可随数据的增加动态扩容。
- 插入和删除效率高：在已经获取到目标前驱节点位置的情况下，插入和删除操作只需要修改指针的指向，时间复杂度为 $O(1)$ 。
缺点：
- 随机访问效率低：不能像数组那样通过索引直接访问元素（数组为 $O(1)$ ），必须从头节点开始逐个遍历查找，时间复杂度为 $O(n)$ 。
- 额外的内存开销：每个节点都需要额外的空间来存储指针。

链表的 python 代码实现

单向链表 (Singly Linked List)

单向链表是最基础的链表形式。它的每个节点只包含一个指向下一个节点的指针（next），因此只能单向遍历。尾节点的指针指向 None。

在代码实现中，我们通常会引入附加头节点（Dummy Head，也叫虚拟节点或哨兵节点）。它是一个放置在链表真正第一个节点之前的占位节点，数据域为空。
作用：它可以极大地简化链表的操作。如果不使用附加头节点，在链表头部插入或删除时需要特殊处理头指针；有了它，所有真实节点的操作逻辑就完全一致了。

下面实现了单向链表，并重点实现了给定前向节点时的 $O(1)$ 插入与删除操作。

from typing import Any, Optional

class ListNode:
    """单向链表的节点"""
    def __init__(self, val: Any = 0, next_node: Optional['ListNode'] = None):
        self.val = val
        self.next = next_node

class SinglyLinkedList:
    """带有附加头节点的单向链表"""
    def __init__(self):
        # 创建附加头节点 (Dummy Head)
        self.dummy_head = ListNode(None)
        self.size = 0

    def insert_after(self, prev_node: ListNode, val: Any) -> None:
        """
        给定前向节点 (prev_node)，在其后面插入一个新节点。
        时间复杂度: O(1)
        """
        if not prev_node:
            raise ValueError("前向节点不能为空")

        new_node = ListNode(val)
        # 1. 新节点的 next 指向前向节点原本的下一个节点
        new_node.next = prev_node.next
        # 2. 前向节点的 next 指向新节点
        prev_node.next = new_node

        self.size += 1

    def delete_after(self, prev_node: ListNode) -> None:
        """
        给定前向节点 (prev_node)，删除其后面的那一个节点。
        时间复杂度: O(1)
        """
        if not prev_node or not prev_node.next:
            # 如果前向节点为空，或者前向节点后面没有节点，则无需删除
            return

        node_to_delete = prev_node.next
        # 直接让前向节点的 next 跨过要删除的节点，指向下一个节点
        prev_node.next = node_to_delete.next

        # 释放被删除节点的指针（良好的编程习惯）
        node_to_delete.next = None

        self.size -= 1

双向链表 (Doubly Linked List)

双向链表中的每个节点不仅包含指向下一个节点的指针 (next)，还包含一个指向上一个节点的指针 (prev)。这使得链表可以双向遍历。

为了最大化双向链表的优势并消除所有边界问题，我们通常会同时引入 虚拟头节点 (Dummy Head) 和 虚拟尾节点 (Dummy Tail)。初始化时将它们互相连接。这样无论链表是否为空，插入操作都不需要判断 next 或 prev 是否为 None。

from typing import Any, Optional

class DoubleNode:
    """双向链表的节点"""
    def __init__(self, val: Any = 0, prev_node: Optional['DoubleNode'] = None, next_node: Optional['DoubleNode'] = None):
        self.val = val
        self.prev = prev_node
        self.next = next_node

class DoublyLinkedList:
    """带有虚拟头尾节点的双向链表"""
    def __init__(self):
        # 创建虚拟头节点和虚拟尾节点
        self.dummy_head = DoubleNode(None)
        self.dummy_tail = DoubleNode(None)

        # 初始化时，将头尾节点互相连接
        self.dummy_head.next = self.dummy_tail
        self.dummy_tail.prev = self.dummy_head
        self.size = 0

    def insert_after(self, prev_node: DoubleNode, val: Any) -> None:
        """
        给定前向节点 (prev_node)，在其后面插入一个新节点。
        时间复杂度: O(1)
        """
        if not prev_node or prev_node is self.dummy_tail:
            raise ValueError("前向节点不能为空，且不能是虚拟尾节点")

        new_node = DoubleNode(val)
        next_node = prev_node.next  # 原本跟在 prev_node 后面的节点

        # 1. 建立 new_node 与 prev_node 的双向连接
        new_node.prev = prev_node
        prev_node.next = new_node

        # 2. 建立 new_node 与 next_node 的双向连接
        new_node.next = next_node
        next_node.prev = new_node

        self.size += 1

题目一：相交链表

问题介绍

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

注意：

题目数据保证整个链式结构中不存在环。
函数返回结果后，链表必须保持其原始结构。

基础示例

示例 1：

输入： intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出： Intersected at '8'
解释： 相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点是内存中不同的节点，而值为 8 的节点在内存中指向相同的位置。

示例 2：

输入： intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出： Intersected at '2'
解释： 相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入： intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出： No intersection
解释： 由于这两个链表不相交，所以 intersectVal 必须为 0。这两个链表不相交，因此返回 null。

提示：

listA 中节点数目为 $m$
listB 中节点数目为 $n$
$1 \le m, n \le 3 \times 10^4$
$1 \le \text{Node.val} \le 10^5$
$0 \le \text{skipA} \le m$
$0 \le \text{skipB} \le n$

问题分析

寻找两个链表的交点，核心难点在于两个链表在相交前的长度可能不同。这意味着如果我们同时从两个链表的头节点开始遍历，由于步调不一致，可能无法同时到达交点。

思路一：哈希表法

最直观的方法是利用哈希集合（Hash Set）来记录节点是否被访问过。注意，这里我们要存的是节点对象本身的引用（内存地址），而不是节点的值，因为不同链表中可能存在值相同但并非同一个节点的元素。

遍历链表 headA，将访问过的每一个节点存入哈希集合中。
遍历链表 headB，对于遍历到的每一个节点，检查它是否已经存在于哈希集合中。
如果在集合中找到了，说明这就是两个链表相交的起始节点，直接返回。
如果遍历完 headB 都没有找到，说明两个链表不相交，返回 null。

时间复杂度： $O(m + n)$ ，其中 $m$ 和 $n$ 分别是两个链表的长度。我们需要分别遍历两个链表各一次。
空间复杂度： $O(m)$ ，我们需要额外的哈希集合来存储链表 A 的所有节点。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        visited = set()

        # 遍历链表 A，将所有节点加入集合
        currA = headA
        while currA:
            visited.add(currA)
            currA = currA.next

        # 遍历链表 B，寻找第一个在集合中的节点
        currB = headB
        while currB:
            if currB in visited:
                return currB
            currB = currB.next

        return None

思路二：双指针法（最优解/进阶要求）

为了满足题目中提出的进阶要求（时间复杂度 $O(m + n)$ 、仅用 $O(1)$ 内存），我们可以使用极其巧妙的“双指针法”。

假设链表 A 在相交前的部分长度为 $a$ ，链表 B 在相交前的部分长度为 $b$ ，相交部分以及之后的公共长度为 $c$ 。

链表 A 的总长度为 $a + c$
链表 B 的总长度为 $b + c$

如果我们让两个指针分别从 headA 和 headB 开始走，每次走一步。

当指针 pA 走完链表 A 时，我们让它跳到链表 B 的头部继续走。
当指针 pB 走完链表 B 时，我们让它跳到链表 A 的头部继续走。

为什么这样能相遇？
指针 pA 走过的总路程为 $a + c + b$ 时，它会到达交点。
指针 pB 走过的总路程为 $b + c + a$ 时，它也会到达交点。
因为 $a + c + b = b + c + a$ ，所以无论 $a$ 和 $b$ 是否相等，两个指针一定会在相交节点相遇。

如果两个链表不相交：
$c = 0$ 。指针 pA 走过的路程为 $a + b$ 后到达 null，指针 pB 走过的路程为 $b + a$ 后也到达 null，它们同时变成 null，循环结束，正好返回 null。

时间复杂度： $O(m + n)$ ，最差情况下每个节点会被遍历两次。
空间复杂度： $O(1)$ ，只需要两个指针变量，不需要额外的存储空间。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        if not headA or not headB:
            return None

        # 初始化两个指针
        pA, pB = headA, headB

        # 两个指针相遇时结束循环，或者同时走到 null 时结束
        while pA != pB:
            # 如果 pA 走到了末尾，则从 headB 开始继续走；否则继续走下一步
            pA = pA.next if pA else headB
            # 如果 pB 走到了末尾，则从 headA 开始继续走；否则继续走下一步
            pB = pB.next if pB else headA

        # 此时 pA 和 pB 要么是相交节点，要么都是 None
        return pA

题目二：反转链表

问题介绍

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

基础示例

示例 1：

输入： head = [1,2,3,4,5]
输出： [5,4,3,2,1]

示例 2：

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

示例 3：

输入： head = []
输出： []

提示：

链表中节点的数目范围是 $[0, 5000]$
$-5000 \le \text{Node.val} \le 5000$

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

问题分析

反转链表是数据结构中最基础且最高频的考察点之一。它的核心在于改变节点之间 next 指针的指向，使得原本从 A 指向 B 的关系，变成从 B 指向 A。

思路一：迭代法（双指针法）

这是最常用、也最容易理解的方法。我们需要在遍历链表的同时，逐个修改节点的指向。为了在修改当前节点 curr 的 next 指针后还能找到原来的下一个节点，我们需要一个临时变量来保存断开的连接。

初始化两个指针：prev 指向 None（作为反转后链表的尾节点），curr 指向头节点 head。
遍历链表，只要 curr 不为空：
- 保存下一个节点： 记录 next_temp = curr.next，防止丢失后续链表。
- 反转指向： 将当前节点的 next 指向 prev（即 curr.next = prev）。
- 指针后移： 将 prev 移动到当前节点 curr 的位置，将 curr 移动到保存的 next_temp 的位置。
遍历结束后，curr 会指向 None，此时 prev 正好指向反转后的新头节点，直接返回 prev。

时间复杂度： $O(n)$ ，其中 $n$ 是链表的长度。我们需要遍历整个链表一次。
空间复杂度： $O(1)$ ，只使用了几个固定大小的指针变量，没有占用额外的线性空间。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head

        while curr:
            # 1. 临时保存当前节点的下一个节点
            next_temp = curr.next
            # 2. 将当前节点的指向反转，指向上一个节点
            curr.next = prev
            # 3. 将 prev 指针向后移动一步
            prev = curr
            # 4. 将 curr 指针向后移动一步
            curr = next_temp

        return prev

思路二：递归法（进阶思想）

递归法的核心思想是将大问题拆解为规模更小的相同问题。假设除了头节点 head 之外，后面的单链表都已经成功反转了，我们只需要处理 head 和它原来的下一个节点之间的关系。

终止条件： 如果链表为空（head == None），或者只有一个节点（head.next == None），直接返回 head，因为不需要反转。
递归调用： 对 head.next 调用反转函数，假设它返回了反转后的新头节点 new_head。
处理当前节点： 此时 head.next 节点是反转后局部链表的尾节点。我们需要让这个尾节点指回 head，即 head.next.next = head。
断开原连接： 将 head 的 next 指向 None，防止链表产生环。
返回结果： 返回递归得到的新头节点 new_head。

时间复杂度： $O(n)$ ，其中 $n$ 是链表的长度。每个节点都会被递归访问一次。
空间复杂度： $O(n)$ ，递归调用会使用隐式的系统调用栈，最坏情况下递归深度为 $n$ 。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 1. 递归终止条件：链表为空或只剩最后一个节点
        if not head or not head.next:
            return head

        # 2. 递归反转后续链表，并接收新的头节点
        new_head = self.reverseList(head.next)

        # 3. 反转当前节点和下一个节点的指向
        head.next.next = head

        # 4. 将当前节点的 next 置空，防止成环
        head.next = None

        # 5. 返回整条反转后的链表的新头节点
        return new_head

题目三：回文链表

问题介绍

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

基础示例

示例 1：

输入： head = [1,2,2,1]
输出： true

示例 2：

输入： head = [1,2]
输出： false

提示：

链表中节点数目在范围 $[1, 10^5]$ 内
$0 \le \text{Node.val} \le 9$

进阶： 你能否用 $O(n)$ 时间复杂度和 $O(1)$ 空间复杂度解决此题？

问题分析

回文结构的特点是“正着读和反着读完全一样”。对于数组，我们可以轻松地使用双指针从两端向中间逼近来进行比较；但对于单链表，由于只能单向遍历，我们无法直接获取前驱节点，这给判断带来了挑战。

思路一：将值复制到数组中后用双指针法（基础解法）

最简单直接的方法是将链表中的所有节点值提取出来，存入一个常规的数组（或列表）中。由于数组支持随机访问，我们就可以直接使用双指针法来判断该数组是否为回文数组。

遍历链表，将每个节点的值追加到一个数组 vals 中。
使用双指针，左指针 left 指向数组首位，右指针 right 指向数组末位。
比较 vals[left] 和 vals[right]：
- 如果不相等，说明不是回文链表，返回 false。
- 如果相等，将 left 右移，right 左移，继续比较，直到两指针相遇或交错。
如果全部比较都相等，返回 true。

时间复杂度： $O(n)$ ，其中 $n$ 是链表的长度。遍历链表需要 $O(n)$ 的时间，双指针判断数组需要 $O(n)$ 的时间。
空间复杂度： $O(n)$ ，我们需要一个额外的数组来存储链表中的所有值。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        vals = []
        curr = head

        # 1. 将链表的值复制到数组中
        while curr:
            vals.append(curr.val)
            curr = curr.next

        # 2. 使用双指针判断是否回文
        left, right = 0, len(vals) - 1
        while left < right:
            if vals[left] != vals[right]:
                return False
            left += 1
            right -= 1

        return True

思路二：快慢指针 + 反转后半部分链表（进阶最优解）

为了满足进阶要求中 $O(1)$ 的空间复杂度，我们需要在原链表上进行操作。核心思想是：找到链表中点，将后半部分链表反转，然后将前半部分和反转后的后半部分进行逐一比较。

这个方法巧妙地结合了“快慢指针找中点”和上一题“反转链表”的技巧：

寻找链表的中点： 使用快慢指针法。慢指针 slow 每次走一步，快指针 fast 每次走两步。当快指针走到链表末尾时，慢指针刚好走到链表的中间位置。（如果是奇数个节点，慢指针正好停在正中间；如果是偶数个节点，慢指针停在偏右的中间节点）。
反转后半部分链表： 从 slow 节点开始，将后续的链表进行反转。记录反转后的头节点（即原链表的尾节点），假设为 second_half_head。
对比两部分链表： 将前半部分（从原 head 开始）与反转后的后半部分（从 second_half_head 开始）进行逐个节点的值比较。只要在后半部分没有遍历完之前，出现了值不相等的情况，就说明不是回文，返回 false。
（可选）恢复链表： 比较完成后，最好将后半部分链表再次反转，恢复原样（虽然不恢复也能通过测试，但在实际工程中，不能随意破坏传入的数据结构）。
返回结果： 比较完毕且都相同，返回 true。

时间复杂度： $O(n)$ 。找中点、反转链表、对比比较都只需遍历局部或整体链表，总时间仍为线性的。
空间复杂度： $O(1)$ 。只使用了几个固定的指针变量，无需额外空间。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return True

        # 1. 寻找链表中点 (快慢指针)
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. 反转后半部分链表 (此时 slow 位于中点或偏右)
        prev = None
        curr = slow
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp

        # 此时 prev 是反转后的后半部分链表的头节点
        first_half = head
        second_half = prev
        result = True

        # 3. 比较前半部分和反转后的后半部分
        while second_half:
            if first_half.val != second_half.val:
                result = False
                break
            first_half = first_half.next
            second_half = second_half.next

        return result

题目四：环形链表

问题介绍

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

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

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

基础示例

示例 1：

输入： head = [3,2,0,-4], pos = 1
输出： true
解释： 链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入： head = [1,2], pos = 0
输出： true
解释： 链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入： head = [1], pos = -1
输出： false
解释： 链表中没有环。

提示：

链表中节点的数目范围是 $[0, 10^4]$
$-10^5 \le \text{Node.val} \le 10^5$
pos 为 -1 或者链表中的一个 有效索引 。

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

问题分析

判断链表中是否有环是一个非常经典的算法问题。它的难点在于，如果链表中存在环，普通的遍历操作会陷入死循环，永远无法到达 null 节点。我们需要一种机制来识别这种“无限循环”的状态。

思路一：哈希表法（基础解法）

最符合直觉的方法是记录我们已经访问过的所有节点。当我们遍历链表时，每次到达一个新节点，我们就去查一下这个节点是否之前已经来过了。

创建一个哈希集合（Hash Set）来存储访问过的节点。注意：存的是节点对象本身的引用（内存地址），而不是节点的值，因为链表中可能存在值相同的不同节点。
从头节点 head 开始遍历链表：
- 如果当前节点为 null，说明链表遍历到了尽头，不存在环，返回 false。
- 如果当前节点已经存在于哈希集合中，说明我们又绕回到了之前访问过的节点，证明链表中存在环，返回 true。
- 如果当前节点不在集合中，将其加入集合，并将指针移动到下一个节点。

时间复杂度： $O(n)$ ，其中 $n$ 是链表中的节点数。最坏情况下，我们需要遍历整个链表一次。
空间复杂度： $O(n)$ ，我们需要一个哈希集合来存储所有访问过的节点，最多需要占用 $O(n)$ 的额外空间。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        visited = set()
        curr = head

        while curr:
            # 如果当前节点已经在集合中，说明有环
            if curr in visited:
                return True
            # 否则，将节点加入集合，继续往下走
            visited.add(curr)
            curr = curr.next

        # 走到尽头，说明没有环
        return False

思路二：快慢指针法（进阶最优解 / 龟兔赛跑算法）

为了满足进阶要求中 $O(1)$ 的空间复杂度，我们需要使用著名的 “快慢指针法”（也称为 Floyd 判圈算法或龟兔赛跑算法）。

想象一下两个人在操场上跑步。如果操场是直的（无环），跑得快的人一定会先到达终点；但如果操场是环形的（有环），跑得快的人最终一定会“套圈”追上跑得慢的人。

定义两个指针，一个慢指针 slow，一个快指针 fast。初始时，它们都指向链表的头节点 head。
在遍历过程中，慢指针每次向前移动一步（slow = slow.next），快指针每次向前移动两步（fast = fast.next.next）。
如果链表中不存在环，快指针 fast 或其下一个节点 fast.next 会率先到达 null，此时可以判断为无环，返回 false。
如果链表中存在环，快指针和慢指针最终一定会在环内的某个节点相遇。也就是说，只要发现 slow == fast，就说明存在环，返回 true。

时间复杂度： $O(n)$ $O (n)$ 。
- 如果没有环，快指针大约只需遍历一半的链表即可到达尽头。
- 如果有环，快慢指针都会进入环内。假设环的长度为 $K$ ，快慢指针在环内的距离每次缩小 1 步，最多经过 $K$ 步必定相遇。因此总体时间复杂度依然是线性的。
空间复杂度： $O(1)$ 。只使用了两个额外的指针变量，内存占用为常数级别。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # 如果链表为空或只有一个节点，不可能成环
        if not head or not head.next:
            return False

        slow = head
        fast = head

        # 快指针每次走两步，所以要确保 fast 和 fast.next 都不为空
        while fast and fast.next:
            slow = slow.next         # 慢指针走一步
            fast = fast.next.next    # 快指针走两步

            # 如果快慢指针相遇，说明有环
            if slow == fast:
                return True

        # 循环正常结束，说明快指针走到了尽头，没有环
        return False

题目五：环形链表 II

问题介绍

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

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

不允许修改 链表。

基础示例

示例 1：

输入： head = [3,2,0,-4], pos = 1
输出： 返回索引为 1 的链表节点
解释： 链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入： head = [1,2], pos = 0
输出： 返回索引为 0 的链表节点
解释： 链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入： head = [1], pos = -1
输出： 返回 null
解释： 链表中没有环。

提示：

链表中节点的数目范围在范围 $[0, 10^4]$ 内
$-10^5 \le \text{Node.val} \le 10^5$
pos 的值为 -1 或者链表中的一个有效索引

进阶： 你是否可以使用 $O(1)$ 空间解决此题？

问题分析

这道题是上一道“环形链表”的升级版。上一题只需要我们回答“有没有环”，而这道题要求我们明确指出“环的入口在哪里”。这也是大厂面试中极具区分度的一道数学与数据结构相结合的经典题目。

思路一：哈希表法（基础解法）

和上一题的思路如出一辙，我们可以利用哈希集合来记录访问过的节点。当我们第一次遇到一个已经存在于集合中的节点时，这个节点必然就是环的入口。

初始化一个空的哈希集合 visited。
从头节点 head 开始遍历链表。
对于当前遍历到的节点 curr：
- 如果 curr 已经在 visited 中，说明我们再次回到了这个节点，它就是环的起始点，直接返回 curr。
- 如果不在，将 curr 存入 visited，并继续遍历下一个节点。
如果遍历到达了 null，说明链表无环，返回 null。

时间复杂度： $O(n)$ ，其中 $n$ 为链表的节点数。最坏情况下我们需要遍历每一个节点一次。
空间复杂度： $O(n)$ ，我们需要额外的哈希集合来存储最多 $n$ 个节点。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        visited = set()
        curr = head

        while curr:
            # 如果节点已经被访问过，说明这就是入环的第一个节点
            if curr in visited:
                return curr

            visited.add(curr)
            curr = curr.next

        # 遍历到尽头，说明无环
        return None

思路二：快慢指针法 + 数学推导（进阶最优解）

为了实现 $O(1)$ 的空间复杂度，我们依然需要请出“快慢指针”。但是找到它们相遇的节点还不够，我们还需要通过一点简单的数学推导来找到入口。

假设：

链表头节点到环入口的距离为 $x$ 。
环入口到快慢指针相遇点的距离为 $y$ 。
相遇点再走到环入口的距离为 $z$ 。
环的总长度为 $y + z$ 。

当快慢指针相遇时：

慢指针 slow 走过的总距离是： $x + y$
快指针 fast 走过的总距离是： $x + y + n(y + z)$ （ $n$ 是快指针在环内绕的圈数）

因为快指针的速度是慢指针的两倍，相同时间内快指针走过的距离是慢指针的两倍：

2(x + y) = x + y + n(y + z)

两边消去 $x + y$ ，得到：

x + y = n(y + z)

我们需要求的是入口位置，即 $x$ 的长度。我们将等式变形提取 $x$ ：

x = n(y + z) - y

x = (n - 1)(y + z) + (y + z) - y

x = (n - 1)(y + z) + z

这个公式的物理意义非常神奇！ 它意味着：
头节点到环入口的距离 $x$ ，等于 (相遇点到环入口的距离 $z$ ) 加上 ( $n-1$ 圈环的长度)。

因此，算法呼之欲出：

先用快慢指针找到相遇点。如果找不到（走到 null），说明无环，返回 null。
找到相遇点后，将其中一个指针（比如新建一个 ptr1）放回头节点 head，另一个指针（ptr2）保留在相遇点。
两个指针每次都只走一步，共同前进。
当它们再次相遇时，相遇的那个节点一定是环的入口节点！

时间复杂度： $O(n)$ 。第一阶段寻找相遇点的时间为 $O(n)$ ，第二阶段寻找入口点最多也只需遍历一次链表，总时间仍为线性。
空间复杂度： $O(1)$ 。只使用了常数个指针变量。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head

        # 阶段一：判断是否有环并寻找相遇点
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            # 找到相遇点，说明有环
            if slow == fast:
                # 阶段二：寻找环的入口
                ptr1 = head
                ptr2 = slow

                # 两个指针每次各走一步，相遇点即为入口
                while ptr1 != ptr2:
                    ptr1 = ptr1.next
                    ptr2 = ptr2.next

                return ptr1

        # fast 走到了链表末尾，说明无环
        return None

题目六：合并两个有序链表

问题介绍

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

基础示例

示例 1：

输入： l1 = [1,2,4], l2 = [1,3,4]
输出： [1,1,2,3,4,4]

示例 2：

输入： l1 = [], l2 = []
输出： []

示例 3：

输入： l1 = [], l2 = [0]
输出： [0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

问题分析

合并两个有序链表是经典的“双指针”应用场景，类似于归并排序（Merge Sort）中的合并阶段。因为两个链表本身已经是有序的，我们只需要从头到尾依次比较两个链表当前节点的值，把较小的那个节点连接到结果链表的末尾即可。

这里有一个非常实用的小技巧：虚拟头节点（Dummy Node / 哨兵节点）。在构建新链表时，初始状态下新链表为空，如果没有虚拟头节点，我们需要写额外的逻辑来处理新链表的第一个节点。引入一个固定的虚拟头节点可以统一所有节点的插入逻辑，最后直接返回 dummy.next 即可。

思路一：迭代法（双指针 + 虚拟头节点）

初始化： 创建一个虚拟头节点 dummy，并用一个指针 curr 指向它，curr 用来跟踪新链表的当前末尾位置。
双指针遍历： 当 l1 和 l2 都不为空时，进入循环：
- 比较 l1.val 和 l2.val 的大小。
- 如果 l1.val <= l2.val，将 curr.next 指向 l1，然后将 l1 指针向后移动一位（l1 = l1.next）。
- 反之，如果 l1.val > l2.val，将 curr.next 指向 l2，然后将 l2 指针向后移动一位（l2 = l2.next）。
- 无论连接了哪个节点，都要将 curr 指针向后移动一位（curr = curr.next），准备连接下一个节点。
处理剩余节点： 循环结束后，至少有一个链表已经遍历完了。由于原链表是有序的，我们只需要将未遍历完的那个链表的剩余部分直接接在新链表的末尾即可（即 curr.next = l1 if l1 else l2）。
返回结果： 真正的头节点是 dummy.next，返回它即可。

时间复杂度： $O(n + m)$ ，其中 $n$ 和 $m$ 分别为两个链表的长度。因为每次循环迭代中，l1 或 l2 会向前移动一步，所以最多循环 $n + m$ 次。
空间复杂度： $O(1)$ 。我们只需要几个指针，直接在原链表上修改引用，没有开辟与原链表大小成比例的额外空间。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # 创建一个虚拟头节点
        dummy = ListNode(-1)
        curr = dummy

        # 遍历两个链表，直到其中一个为空
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            # curr 指针向后移动
            curr = curr.next

        # 把剩余不为空的链表直接拼接到末尾
        curr.next = l1 if l1 else l2

        # 返回虚拟头节点的下一个节点
        return dummy.next

思路二：递归法（优雅与简洁）

合并有序链表的逻辑也天然适合递归。我们可以这样定义递归函数：合并以 l1 和 l2 为头节点的两个有序链表，并返回合并后的头节点。

终止条件：
- 如果 l1 为空，合并结果直接是 l2。
- 如果 l2 为空，合并结果直接是 l1。
递归调用与逻辑：
- 如果 l1.val < l2.val，那么 l1 应该是合并后链表的头节点。那它后面的节点（l1.next）应该是什么呢？应该是 l1 余下的部分和整个 l2 合并的结果。所以我们递归调用 l1.next = self.mergeTwoLists(l1.next, l2)，然后返回 l1。
- 反之，如果 l1.val >= l2.val，同理，l2 应该是头节点，它的下一个节点应该是 l2 余下的部分和整个 l1 合并的结果。所以 l2.next = self.mergeTwoLists(l1, l2.next)，然后返回 l2。

时间复杂度： $O(n + m)$ 。每次递归调用都会将指针后移，直到某一个链表为空，总共最多调用 $n + m$ 次。
空间复杂度： $O(n + m)$ 。递归调用会消耗栈空间，栈的深度最多为 $n + m$ 。虽然代码非常简洁优雅，但在实际工程中，如果链表非常长，可能会有栈溢出（Stack Overflow）的风险。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # 1. 递归终止条件
        if not l1:
            return l2
        if not l2:
            return l1

        # 2. 比较当前节点的值，决定谁是头节点，并递归处理剩余部分
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

这是一份完全按照你提供的模板格式生成的 Markdown 文档。

题目七：两数相加

问题介绍

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

基础示例

示例 1：

输入： l1 = [2,4,3], l2 = [5,6,4]
输出： [7,0,8]
解释： 342 + 465 = 807.

示例 2：

输入： l1 = [0], l2 = [0]
输出： [0]

示例 3：

输入： l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出： [8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
$0 \le \text{Node.val} \le 9$
题目数据保证列表表示的数字不含前导零

问题分析

这道题的核心在于模拟我们日常手工加法的过程。由于链表是逆序存储数字的，链表的头节点正好对应数字的个位数。这极大地简化了计算：我们可以直接从头节点开始，逐位对齐相加，并顺次处理进位。

思路：模拟加法（哨兵技巧）

我们需要同时遍历两个链表，将对应位置的节点值相加，再加上前一位的进位（初始进位为 0）。为了避免处理头节点为空的繁琐边界条件，我们可以引入一个“哨兵节点”（Dummy Node）。

初始化： 创建一个哨兵节点 dummy，它的下一个节点将是结果链表的头节点。创建一个指针 curr 指向 dummy，并初始化进位变量 carry = 0。
遍历链表： 当 l1 不为空、l2 不为空，或者 carry 不为 0 时，执行循环：
- 获取 l1 和 l2 当前节点的值。如果某个链表已经遍历完毕，则将其对应的值视为 0。
- 计算当前位的总和：total = val1 + val2 + carry。
- 更新进位：carry = total // 10。
- 计算当前位要存储的数字：total % 10，并创建一个新节点，将其连接到 curr.next。
- 移动指针：curr 向后移动，l1 和 l2 如果不为空也分别向后移动。
返回结果： 循环结束后，dummy.next 即为新链表的真实头节点，将其返回。

时间复杂度： $O(\max(m, n))$ ，其中 $m$ 和 $n$ 分别是两个链表的长度。我们需要遍历两个链表的全部位置。
空间复杂度： $O(1)$ 。返回值构建的新链表不计入空间复杂度，我们只需要常数级别的额外空间来存储指针和进位状态。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)  # 创建哨兵节点
        curr = dummy
        carry = 0  # 进位

        # 当 l1 或 l2 还有节点，或者最后还有进位时，继续循环
        while l1 or l2 or carry:
            # 获取当前节点的值，如果节点为空则补 0
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            # 计算和及进位
            total = val1 + val2 + carry
            carry = total // 10

            # 创建新节点并链接到结果链表
            curr.next = ListNode(total % 10)
            curr = curr.next

            # 指针后移
            if l1: l1 = l1.next
            if l2: l2 = l2.next

        return dummy.next

题目八：删除链表的倒数第 N 个结点

问题介绍

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶： 你能尝试使用一趟扫描实现吗？

基础示例

示例 1：

输入： head = [1,2,3,4,5], n = 2
输出： [1,2,3,5]
解释： 链表倒数第 2 个节点是值为 4 的节点，删除后链表变为 [1,2,3,5]。

示例 2：

输入： head = [1], n = 1
输出： []
解释： 链表只有一个节点，删除倒数第 1 个节点后为空链表。

示例 3：

输入： head = [1,2], n = 1
输出： [1]
解释： 删除倒数第 1 个节点（值为 2 的节点）后，剩下 [1]。

提示：

链表中结点的数目为 $sz$
$1 \le sz \le 30$
$0 \le \text{Node.val} \le 100$
$1 \le n \le sz$

问题分析

删除链表中的某个节点，常规做法是找到待删除节点的前驱节点，然后修改前驱节点的 next 指针即可。
本题的难点在于：我们通常只能从头向后单向遍历链表，如何在不知道链表总长度的情况下，准确找到“倒数”第 $n$ 个节点的前驱节点？

为了方便处理删除头节点这种边界情况（例如示例 2 中删除唯一的节点），我们通常会在真正的 head 节点前人为添加一个哑节点（Dummy Node），使其指向 head。这样，所有的删除操作都可以统一处理，无需对头节点做特殊判断。

思路一：计算链表长度（两趟扫描）

最直观朴素的思路就是把“倒数”变成“正数”。

第一趟遍历： 从头节点开始遍历整个链表，统计链表的总长度 $L$ 。
计算位置： 倒数第 $n$ 个节点，实际上就是正数第 $L - n + 1$ 个节点。它的前驱节点就是第 $L - n$ 个节点。
第二趟遍历： 借助哑节点，从头开始往后走 $L - n$ 步，找到前驱节点，执行删除操作：curr.next = curr.next.next。

时间复杂度： $O(L)$ ，其中 $L$ 是链表的长度。我们需要遍历链表两次。
空间复杂度： $O(1)$ ，只需要常数级别的额外空间来存储指针和长度变量。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 获取链表长度
        def getLength(head: ListNode) -> int:
            length = 0
            while head:
                length += 1
                head = head.next
            return length

        dummy = ListNode(0, head)
        length = getLength(head)

        curr = dummy
        # 走到待删除节点的前驱节点
        for _ in range(length - n):
            curr = curr.next

        # 删除节点
        curr.next = curr.next.next

        return dummy.next

思路二：双指针法（最优解/一趟扫描）

为了满足题目中提出的进阶要求（一趟扫描），我们可以使用经典的**快慢双指针（Fast & Slow Pointers）**技巧。

想象一下两个指针之间保持一个固定的距离 $n$ 。如果前面的指针走到了链表的末尾，那么后面的指针正好就停在倒数第 $n$ 个节点的位置。

创建一个哑节点 dummy，指向 head，并将快指针 fast 和慢指针 slow 都初始化在 dummy 上。
先让 fast 指针向前移动 $n + 1$ 步。这样 fast 和 slow 之间就隔了 $n$ 个节点。
然后让 fast 和 slow 同时向前移动，每次各走一步，直到 fast 走到链表的末尾（即 fast 变为 None）。
此时，slow 指针刚好停在待删除节点的前驱节点上。我们只需执行 slow.next = slow.next.next 即可完成删除。

时间复杂度： $O(L)$ ，其中 $L$ 是链表的长度。我们只需要遍历链表一次。
空间复杂度： $O(1)$ ，只需要两个指针变量 fast 和 slow。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 创建哑节点，统一边界情况的处理
        dummy = ListNode(0, head)
        fast = dummy
        slow = dummy

        # fast 指针先向前走 n + 1 步
        for _ in range(n + 1):
            fast = fast.next

        # fast 和 slow 同时向前走，直到 fast 遍历完链表
        while fast is not None:
            fast = fast.next
            slow = slow.next

        # 此时 slow 停在待删除节点的前面，执行删除操作
        slow.next = slow.next.next

        # 返回真正的头节点
        return dummy.next

题目九：两两交换链表中的节点

问题介绍

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

基础示例

示例 1：

输入： head = [1,2,3,4]
输出： [2,1,4,3]
解释： 节点 1 和 2 交换，节点 3 和 4 交换。

示例 2：

输入： head = []
输出： []
解释： 空链表直接返回空。

示例 3：

输入： head = [1]
输出： [1]
解释： 只有一个节点，无法两两交换，直接返回原节点。

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

问题分析

这道题的核心要求是修改指针的指向，而不是简单地交换节点内部的值。由于头节点在交换过程中会发生改变（原来的第二个节点会变成新的头节点），为了统一处理逻辑并避免复杂的边界判断，引入**虚拟头节点（Dummy Node）**是最佳实践。

解决本题通常有两种经典思路：迭代法和递归法。

思路一：迭代法（虚拟头节点）

通过引入虚拟头节点 dummy，我们可以确保每次交换的两个节点都有一个固定的“前驱节点”。

创建虚拟头节点 dummy，令 dummy.next = head。
初始化一个指针 temp 指向 dummy。temp 将始终指向准备交换的两个节点的前驱节点。
当 temp 后面至少有两个节点时（即 temp.next 和 temp.next.next 都不为空），开始交换：
- 记录要交换的两个节点：node1 = temp.next，node2 = temp.next.next。
- 修改指针：
  1. temp.next = node2 （前驱节点连向第二个节点）
  2. node1.next = node2.next （第一个节点连向第三个节点/后面的链表）
  3. node2.next = node1 （第二个节点连向第一个节点，完成交换）
- 将 temp 向前移动两位，即 temp = node1，准备下一轮交换。

时间复杂度： $O(n)$ ，其中 $n$ 是链表的节点数量。我们需要遍历一遍链表。
空间复杂度： $O(1)$ ，仅使用了常数个指针变量，没有占用额外的线性空间。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        temp = dummy

        # 必须确保 temp 后面至少有两个节点才能进行交换
        while temp.next and temp.next.next:
            node1 = temp.next
            node2 = temp.next.next

            # 执行交换步骤
            temp.next = node2
            node1.next = node2.next
            node2.next = node1

            # temp 移动到下一组准备交换的节点的前面
            temp = node1

        return dummy.next

思路二：递归法

递归的思维方式更加函数式：假设链表后面的节点都已经成功按要求两两交换了，我们现在只需要集中精力处理开头的这两个节点。

终止条件： 如果当前节点为空（head is None）或者只有一个节点（head.next is None），说明没有足够的节点进行交换，直接返回 head。
定义新头节点： 原链表的第二个节点 head.next 将会成为交换后的新头节点，我们记为 newHead。
递归处理后续节点： 原来的头节点 head 需要连接到后续已经完成交换的链表上，即 head.next = self.swapPairs(newHead.next)。
完成当前层交换： 将新的头节点指向原来的头节点，即 newHead.next = head。
返回： 返回新的头节点 newHead。

时间复杂度： $O(n)$ ，其中 $n$ 是链表的节点数量。每个节点都会被访问并处理一次。
空间复杂度： $O(n)$ ，主要是递归调用栈的空间开销。每次递归消耗 $O(1)$ 空间，递归深度为 $n/2$ 。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 递归终止条件：如果没有节点或者只有一个节点，直接返回
        if not head or not head.next:
            return head

        # newHead 是当前的第二个节点，交换后它将成为这部分链表的头节点
        newHead = head.next

        # head 的下一个节点应该是后续链表交换完成后的头节点
        head.next = self.swapPairs(newHead.next)

        # newHead 指向 head，完成这两个节点的交换
        newHead.next = head

        return newHead

题目十：K 个一组翻转链表

问题介绍

给你链表的头节点 head，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

注意： 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

进阶： 你可以设计一个只用 $O(1)$ 额外内存空间的算法解决此问题吗？

基础示例

示例 1：

输入： head = [1,2,3,4,5], k = 2
输出： [2,1,4,3,5]
解释： 每 2 个节点一组进行翻转。节点 1 和 2 翻转，节点 3 和 4 翻转。节点 5 剩余，保持原样。

示例 2：

输入： head = [1,2,3,4,5], k = 3
输出： [3,2,1,4,5]
解释： 每 3 个节点一组进行翻转。节点 1、2、3 翻转。节点 4 和 5 不足 3 个，保持原样。

提示：

链表中的节点数目为 $n$
$1 \le k \le n \le 5000$
$0 \le \text{Node.val} \le 1000$

问题分析

这是一道经典的链表困难题，综合了“链表遍历”、“节点断开与重连”以及“反转链表”的操作。为了满足进阶要求中 $O(1)$ 的额外空间复杂度，我们需要在原链表上直接修改指针，而不是创建新的节点或使用递归（递归会产生 $O(n/k)$ 的调用栈空间）。

解决这道题的关键在于模块化拆解。我们可以把整个过程拆分为两个核心任务：

判断剩下的链表是否有 $k$ 个节点，如果有，把这 $k$ 个节点截取出来。
调用一个基础的“反转单链表”子函数，将这 $k$ 个节点反转，然后再拼接到原链表中。

思路：迭代法 + 局部翻转（最优解）

为了避免处理头节点发生变化时的繁琐边界条件，我们依然引入虚拟头节点（Dummy Node）。

初始化： 创建 dummy 节点指向 head。创建一个指针 pre 指向 dummy，pre 始终代表我们要翻转的 $k$ 个节点的前驱节点。
分组遍历： 每次从 pre 开始往后走 $k$ $k$ 步，找到当前组的尾节点 end。
- 如果走不到 $k$ 步 end 就变成了 None，说明剩余节点不足 $k$ 个，不需要翻转，直接结束循环。
记录与断开：
- 记录当前组的头节点：start = pre.next。
- 记录下一组的头节点：next_group = end.next。
- 将当前组与后面的链表断开：end.next = None。
局部翻转： 将以 start 为头节点的这段链表进行反转。反转后，原本的尾节点 end 变成了新的头节点，原本的头节点 start 变成了新的尾节点。
重新连接：
- 将前驱节点连向反转后的新头节点：pre.next = end。
- 将反转后的新尾节点连向后面的链表：start.next = next_group。
指针推进： 将 pre 移动到当前翻转部分的尾节点（即 start），准备处理下一组 $k$ 个节点。

时间复杂度： $O(n)$ ，其中 $n$ 是链表的节点数。每个节点会被遍历两次（一次是分组找 end，一次是执行局部翻转），所以总时间复杂度是线性的。
空间复杂度： $O(1)$ ，我们只使用了几个额外的指针变量，满足进阶要求。

Python 代码实现

# 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]:
        # 辅助函数：反转单链表，返回新的头节点
        def reverse_list(node: ListNode) -> ListNode:
            prev = None
            curr = node
            while curr:
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node
            return prev

        dummy = ListNode(0, head)
        pre = dummy

        while True:
            # 1. 检查剩余节点是否有 k 个
            end = pre
            count = 0
            while end and count < k:
                end = end.next
                count += 1

            # 如果不足 k 个，直接结束
            if not end:
                break

            # 2. 记录关键节点
            start = pre.next
            next_group = end.next

            # 3. 断开链表，准备独立翻转这 k 个节点
            end.next = None

            # 4. 执行翻转，并将翻转后的部分重新接入原链表
            # 注意：翻转后，原本的 end 变成了头，原本的 start 变成了尾
            pre.next = reverse_list(start)
            start.next = next_group

            # 5. 更新 pre，为下一轮循环做准备
            pre = start

        return dummy.next

题目十一：随机链表的复制

问题介绍

给你一个长度为 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 \le n \le 1000$
$-10^4 \le \text{Node.val} \le 10^4$
Node.random 为 null 或指向链表中的节点。

问题分析

这道题的核心难点在于 随机指针可能指向一个尚未被创建的节点。如果是普通的链表，我们只需要从头到尾遍历并逐个创建新节点即可。但因为有了 random 指针，传统的单次遍历直接复制的方法行不通。我们需要一种机制来建立“原节点”和“新节点”之间的映射关系。

思路一：哈希表法

利用哈希表（字典）来记录原节点到新节点的映射关系。我们可以分两步走：

第一遍遍历：不考虑 next 和 random 指针，只遍历原链表，为每个原节点创建一个对应的新节点，并将 原节点 -> 新节点 的键值对存入哈希表中。
第二遍遍历：再次遍历原链表。此时，我们可以通过哈希表轻松找到当前节点对应的新节点，并根据原节点的 next 和 random 指向，在哈希表中找到对应的新节点，赋值给新节点的 next 和 random。

时间复杂度： $O(n)$ ，我们需要遍历链表两次，每次操作的时间是常数级别。
空间复杂度： $O(n)$ ，我们需要额外的哈希表来存储 $n$ 个节点的映射关系。

Python 代码实现

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

        node_map = {}

        # 第一遍遍历：创建所有新节点并存入哈希表
        curr = head
        while curr:
            node_map[curr] = Node(curr.val)
            curr = curr.next

        # 第二遍遍历：构建新节点的 next 和 random 指向
        curr = head
        while curr:
            if curr.next:
                node_map[curr].next = node_map[curr.next]
            if curr.random:
                node_map[curr].random = node_map[curr.random]
            curr = curr.next

        # 返回新链表的头节点
        return node_map[head]

思路二：节点拼接与拆分法（原地修改， $O(1)$ 空间）

如果想要挑战进阶的 $O(1)$ 空间复杂度（不计算返回的新链表所占空间），我们可以巧妙地利用原链表的结构来代替哈希表。具体分为三个步骤：

复制节点并拼接：遍历原链表，为每个节点创建一个克隆节点，并将其紧挨着插在原节点之后。例如，原链表 A -> B -> C 会变成 A -> A' -> B -> B' -> C -> C'。
处理随机指针：再次遍历链表，此时可以很容易地设置克隆节点的 random 指针。如果原节点 curr 的随机指针指向了 node，那么克隆节点 curr.next 的随机指针就应该指向 node.next（即 node 的克隆节点）。
拆分链表：将这个长链表拆分成两个链表：将所有原节点分离出来恢复原状，将所有克隆节点分离出来组成所需深拷贝的新链表。

时间复杂度： $O(n)$ ，一共遍历链表三次。
空间复杂度： $O(1)$ ，没有使用额外的哈希表，仅使用了几个常数级别的指针变量。

Python 代码实现

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

        # 第一步：复制每个节点，并将其插入到原节点之后
        curr = head
        while curr:
            new_node = Node(curr.val, curr.next)
            curr.next = new_node
            curr = new_node.next

        # 第二步：设置新节点的 random 指针
        curr = head
        while curr:
            if curr.random:
                # 克隆节点的 random 指向原节点 random 的克隆节点
                curr.next.random = curr.random.next
            curr = curr.next.next

        # 第三步：拆分原链表和新链表
        curr = head
        new_head = head.next
        while curr:
            clone = curr.next
            curr.next = clone.next
            if clone.next:
                clone.next = clone.next.next
            curr = curr.next

        return new_head

题目十二：排序链表

问题介绍

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

进阶： 你可以在 $O(n \log n)$ 时间复杂度和常数级空间复杂度 $O(1)$ 下，对链表进行排序吗？

基础示例

示例 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 \times 10^4]$ 内
$-10^5 \le \text{Node.val} \le 10^5$

问题分析

要实现时间复杂度为 $O(n \log n)$ 的排序算法，我们通常会想到 归并排序（Merge Sort）、快速排序（Quick Sort） 或 堆排序（Heap Sort）。

对于单链表而言，由于它不支持随机访问，快速排序的 partition 操作和堆排序的建堆操作实现起来都比较麻烦且效率容易退化。因此，归并排序 是对链表进行排序的最理想选择。归并排序又可以分为“自顶向下”和“自底向上”两种实现方式。

思路一：自顶向下归并排序（递归法）

这是最直观的归并排序实现。我们将链表从中间一分为二，对两部分分别递归排序，然后再将两个有序链表合并。

寻找中点：利用“快慢指针”（快指针每次走两步，慢指针每次走一步）。当快指针走到链表末尾时，慢指针刚好停在链表的中间位置。将链表从慢指针处断开。
递归排序：分别对断开后的左半部分和右半部分调用排序函数。
合并链表：将两个已经排好序的子链表合并成一个有序链表（类似 LeetCode 21. 合并两个有序链表）。

时间复杂度： $O(n \log n)$ ，其中 $n$ 是链表的长度。
空间复杂度： $O(\log n)$ ，主要为递归调用栈的空间。虽然没有额外开辟数组，但递归深度为 $\log n$ ，因此 不满足 进阶要求的 $O(1)$ 空间。

Python 代码实现

# 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]:
        # base case: 链表为空或只有一个节点，直接返回
        if not head or not head.next:
            return head

        # 1. 快慢指针找中点，将链表一分为二
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        mid = slow.next
        slow.next = None # 断开链表

        # 2. 递归对左右两半部分进行排序
        left = self.sortList(head)
        right = self.sortList(mid)

        # 3. 合并两个有序链表
        return self.merge(left, right)

    def merge(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        curr = dummy
        while l1 and l2:
            if l1.val < l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next

        curr.next = l1 if l1 else l2
        return dummy.next

思路二：自底向上归并排序（迭代法 / 满足进阶要求）

为了实现严格的 $O(1)$ 空间复杂度，我们需要消除递归，改用迭代的方式来实现归并排序。

自底向上的归并排序思路是：

首先将链表按长度为 subLength = 1 进行拆分，并将相邻的两个长度为 1 的子链表合并。
然后将 subLength 乘以 2（变为 2、4、8…），重复拆分和合并的过程。
直到 subLength 大于等于链表的总长度，排序完成。

时间复杂度： $O(n \log n)$ ，其中 $n$ 是链表长度。
空间复杂度： $O(1)$ ，全程只使用了常数个指针变量，满足进阶要求。

Python 代码实现

# 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

        # 统计链表长度
        length = 0
        curr = head
        while curr:
            length += 1
            curr = curr.next

        dummy = ListNode(0, head)
        subLength = 1

        # 自底向上归并
        while subLength < length:
            prev = dummy
            curr = dummy.next

            while curr:
                # 截取第一个子链表
                head1 = curr
                for _ in range(1, subLength):
                    if curr.next:
                        curr = curr.next
                    else:
                        break

                head2 = None
                if curr.next:
                    head2 = curr.next
                    curr.next = None # 断开 head1 和 head2
                    curr = head2

                    # 截取第二个子链表
                    for _ in range(1, subLength):
                        if curr.next:
                            curr = curr.next
                        else:
                            break

                    next_node = None
                    if curr.next:
                        next_node = curr.next
                        curr.next = None # 断开 head2 和后面的链表
                    curr = next_node # 更新 curr 为下一轮合并的起点

                # 合并 head1 和 head2
                merged = self.merge(head1, head2)
                prev.next = merged
                # 将 prev 移动到合并后链表的末尾
                while prev.next:
                    prev = prev.next

            subLength *= 2

        return dummy.next

    def merge(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        curr = dummy
        while l1 and l2:
            if l1.val < l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next

        curr.next = l1 if l1 else l2
        return dummy.next

题目十三：合并 K 个升序链表

问题介绍

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

基础示例

示例 1：

输入： lists = [[1,4,5],[1,3,4],[2,6]]
输出： [1,1,2,3,4,4,5,6]
解释： 链表数组如下：
1
2
3
4
5
[ 1->4->5, 1->3->4, 2->6 ]
将它们合并到一个有序链表中得到：
1->1->2->3->4->4->5->6

示例 2：

输入： lists = []
输出： []

示例 3：

输入： lists = [[]]
输出： []

提示：

$k == \text{lists.length}$
$0 \le k \le 10^4$
$0 \le \text{lists[i].length} \le 500$
$-10^4 \le \text{lists[i][j]} \le 10^4$
lists[i] 按升序排列
lists[i].length 的总和不超过 $10^4$

问题分析

这道题是“合并两个有序链表”的进阶版。当我们需要合并 $k$ 个链表时，最朴素的做法是将第一个链表与第二个合并，然后将结果与第三个合并，以此类推。但这种“顺序合并”会导致越往后合并，链表越长，重复遍历的节点越多，效率较低。

为了优化多路归并的效率，我们通常有两种高效的解决方案：优先队列（小顶堆） 和 分治合并。

思路一：优先队列（小顶堆）

我们需要频繁地从 $k$ 个链表的头节点中找出最小的那一个。优先队列（最小堆） 天然适合解决这类动态求最小值的问题。

创建一个小顶堆。
遍历链表数组 lists，将每个链表的头节点加入堆中。
- 注意：在 Python 的 heapq 中，如果节点值相同，会尝试比较下一个元素。为了防止直接比较 ListNode 对象报错，我们可以在存入堆时，加入一个递增的索引 i 作为第二排序维度：(node.val, i, node)。
创建一个虚拟头节点 dummy 用于构建结果链表。
当堆不为空时，不断弹出堆顶元素（即当前所有链表头节点中的最小值），将其接到结果链表后面。
如果弹出的节点还有下一个节点（node.next 不为空），则将它的下一个节点也加入堆中。
重复步骤 4 和 5，直到堆为空。

时间复杂度： $O(N \log k)$ ，其中 $N$ 是所有链表节点的总数， $k$ 是链表的数量。每个节点都会被压入和弹出堆一次，堆的大小最多为 $k$ ，堆操作的时间复杂度为 $O(\log k)$ 。
空间复杂度： $O(k)$ ，堆中最多同时维护 $k$ 个元素。

Python 代码实现

import heapq
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []

        # 1. 将所有链表的头节点加入小顶堆
        # 使用索引 i 作为 tie-breaker，防止 ListNode 对象之间进行比较
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))

        dummy = ListNode(0)
        curr = dummy

        # 2. 依次弹出最小节点并拼接
        while heap:
            val, i, node = heapq.heappop(heap)
            curr.next = node
            curr = curr.next

            # 3. 如果该节点有下一个节点，将其加入堆中
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))

        return dummy.next

思路二：分治合并（归并思想）

我们可以借鉴归并排序的思想，将 $k$ 个链表配对并将同一对中的链表合并。

将 $k$ 个链表两两配对合并（第 1 个和第 2 个合并，第 3 个和第 4 个合并…）。
第一轮合并后， $k$ 个链表合并成了 $k/2$ 个链表，平均长度变为原来的两倍。
继续两两合并，直到最终只剩下一个链表为止。
底层的核心逻辑就是“合并两个有序链表”。

时间复杂度： $O(N \log k)$ ，其中 $N$ 是节点总数。第一轮合并需要遍历所有的节点，时间复杂度为 $O(N)$ ；合并的轮数为 $\log k$ 轮。
空间复杂度： $O(\log k)$ ，取决于递归调用的栈空间深度（如果是用迭代实现的分治，空间复杂度可以优化到 $O(1)$ ）。

Python 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None

        return self.merge_sort(lists, 0, len(lists) - 1)

    def merge_sort(self, lists, left, right):
        # 递归的 base case
        if left == right:
            return lists[left]
        if left > right:
            return None

        # 找到中点，分而治之
        mid = (left + right) // 2
        l1 = self.merge_sort(lists, left, mid)
        l2 = self.merge_sort(lists, mid + 1, right)

        # 合并两个有序链表
        return self.merge_two_lists(l1, l2)

    def merge_two_lists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        curr = dummy
        while l1 and l2:
            if l1.val < l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next

        curr.next = l1 if l1 else l2
        return dummy.next

题目十四：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

问题分析

要在 $O(1)$ 的时间复杂度内完成 get 和 put 操作，我们需要仔细挑选数据结构：

查询快 ( $O(1)$ )：必须要有哈希表（字典），这样才能根据 key 直接定位到数据。
插入/删除快 ( $O(1)$ )：必须要有链表。数组在移动元素时需要 $O(n)$ 的时间，而链表只需改变指针。
维持 LRU 顺序：每次访问（get 或 put）某个节点时，需要将该节点移动到链表的头部（或尾部），表示“最近被使用过”。当缓存满时，删除链表尾部（或头部）的节点，表示“淘汰最久未使用的元素”。
为什么是“双向”链表？：当我们通过哈希表在 $O(1)$ 时间内找到链表中的某个节点，并准备将其移动到头部时，我们需要知道该节点的前驱节点。如果是单链表，找前驱节点需要 $O(n)$ 的时间从头遍历；而双向链表本身就存储了前驱指针，可以做到 $O(1)$ 删除。

综上所述，最经典且标准的解法是：哈希表 + 双向链表。

思路一：自定义哈希表 + 双向链表（核心考点）

我们自己定义一个双向链表节点类 DLinkedNode，包含 key、value、prev 和 next。

初始化：创建一个哈希表 cache 记录键到节点的映射。为了避免在头部和尾部操作时处理繁琐的边界条件（如空节点），我们引入两个伪节点（Dummy Node）：head 和 tail。将它们连接起来，真实的缓存数据节点全插在它们中间。约定靠近 head 的是最近使用的，靠近 tail 的是最久未使用的。
get 操作：
- 如果 key 不在哈希表中，返回 -1。
- 如果 key 在哈希表中，通过哈希表找到该节点，将其在链表中移除，然后重新插入到 head 之后（表示刚刚被使用过）。返回节点的值。
put 操作：
- 如果 key 存在：更新节点的值，并像 get 一样把节点移动到链表头部。
- 如果 key 不存在：创建一个新节点，添加进哈希表，并插入到链表头部。接着判断容量：
  - 如果当前缓存大小超出了 capacity，则找到双向链表的尾部节点（tail.prev），将其从链表中删除，并且同步从哈希表中删除对应的 key。这就是为什么节点里必须存 key 的原因（只存 value 的话，删除了链表节点就不知道该去哈希表里删哪个键了）。

时间复杂度： 对于 put 和 get 操作，都是 $O(1)$ 。
空间复杂度： $O(\text{capacity})$ ，因为哈希表和双向链表最多只存储 capacity 个元素。

Python 代码实现

class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = dict()
        # 使用伪头部和伪尾部节点
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # 如果 key 存在，先通过哈希表定位，再移到头部
        node = self.cache[key]
        self.move_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            # 如果 key 不存在，创建一个新的节点
            node = DLinkedNode(key, value)
            # 添加进哈希表
            self.cache[key] = node
            # 添加至双向链表的头部
            self.add_to_head(node)
            self.size += 1
            if self.size > self.capacity:
                # 如果超出容量，删除双向链表的尾部节点
                removed = self.remove_tail()
                # 删除哈希表中对应的项
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            # 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node = self.cache[key]
            node.value = value
            self.move_to_head(node)

    # ---------- 链表操作的辅助函数 ----------

    def add_to_head(self, node):
        # 将节点插入到头节点之后
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def remove_node(self, node):
        # 移除存在的节点
        node.prev.next = node.next
        node.next.prev = node.prev

    def move_to_head(self, node):
        # 将节点移动到头部：先摘除，再添加到头部
        self.remove_node(node)
        self.add_to_head(node)

    def remove_tail(self):
        # 弹出尾部节点
        res = self.tail.prev
        self.remove_node(res)
        return res

思路二：利用 Python 内置数据结构 OrderedDict

在工程实践中，Python 的 collections.OrderedDict 已经完美实现了这种“保持插入/访问顺序的哈希表”功能。底层同样是哈希表和双向链表的结合。

move_to_end(key, last=False)：可以将某个键值对移动到末尾或开头（这里我们可以把末尾当成最近使用的位置）。
popitem(last=False)：可以按 FIFO 顺序删除字典的键值对。

这种方法代码极其简洁，面试时可以提一嘴，但建议主要还是手写双向链表，以体现对数据结构的扎实理解。

Python 代码实现

from collections import OrderedDict

class LRUCache(OrderedDict):

    def __init__(self, capacity: int):
        super().__init__()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self:
            return -1
        self.move_to_end(key) # 将被访问的元素移到末尾（最近使用）
        return self[key]

    def put(self, key: int, value: int) -> None:
        if key in self:
            self.move_to_end(key) # 更新已有节点，移到末尾
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last=False) # 弹出开头的元素（最久未使用）

算法程序设计

#LeetCode热题100

LeetCode 热题100 链表

https://huan-yin.github.io/2026/03/17/LeetCode热题100链表/

作者

李相越

发布于

2026年3月17日

许可协议

ViT、DiT、MMDiT架构解析上一篇

用图像来引导 Stable Diffusion 下一篇

LeetCode 热题100 链表

LeetCode 热题100 链表

链表的基础介绍

链表的概念

链表的优缺点

链表的 python 代码实现

单向链表 (Singly Linked List)

双向链表 (Doubly Linked List)

题目一：相交链表

问题介绍

基础示例

问题分析

思路一：哈希表法

思路二：双指针法（最优解/进阶要求）

题目二：反转链表

问题介绍

基础示例

问题分析

思路一：迭代法（双指针法）

思路二：递归法（进阶思想）

题目三：回文链表

问题介绍

基础示例

问题分析

思路一：将值复制到数组中后用双指针法（基础解法）

思路二：快慢指针 + 反转后半部分链表（进阶最优解）

题目四：环形链表

问题介绍

基础示例

问题分析

思路一：哈希表法（基础解法）

思路二：快慢指针法（进阶最优解 / 龟兔赛跑算法）

题目五：环形链表 II

问题介绍

基础示例

问题分析

思路一：哈希表法（基础解法）

思路二：快慢指针法 + 数学推导（进阶最优解）

题目六：合并两个有序链表

问题介绍

基础示例

问题分析

思路一：迭代法（双指针 + 虚拟头节点）

思路二：递归法（优雅与简洁）

题目七：两数相加

问题介绍

基础示例

问题分析

思路：模拟加法（哨兵技巧）

题目八：删除链表的倒数第 N 个结点

问题介绍

基础示例

问题分析

思路一：计算链表长度（两趟扫描）

思路二：双指针法（最优解/一趟扫描）

题目九：两两交换链表中的节点

问题介绍

基础示例

问题分析

思路一：迭代法（虚拟头节点）

思路二：递归法

题目十：K 个一组翻转链表

问题介绍

基础示例

问题分析

思路：迭代法 + 局部翻转（最优解）

题目十一：随机链表的复制

问题介绍

基础示例

问题分析

思路一：哈希表法

思路二：节点拼接与拆分法（原地修改，O(1)O(1)O(1) 空间）

题目十二：排序链表

问题介绍

基础示例

问题分析

思路一：自顶向下归并排序（递归法）

思路二：自底向上归并排序（迭代法 / 满足进阶要求）

题目十三：合并 K 个升序链表

问题介绍

思路二：节点拼接与拆分法（原地修改， $O(1)$ 空间）