03-链表（Linked List）详解¶

重要性：⭐⭐⭐⭐⭐ 难度：⭐⭐⭐ 学习时间：3-4天 前置知识：指针基础（C++）

📚 目录¶

什么是链表
链表的内存结构
链表类型
链表操作详解
经典面试题
链表vs数组
练习题

什么是链表？¶

基本概念¶

链表是一种通过指针连接的线性数据结构，每个元素包含数据和指向下一个元素的指针。

生活中的例子¶

想象一列火车：

Text Only

[车头] → [车厢1] → [车厢2] → [车厢3] → [车厢尾]
  ↓        ↓         ↓         ↓         ↓
 数据1   数据2     数据3     数据4     数据5

每节车厢（节点）存放货物（数据）
车厢之间通过挂钩（指针）连接
可以随时添加或移除车厢

为什么学链表？¶

✅ 优点： 1. 动态大小：可以在运行时动态增长/缩小 2. 高效插入/删除：只需改变指针，O(1)时间 3. 内存灵活：不需要连续内存空间

❌ 缺点： 1. 无随机访问：必须从头遍历，O(n)时间 2. 额外空间：每个节点需要存储指针 3. 缓存不友好：内存不连续，缓存命中率低

链表的内存结构¶

可视化¶

Text Only

内存地址:  1000    2000    3000    4000    5000
           ┌────┐  ┌────┐  ┌────┐  ┌────┐  ┌────┐
节点内容:  │ 10 │  │ 20 │  │ 30 │  │ 40 │  │NULL│
           │  ──┼──│  ──┼──│  ──┼──│  ──┼──│    │
           └────┘  └────┘  └────┘  └────┘  └────┘
             ↓        ↓        ↓        ↓
           下一个:   2000     3000     4000     NULL

注意：节点可以在内存的任意位置，不连续！

图：链表在内存中的分散存储结构，节点通过指针连接

节点结构¶

Python

class ListNode:
    """链表节点"""
    def __init__(self, val=0, next=None):
        self.val = val      # 数据
        self.next = next    # 指向下一个节点的指针

C++

struct ListNode {  // struct结构体：自定义复合数据类型
    int val;         // 数据
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(nullptr) {}
};

与数组对比¶

Text Only

数组（连续内存）:
[10] [20] [30] [40] [50]
 ↓    ↓    ↓    ↓    ↓
1000 1004 1008 1012 1016  ← 连续地址

链表（分散内存）:
[10] ─────→ [20] ─────→ [30] ─────→ [40] ─────→ NULL
 ↓           ↓           ↓           ↓
1000        2500        3800        5200  ← 任意地址

链表类型¶

1️⃣ 单向链表（Singly Linked List）¶

结构：每个节点只有一个指针，指向下一个节点。

Text Only

Head → [A] → [B] → [C] → NULL

节点定义：

Python

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

2️⃣ 双向链表（Doubly Linked List）¶

结构：每个节点有两个指针，分别指向前一个和后一个节点。

Text Only

NULL ← [A] ↔ [B] ↔ [C] → NULL

节点定义：

Python

class DoublyListNode:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev  # 指向前一个节点
        self.next = next  # 指向后一个节点

优点： - 可以双向遍历 - 删除节点更方便（不需要前驱节点）

缺点： - 每个节点多一个指针，占用更多空间 - 插入/删除需要维护两个指针

3️⃣ 循环链表（Circular Linked List）¶

结构：最后一个节点的指针指向头节点，形成一个环。

Text Only

    ┌─────────────────┐
    │                 ↓
Head → [A] → [B] → [C]
    ↑                 │
    └─────────────────┘

应用： - 轮询调度 - 缓冲区实现 - 游戏中的回合制

链表操作详解¶

操作1：创建链表¶

Python

def create_linked_list(values):
    """
    从列表创建链表
    """
    if not values:
        return None

    # 创建头节点
    head = ListNode(values[0])
    current = head

    # 逐个添加节点
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next

    return head

# 测试
head = create_linked_list([1, 2, 3, 4, 5])

# 遍历验证
current = head
while current:
    print(current.val, end=" → ")
    current = current.next
print("NULL")
# 输出: 1 → 2 → 3 → 4 → 5 → NULL

图解创建过程：

Text Only

输入: [1, 2, 3]

步骤1: 创建头节点
head → [1] → NULL

步骤2: 添加节点2
head → [1] → [2] → NULL
         current ↑

步骤3: 添加节点3
head → [1] → [2] → [3] → NULL
                   current ↑

操作2：遍历链表 (O(n))¶

Python

def traverse(head):
    """
    遍历链表并打印所有值
    """
    current = head
    while current:
        print(current.val, end=" → ")
        current = current.next
    print("NULL")

def traverse_recursive(head):
    """
    递归遍历链表
    """
    if not head:
        print("NULL")
        return

    print(head.val, end=" → ")
    traverse_recursive(head.next)

遍历过程：

Text Only

链表: [1] → [2] → [3] → NULL

第1次循环: current = [1], 打印1, current = current.next = [2]
第2次循环: current = [2], 打印2, current = current.next = [3]
第3次循环: current = [3], 打印3, current = current.next = NULL
第4次循环: current = NULL, 退出循环

输出: 1 → 2 → 3 → NULL

操作3：查找元素 (O(n))¶

Python

def search(head, target):
    """
    在链表中查找目标值
    返回节点或None
    """
    current = head
    position = 0

    while current:
        if current.val == target:
            print(f"找到{target}，位置为{position}")
            return current
        current = current.next
        position += 1

    print(f"未找到{target}")
    return None

# 测试
head = create_linked_list([1, 2, 3, 4, 5])
search(head, 3)  # 找到3，位置为2
search(head, 10)  # 未找到10

操作4：在开头插入 (O(1))¶

Python

def insert_at_head(head, val):
    """
    在链表开头插入新节点
    """
    new_node = ListNode(val)
    new_node.next = head
    return new_node

# 测试
head = create_linked_list([2, 3, 4])
print("原链表:", end=" ")
traverse(head)

head = insert_at_head(head, 1)
print("插入后:", end=" ")
traverse(head)
# 输出: 1 → 2 → 3 → 4 → NULL

插入过程图解：

Text Only

插入前:
head → [2] → [3] → [4] → NULL

创建新节点:
[1] → NULL
new_node

连接新节点到头部:
[1] → [2] → [3] → [4] → NULL
 ↑
head = new_node

操作5：在末尾插入 (O(n))¶

Python

def insert_at_tail(head, val):
    """
    在链表末尾插入新节点
    """
    new_node = ListNode(val)

    # 空链表情况
    if not head:
        return new_node

    # 找到最后一个节点
    current = head
    while current.next:
        current = current.next

    # 连接新节点
    current.next = new_node
    return head

# 测试
head = create_linked_list([1, 2, 3])
print("原链表:", end=" ")
traverse(head)

head = insert_at_tail(head, 4)
print("插入后:", end=" ")
traverse(head)
# 输出: 1 → 2 → 3 → 4 → NULL

插入过程图解：

Text Only

插入前:
head → [1] → [2] → [3] → NULL

遍历到最后:
head → [1] → [2] → [3] → NULL
                       current ↑

创建新节点并连接:
head → [1] → [2] → [3] → [4] → NULL
                       current   new_node

操作6：在指定位置插入 (O(n))¶

Python

def insert_at_position(head, val, position):
    """
    在指定位置插入新节点
    position: 从0开始
    """
    # 在头部插入
    if position == 0:
        return insert_at_head(head, val)

    new_node = ListNode(val)
    current = head

    # 找到插入位置的前一个节点
    for _ in range(position - 1):
        if not current:
            print("位置超出范围")
            return head
        current = current.next

    # 插入节点
    new_node.next = current.next
    current.next = new_node

    return head

# 测试
head = create_linked_list([1, 2, 4, 5])
print("原链表:", end=" ")
traverse(head)

head = insert_at_position(head, 3, 2)
print("在位置2插入3:", end=" ")
traverse(head)
# 输出: 1 → 2 → 3 → 4 → 5 → NULL

插入过程图解：

Text Only

原链表:
head → [1] → [2] → [4] → [5] → NULL
索引:    0     1     2     3

在位置2插入3:

步骤1: 找到位置1的节点（即位置2的前一个节点）
head → [1] → [2] → [4] → [5] → NULL
               current ↑

步骤2: 创建新节点
[3] → NULL
new_node

步骤3: 连接
[2] ──→ [3] ──→ [4]
current  new_node

最终:
head → [1] → [2] → [3] → [4] → [5] → NULL

操作7：删除头节点 (O(1))¶

Python

def delete_head(head):
    """
    删除链表的头节点
    """
    if not head:
        return None

    new_head = head.next
    head.next = None  # 断开连接
    return new_head

# 测试
head = create_linked_list([1, 2, 3, 4, 5])
print("原链表:", end=" ")
traverse(head)

head = delete_head(head)
print("删除头节点:", end=" ")
traverse(head)
# 输出: 2 → 3 → 4 → 5 → NULL

操作8：删除尾节点 (O(n))¶

Python

def delete_tail(head):
    """
    删除链表的尾节点
    """
    if not head:
        return None

    # 只有一个节点
    if not head.next:
        return None

    # 找到倒数第二个节点
    current = head
    while current.next.next:
        current = current.next

    # 删除最后一个节点
    current.next = None
    return head

# 测试
head = create_linked_list([1, 2, 3, 4, 5])
print("原链表:", end=" ")
traverse(head)

head = delete_tail(head)
print("删除尾节点:", end=" ")
traverse(head)
# 输出: 1 → 2 → 3 → 4 → NULL

操作9：删除指定节点 (O(n))¶

Python

def delete_node(head, val):
    """
    删除第一个值为val的节点
    """
    if not head:
        return None

    # 删除头节点
    if head.val == val:
        return head.next

    current = head

    # 查找要删除的节点
    while current.next and current.next.val != val:
        current = current.next

    # 找到并删除
    if current.next:
        current.next = current.next.next

    return head

# 测试
head = create_linked_list([1, 2, 3, 4, 5])
print("原链表:", end=" ")
traverse(head)

head = delete_node(head, 3)
print("删除3:", end=" ")
traverse(head)
# 输出: 1 → 2 → 4 → 5 → NULL

删除过程图解：

Text Only

原链表:
head → [1] → [2] → [3] → [4] → [5] → NULL

删除值为3的节点:

步骤1: 找到节点3的前一个节点（节点2）
head → [1] → [2] → [3] → [4] → [5] → NULL
               current ↑

步骤2: 跳过节点3
current.next = current.next.next
即 [2].next = [4]

结果:
head → [1] → [2] ─────→ [4] → [5] → NULL
                    [3] → (被删除)

操作10：反转链表 ⭐⭐⭐⭐⭐¶

Python

def reverse_list(head):
    """
    反转链表（迭代版）
    时间：O(n)
    空间：O(1)
    """
    prev = None
    current = head

    while current:
        # 保存下一个节点
        next_node = current.next

        # 反转指针
        current.next = prev

        # 移动指针
        prev = current
        current = next_node

    return prev

def reverse_list_recursive(head):
    """
    反转链表（递归版）
    时间：O(n)
    空间：O(n) - 递归栈
    """
    if not head or not head.next:
        return head

    # 递归反转后面的链表
    new_head = reverse_list_recursive(head.next)

    # 反转当前节点
    head.next.next = head
    head.next = None

    return new_head

# 测试
head = create_linked_list([1, 2, 3, 4, 5])
print("原链表:", end=" ")
traverse(head)

head = reverse_list(head)
print("反转后:", end=" ")
traverse(head)
# 输出: 5 → 4 → 3 → 2 → 1 → NULL

反转过程图解（迭代版）：

Text Only

初始: NULL ← [1]   [2] → [3] → [4] → [5] → NULL
              ↑    ↑
            prev current

第1次迭代:
保存next: next_node = [2]
反转: [1].next = NULL
移动: prev = [1], current = [2]
结果: NULL ← [1]   [2] → [3] → [4] → [5] → NULL
                   ↑    ↑
                 prev current

第2次迭代:
保存next: next_node = [3]
反转: [2].next = [1]
移动: prev = [2], current = [3]
结果: NULL ← [1] ← [2]   [3] → [4] → [5] → NULL
                        ↑    ↑
                      prev current

第3次迭代:
结果: NULL ← [1] ← [2] ← [3]   [4] → [5] → NULL
                             ↑    ↑
                           prev current

第4次迭代:
结果: NULL ← [1] ← [2] ← [3] ← [4]   [5] → NULL
                                  ↑    ↑
                                prev current

第5次迭代:
结果: NULL ← [1] ← [2] ← [3] ← [4] ← [5]   NULL
                                        ↑    ↑
                                      prev current

结束: current = NULL, 返回 prev = [5]
最终: NULL ← [1] ← [2] ← [3] ← [4] ← [5]
                                         ↑
                                       new_head

图：使用迭代法反转链表的逐步过程

操作11：合并两个有序链表 ⭐⭐⭐⭐⭐¶

Python

def merge_two_lists(list1, list2):
    """
    合并两个有序链表
    时间：O(n + m)
    空间：O(1)
    """
    # 创建哑节点
    dummy = ListNode(0)
    current = dummy

    # 比较并合并
    while list1 and list2:
        if list1.val < list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next

    # 连接剩余部分
    current.next = list1 if list1 else list2

    return dummy.next

# 测试
list1 = create_linked_list([1, 3, 5])
list2 = create_linked_list([2, 4, 6])

print("链表1:", end=" ")
traverse(list1)
print("链表2:", end=" ")
traverse(list2)

merged = merge_two_lists(list1, list2)
print("合并:", end=" ")
traverse(merged)
# 输出: 1 → 2 → 3 → 4 → 5 → 6 → NULL

合并过程图解：

Text Only

list1: [1] → [3] → [5] → NULL
list2: [2] → [4] → [6] → NULL

步骤1: 比较1和2，1更小
dummy → [1]
list1: [3] → [5] → NULL
list2: [2] → [4] → [6] → NULL

步骤2: 比较3和2，2更小
dummy → [1] → [2]
list1: [3] → [5] → NULL
list2: [4] → [6] → NULL

步骤3: 比较3和4，3更小
dummy → [1] → [2] → [3]
list1: [5] → NULL
list2: [4] → [6] → NULL

步骤4: 比较5和4，4更小
dummy → [1] → [2] → [3] → [4]
list1: [5] → NULL
list2: [6] → NULL

步骤5: 比较5和6，5更小
dummy → [1] → [2] → [3] → [4] → [5]
list1: NULL
list2: [6] → NULL

步骤6: list1为空，连接list2剩余部分
dummy → [1] → [2] → [3] → [4] → [5] → [6] → NULL

完成！

经典面试题¶

题目1：判断链表是否有环¶

问题描述：给定一个链表，判断链表中是否有环。

示例：

Text Only

输入：head = [3, 2, 0, -4], pos = 1（表示尾节点连接到索引1的节点）
输出：true
解释：链表中有一个环

解法1：哈希表（O(n)空间）

Python

def has_cycle_hash(head):
    """
    哈希表解法
    时间：O(n)
    空间：O(n)
    """
    visited = set()
    current = head

    while current:
        if current in visited:
            return True
        visited.add(current)
        current = current.next

    return False

解法2：快慢指针（O(1)空间）

Python

def has_cycle_two_pointers(head):
    """
    快慢指针解法（Floyd判圈算法）
    时间：O(n)
    空间：O(1)

    核心思想：
    - 慢指针每次走1步
    - 快指针每次走2步
    - 如果有环，快指针一定会追上慢指针
    """
    if not head or not head.next:
        return False

    slow = head
    fast = head.next

    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next

    return True

# 测试
# 创建有环链表
head = ListNode(3)
node2 = ListNode(2)
node3 = ListNode(0)
node4 = ListNode(-4)

head.next = node2
node2.next = node3
node3.next = node4
node4.next = node2  # 形成环

print(f"链表是否有环: {has_cycle_two_pointers(head)}")  # True

快慢指针图解：

Text Only

无环情况:
[1] → [2] → [3] → [4] → NULL
 ↑     ↑
慢    快

慢: [1] → [2] → [3] → [4] → NULL
快: [1] → [3] → NULL（快指针先到达终点）

返回 False ✓

有环情况:
         ┌─────────────────┐
         │                 ↓
[3] → [2] → [0] → [-4]
 ↑     ↑
慢    快

第1步: 慢=[2], 快=[0]
第2步: 慢=[0], 快=[2]
第3步: 慢=[-4], 快=[0]
第4步: 慢=[2], 快=[2] ✓ 相遇！

返回 True ✓

图：快慢指针算法检测链表中是否存在环

题目2：找链表的中间节点¶

问题描述：给定一个头节点为 head 的非空单链表，返回链表的中间节点。如果有两个中间节点，则返回第二个中间节点。

示例：

Text Only

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

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

解法：快慢指针

Python

def middle_node(head):
    """
    快慢指针找中间节点
    时间：O(n)
    空间：O(1)

    核心思想：
    - 慢指针每次走1步
    - 快指针每次走2步
    - 快指针到达终点时，慢指针正好在中间
    """
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

# 测试
head1 = create_linked_list([1, 2, 3, 4, 5])
mid1 = middle_node(head1)
print(f"中间节点: {mid1.val}")  # 3

head2 = create_linked_list([1, 2, 3, 4, 5, 6])
mid2 = middle_node(head2)
print(f"中间节点: {mid2.val}")  # 4

快慢指针图解：

Text Only

链表: [1] → [2] → [3] → [4] → [5]

初始: slow=[1], fast=[1]

第1次: slow=[2], fast=[3]
第2次: slow=[3], fast=[5]
第3次: fast.next=NULL，停止

返回 slow=[3] ✓

---

链表: [1] → [2] → [3] → [4] → [5] → [6]

初始: slow=[1], fast=[1]

第1次: slow=[2], fast=[3]
第2次: slow=[3], fast=[5]
第3次: slow=[4], fast=NULL（fast.next.next=NULL）

返回 slow=[4] ✓

题目3：删除链表的倒数第N个节点¶

问题描述：给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头节点。

示例：

Text Only

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

解法：双指针（一次遍历）

Python

def remove_nth_from_end(head, n):
    """
    双指针解法
    时间：O(n)
    空间：O(1)

    核心思想：
    - 使用哑节点简化边界情况
    - fast指针先走n步
    - 然后slow和fast一起走，直到fast到达末尾
    - 删除slow的下一个节点
    """
    # 创建哑节点
    dummy = ListNode(0)
    dummy.next = head

    fast = dummy
    slow = dummy

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

    # 一起走，直到fast到达末尾
    while fast:
        slow = slow.next
        fast = fast.next

    # 删除slow的下一个节点
    slow.next = slow.next.next

    return dummy.next

# 测试
head = create_linked_list([1, 2, 3, 4, 5])
print("原链表:", end=" ")
traverse(head)

head = remove_nth_from_end(head, 2)
print("删除倒数第2个节点:", end=" ")
traverse(head)
# 输出: 1 → 2 → 3 → 5 → NULL

双指针图解：

Text Only

链表: [1] → [2] → [3] → [4] → [5], n=2

创建哑节点:
dummy → [1] → [2] → [3] → [4] → [5]
  ↑
slow/fast

第1步: fast先走3步（n+1）
dummy → [1] → [2] → [3] → [4] → [5]
  ↑                        ↑
slow                    fast

第2步: slow和fast一起走
dummy → [1] → [2] → [3] → [4] → [5]
         ↑                ↑
       slow            fast

第3步: 继续走
dummy → [1] → [2] → [3] → [4] → [5]
               ↑        ↑
             slow    fast

第4步: fast到达NULL，停止
dummy → [1] → [2] → [3] → [4] → [5] → NULL
                  ↑              ↑
                slow          fast

删除slow.next（节点4）:
dummy → [1] → [2] → [3] ─────→ [5] → NULL

返回 dummy.next

题目4：回文链表¶

问题描述：给定一个链表的头节点 head ，请判断其是否为回文链表。

示例：

Text Only

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

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

解法1：转数组（简单）

Python

def is_palindrome_array(head):
    """
    转数组解法
    时间：O(n)
    空间：O(n)
    """
    # 转为数组
    values = []
    current = head
    while current:
        values.append(current.val)
        current = current.next

    # 判断回文
    return values == values[::-1]  # 切片操作：[start:end:step]提取子序列

解法2：快慢指针+反转（最优）

Python

def is_palindrome_optimal(head):
    """
    快慢指针+反转链表
    时间：O(n)
    空间：O(1)

    步骤：
    1. 找到链表中点（快慢指针）
    2. 反转后半部分
    3. 比较前后两半
    4. 恢复链表（可选）
    """
    # 步骤1: 找中点
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # 步骤2: 反转后半部分
    second_half = reverse_list(slow)

    # 步骤3: 比较
    first_half = head
    result = True
    while second_half:
        if first_half.val != second_half.val:
            result = False
            break
        first_half = first_half.next
        second_half = second_half.next

    # 步骤4: 恢复链表（可选）
    # reverse_list(slow)

    return result

# 测试
head1 = create_linked_list([1, 2, 2, 1])
print(f"是否回文: {is_palindrome_optimal(head1)}")  # True

head2 = create_linked_list([1, 2])
print(f"是否回文: {is_palindrome_optimal(head2)}")  # False

过程图解：

Text Only

链表: [1] → [2] → [2] → [1]

步骤1: 找中点
慢指针: [1] → [2]
快指针: [1] → [2] → [1]
中点: 第2个[2]

步骤2: 反转后半部分
前半: [1] → [2] → NULL
后半: [1] → [2] → NULL（已反转）

步骤3: 比较
[1] → [2] → NULL
[1] → [2] → NULL
  ✓     ✓

返回 True ✓

题目5：环形链表II¶

问题描述：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

解法：快慢指针

Python

def detect_cycle(head):
    """
    快慢指针找环的入口
    时间：O(n)
    空间：O(1)

    数学证明：
    - 设头到环入口距离为a
    - 环入口到相遇点距离为b
    - 相遇点到环入口距离为c
    - 慢指针走了：a + b
    - 快指针走了：a + b + n(b + c)
    - 快指针速度是慢指针2倍：2(a + b) = a + b + n(b + c)
    - 解得：a = c
    """
    # 步骤1: 判断是否有环，并找到相遇点
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:  # 相遇
            # 步骤2: 找环的入口
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next

            return slow

    return None

链表vs数组¶

对比表¶

操作	数组	链表
访问	O(1) 随机访问	O(n) 顺序访问
头部插入	O(n) 需要移动所有元素	O(1) 只需改变指针
尾部插入	O(1) 如果有空间	O(n) 需要遍历
中间插入	O(n) 需要移动元素	O(n) 需要遍历找到位置
头部删除	O(n) 需要移动所有元素	O(1) 只需改变指针
内存	连续内存	分散内存
空间	只存储数据	数据+指针

选择建议¶

使用数组： - 需要频繁访问元素 - 数据大小已知且稳定 - 需要内存连续（如GPU计算）

使用链表： - 频繁在头部插入/删除 - 数据大小动态变化 - 不需要随机访问

练习题¶

基础题¶

获取链表长度

Python

def get_length(head):
    # 你的代码
    pass

获取链表第n个节点的值

Python

def get_nth(head, n):
    # 你的代码
    pass

清空链表

Python

def clear_list(head):
    # 你的代码
    pass

中等题¶

奇偶链表

Python

def odd_even_list(head):
    """
    将所有奇数索引节点放在偶数索引节点之前
    示例：[1, 2, 3, 4, 5] → [1, 3, 5, 2, 4]
    """
    # 你的代码
    pass

相交链表

Python

def get_intersection_node(headA, headB):
    """
    找到两个链表相交的起始节点
    """
    # 你的代码
    pass

旋转链表

Python

def rotate_right(head, k):
    """
    将链表向右旋转k个位置
    示例：[1, 2, 3, 4, 5], k=2 → [4, 5, 1, 2, 3]
    """
    # 你的代码
    pass

困难题¶

K个一组翻转链表

Python

def reverse_k_group(head, k):
    """
    每k个节点一组进行翻转
    示例：[1, 2, 3, 4, 5], k=2 → [2, 1, 4, 3, 5]
    """
    # 你的代码
    pass

复制带随机指针的链表

Python

def copy_random_list(head):
    """
    链表节点除了next指针还有random指针
    深度复制这个链表
    """
    # 你的代码
    pass

📝 总结¶

关键要点¶

✅ 链表特点： - 动态大小，非连续内存 - 插入/删除高效（O(1)） - 访问需要遍历（O(n)）

✅ 核心操作： - 遍历、插入、删除 - 反转、合并

✅ 常用技巧： - 哑节点简化边界处理 - 快慢指针（找中点、判环） - 双指针（删除倒数第n个）

✅ 经典题型： - 反转链表 - 判断环 - 合并有序链表 - 回文链表

下一步¶

继续学习： - 栈 - 后进先出的数据结构 - 队列 - 先进先出的数据结构