下面我给你一份**「单链表操作详解」，从概念 → 结构 → 常见操作 → 图解思路 → 面试高频题**，一步步讲清楚，不依赖语言基础也能看懂，同时附上 C / Java / Python 通用思想。

一、什么是单链表（Single Linked List）

1️⃣ 定义

单链表是一种线性数据结构，由若干个 结点（Node） 组成：

[数据 | 指针] -> [数据 | 指针] -> [数据 | 指针] -> NULL

• 每个结点包含：
  • 数据域（data）
  • 指针域（next）：指向下一个结点
• 只能从前往后遍历

2️⃣ 与数组的区别

二、单链表的基本结构

1️⃣ 结点结构（通用）

Node {
  data
  next
}

2️⃣ 带头结点 vs 不带头结点

✔ 带头结点（推荐）

head -> node1 -> node2 -> node3 -> NULL

优点：

• 插入、删除统一处理
• 不用单独判断空链表

三、单链表的基本操作（核心）

以下所有操作都假设：带头结点

1️⃣ 初始化链表

head = new Node
head.next = NULL

时间复杂度：O(1)

2️⃣ 头插法（Head Insert）

思想

新结点插入到 头结点之后

步骤

new.next = head.next
head.next = new

特点

• 速度快
• 元素顺序会 反转

时间复杂度：O(1)

3️⃣ 尾插法（Tail Insert）

思想

新结点插入到 链表尾部

步骤

tail.next = new
new.next = NULL

时间复杂度：

• 有尾指针：O(1)
• 无尾指针：O(n)

4️⃣ 遍历链表

思想

从第一个有效结点开始，直到 NULL

p = head.next
while p != NULL:
    visit(p.data)
    p = p.next

时间复杂度：O(n)

5️⃣ 按值查找

p = head.next
while p != NULL:
    if p.data == x:
        return p
    p = p.next

时间复杂度：O(n)

6️⃣ 按位置插入（重点）

在第 i 个位置插入（1-based）

思路

• 找到第 i-1 个结点 p
• 插入新结点

操作顺序（不能反！）

new.next = p.next
p.next = new

⚠️ 若反过来会断链

时间复杂度：O(n)

7️⃣ 按位置删除（重点）

删除第 i 个结点

思路

• 找到第 i-1 个结点 p
• 删除 p.next

q = p.next
p.next = q.next
free(q)

时间复杂度：O(n)

8️⃣ 删除指定值结点

p = head
while p.next != NULL:
    if p.next.data == x:
        p.next = p.next.next
        break
    p = p.next

四、常见进阶操作（高频）

1️⃣ 单链表反转（面试必考）

方法一：迭代法（最常用）

prev = NULL
curr = head.next

while curr != NULL:
    next = curr.next
    curr.next = prev
    prev = curr
    curr = next

head.next = prev

时间复杂度：O(n)
空间复杂度：O(1)

2️⃣ 查找倒数第 k 个结点

双指针法

fast = slow = head.next

fast 先走 k 步
然后 fast、slow 同时走

fast 到尾时
slow 即倒数第 k 个

时间复杂度：O(n)

3️⃣ 判断链表是否有环

快慢指针（Floyd）

slow 每次走 1 步
fast 每次走 2 步

如果相遇 → 有环

4️⃣ 合并两个有序单链表

p1, p2 指向两链表头
依次比较，小的接入新链表

时间复杂度：O(n + m)

五、常见错误总结（非常重要）

❌ 插入时指针顺序写反
❌ 删除结点后继续使用该指针
❌ 忘记处理空链表
❌ 遍历条件写成 p.next != NULL（会漏最后一个）

六、单链表操作时间复杂度总览

七、面试高频问题汇总

✅ 单链表反转
✅ 删除倒数第 N 个结点
✅ 合并有序链表
✅ 判断是否有环
✅ 找中间结点

最后一句话总结

单链表的核心只有一句：指针永远不要丢，顺序永远不要反。