单链表基础操作详解：从节点定义到逆序与合并

标题写的“单列表”，我猜大概率是“单链表”的笔误。单链表（singly linked list）是数据结构里最基础也最容易被轻视的一节课。它不只是考试题，后面的栈、队列、哈希表的链地址法、图的邻接表、LRU缓存，底层全是链表或者链表思想的变体。这篇文章就把单链表的创建和使用讲透：从节点的定义、头插法和尾插法，到查找、插入、删除这些基本操作，再把两个高频经典问题——链表逆序和两个升序链表合并——完整写一遍。如果你正在做“单链表的基本操作实验”，或者准备面试刷链表题，这篇可以直接照着敲代码，也能帮你避掉那些经常让人调一晚上的低级错误。

1. 为什么数组用得好好的，还要搞出一个链表来

1.1 数组的三处硬伤

数组是大多数人学会的第一种数据结构，它确实好用：连续内存、按下标直接访问，a[i]一步到位，时间复杂度 O(1)。但数组的缺点在我实际写程序时越来越明显，尤其在元素个数不确定、频繁增删的场景里。

第一处硬伤是长度固定。C 语言的数组声明之后长度就不能变，必须提前估算最大值。估算大了浪费内存，估算小了程序直接越界。Python 里的 list 虽然看着能随便 append，但底层是动态数组，扩容时要申请一块更大的内存，然后把旧数据全部搬过去，这个搬迁成本是 O(n) 的。如果你往一个动态数组里不断头插，每次都要把已有元素一个个往后挪，性能肉眼可见地拉胯。

第二处硬伤是插入和删除的代价太高。在数组中间插入一个元素，需要把插入位置后面的所有元素依次后移一位；删除则是前移。假设数组长度是 n，在头部插入就是 O(n)，在中间随机位置插入平均也是 O(n)。这在写课程设计、做数据处理时很致命。

第三处硬伤是内存的连续性要求。数组必须占用一整块连续的内存空间。内存被分来分去之后，剩余的空闲块可能都是零散的，任何一个单独的空闲块都装不下一个大数组。这时候系统要么触发内存整理，要么分配失败。

1.2 链表的本质：用离散存储换灵活操作

链表的思路很简单：既然连续的大块内存不好找，那我就不找连续的了。每个元素放在一个独立的“节点”里，节点之间用指针串起来，像一串珠子一样。每个节点只干两件事：存自己的数据，记下一个节点在哪儿。

所以单链表的核心定义就是：节点之间是线性逻辑关系，但物理存储是离散的。

这个设计带来几个直接好处：

• 内存分配灵活，每个节点可以单独分配，不需要一次性申请一整块。
• 插入删除只需要改指针，不需要搬动其他元素，O(1) 完成。
• 长度天然动态，想加就加，想删就删。

代价也很明确：不支持随机访问，想找第 k 个节点必须从头一个个往后走，时间复杂度 O(n)；每个节点多出一个指针域，内存占用比数组高；另外由于节点在内存里不连续，CPU 缓存命中率低，大数据量下遍历性能不如数组。

我见过不少同学一上来就纠结“哪个更好”。没有更好，只有合适。频繁查找、数量稳定用数组；频繁增删、数量动态用链表。这也是为什么实际项目里两种都会用。

1.3 指针也好，引用也罢，理解“节点”才是关键

学链表的时候，很多人被“指针”这个概念吓住了。C 语言里指针就是一个变量，存的是另一个变量的内存地址。Python 里没有指针这个说法，但有个东西叫“引用”，本质是一样的：对象在内存中有地址，变量绑定到这个地址上。

理解这一点特别重要。你在 Python 里写：

a = ListNode(1) b = a b.val = 2

改的是同一个对象，因为a和b指向同一个内存位置。链表的next字段，存的就是下一个节点的引用（或者指针）。操作链表，本质上就是不断问自己一个问题：当前这个节点的 next 应该指向谁？

在纸上画图是理解链表的最好方式。一个节点画成一个方块，左边写值，右边画一个箭头指向下一个方块。所有指针操作，跟着箭头走一遍就通了。

2. 从节点定义开始：创建链表的两种方法

2.1 节点结构怎么定义最顺手

无论用什么语言，单链表的节点都长一个样：一个数据域，一个指针域/引用域。

Python 版本用类定义：

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

C 语言版本用结构体：

typedef struct Node { int data; struct Node *next; } Node;

两个版本一一对应。val存数据，next存下一个节点的位置。最后一个节点的next指向None（Python）或者NULL（C），表示链表结束。

这里有个细节：节点定义里的next=None是默认参数。这样创建单个节点时可以不传 next，写node = ListNode(5)，它天然就是链表尾部。这个默认值看起来不起眼，实际写代码时能少写很多判断。

2.2 尾插法：顺序不变，最符合直觉的建链方式

创建链表最直接的想法是：新来的节点放到链表的最后面。这样创建出来的链表顺序和输入顺序完全一致。比如输入[1, 2, 3]，得到的链表就是1 -> 2 -> 3 -> None。

尾插法的实现需要维护一个尾指针，每次都在尾指针后面挂新节点，然后让尾指针移动到新节点上：

def create_by_tail(values): dummy = ListNode() # 哨兵节点，下面细说 tail = dummy # 尾指针 for v in values: tail.next = ListNode(v) # 新节点挂到尾部 tail = tail.next # 尾指针后移 return dummy.next # 哨兵的下一个才是真正的头节点

你注意这里的dummy节点。它本身不存有效数据，作用是让代码在链表为空时也能统一处理。没有 dummy 的话，往空链表里加第一个节点时要额外判断if head is None，代码会丑很多。后面合并两个链表时，这种哨兵节点更是神器。

2.3 头插法：代码最简洁，但链表是反的

头插法的思路反过来：每次把新节点插到链表的头部，让新节点成为新的头节点。

def create_by_head(values): head = None for v in values: new_node = ListNode(v) new_node.next = head head = new_node return head

代码非常短，但有一个容易忽略的副作用：输入顺序和链表顺序相反。输入[1, 2, 3]，得到的是3 -> 2 -> 1 -> None。

为什么会反？因为每次新节点都跑到最前面了，后输入的反而在链头。这个特性不是 bug，它可以被反过来利用：如果你有一批逆序数据想得到正序链表，或者实现“后进先出”的栈结构，头插法正好合适。很多教科书在讲“栈的链表实现”时用的就是头插法思路。

2.4 哨兵节点到底要不要？实战中的选择

上一节代码里出现了dummy，很多初学者会困惑：这不是白造了一个节点吗？

哨兵节点的价值在于消除边界条件的特殊处理。举个例子，删除一个节点，正常的逻辑是：找到前驱节点 prev，然后prev.next = prev.next.next。但如果要删的是头节点，它没有前驱，就要单独写一个分支。有了哨兵节点之后，头节点也变成了“某个节点的下一个”，所有删除操作统一成同一种写法。

我的个人建议是：刷题和写项目时都用哨兵节点，养成习惯。它让你少想很多 if 分支，代码也更不容易出 bug。唯一的代价就是多一个节点的内存，现代计算机完全不在乎这一点。

3. 基本操作实验：遍历、查找、插入、删除

3.1 遍历和求长度：所有操作的地基

遍历是最基础的操作，思路就是“从头开始，跟着 next 一直走，走到 None 为止”：

def traverse(head): cur = head while cur is not None: print(cur.val) cur = cur.next

求链表长度的代码几乎一样，只是把打印换成计数：

def length(head): count = 0 cur = head while cur is not None: count += 1 cur = cur.next return count

这里有一个新手很容易犯的错：有人在 while 里写了cur.next，然后循环里又移动cur。仔细看，如果你写的是while cur.next is not None，那循环结束时停在了最后一个节点上，最后一个节点的值就没处理到。统一用while cur is not None判断，逻辑最简单。

3.2 按值查找和按下标访问

按值查找就是遍历一遍，比较每个节点的 val：

def find_by_value(head, target): cur = head pos = 0 while cur is not None: if cur.val == target: return pos cur = cur.next pos += 1 return -1 # 没找到

按下标访问也一样，只是判断条件从“值相等”变成“走够了步数”：

def get_by_index(head, index): cur = head for _ in range(index): if cur is None: raise IndexError("下标越界") cur = cur.next if cur is None: raise IndexError("下标越界") return cur.val

注意越界判断。链表不支持随机访问，按下标访问是 O(n)，这是链表的固有特性。如果频繁按位置访问，说明你选错了数据结构。

3.3 插入操作：先连后继，再连前驱

在链表第 pos 个位置后面插入一个新节点，核心操作两步：

def insert_after(prev_node, new_node): """ 在 prev_node 后面插入 new_node """ new_node.next = prev_node.next prev_node.next = new_node

这两行的顺序不能反。我当年第一次写的时候就是反着来的：

# 错误示范 prev_node.next = new_node # 先把 prev 指向新节点 new_node.next = prev_node.next # 但 prev_node.next 已经变成 new_node 自己了

反了之后，新节点 next 指向了自己，形成自环，链表从那里断成两截，后面所有节点彻底丢失。正确的逻辑永远是：先把新节点的后继接到原后继上，再把前驱的 next 接到新节点上。注意这个顺序，插到头节点、插到中间、插到末尾都一样。

类比一下：你想在一列队伍里插队，一定是你先拉住后面那个人的手，再让前面那个人拉住你。如果前面那个人先松手拉住你，后面那个人就找不到了。

3.4 删除节点：找到前驱是关键

删除的本质是：让目标节点的前驱，直接跳过目标节点，指向目标节点的后继。

def delete_node(head, target_val): dummy = ListNode(0) dummy.next = head prev = dummy cur = head while cur is not None: if cur.val == target_val: prev.next = cur.next return dummy.next prev = cur cur = cur.next return dummy.next

几个要点：

• 借助 dummy 以后，删除头节点也只是普通情况，不需要单独写 if。
• 删除操作真正的难度不是“删”这一步，而是“找到前驱”。单链表只能往后走，你不能从当前节点回头找它的前驱，所以必须用一个 prev 指针跟在后面。
• C 语言里删除节点还要手动free(cur)，否则会内存泄漏；Python 有垃圾回收，不需要这一步，但你要明白在这个语言里节点是何时被回收的。

3.5 一个完整可运行的链表类，“基本操作实验”直接抄

把上面的操作组装成一个类，就是课程里常见的“单链表基本操作实验”：

class SinglyLinkedList: def __init__(self): self.head = None self.size = 0 def insert_head(self, val): """头插法插入""" node = ListNode(val) node.next = self.head self.head = node self.size += 1 def append(self, val): """尾插法插入""" node = ListNode(val) if self.head is None: self.head = node else: cur = self.head while cur.next is not None: cur = cur.next cur.next = node self.size += 1 def insert(self, index, val): """在下标 index 处插入""" if index < 0 or index > self.size: raise IndexError("下标越界") if index == 0: self.insert_head(val) return prev = self.head for _ in range(index - 1): prev = prev.next node = ListNode(val) node.next = prev.next prev.next = node self.size += 1 def delete(self, index): """删除下标 index 处的节点""" if index < 0 or index >= self.size: raise IndexError("下标越界") if index == 0: self.head = self.head.next else: prev = self.head for _ in range(index - 1): prev = prev.next prev.next = prev.next.next self.size -= 1 def find(self, val): """按值查找，返回下标""" cur = self.head pos = 0 while cur is not None: if cur.val == val: return pos cur = cur.next pos += 1 return -1 def display(self): cur = self.head values = [] while cur is not None: values.append(str(cur.val)) cur = cur.next print(" -> ".join(values) + " -> None")

这个类能覆盖绝大多数课程实验和面试基础题的测试需求。注意size字段的维护：插入时加一，删除时减一。很多人漏掉这一步，后面查找和插入的下标判断就会出 bug。调试链表的题，建议先把“遍历打印”写出来，每操作一步就打印一次链表，比盯代码快得多。

4. 单链表逆序：最容易丢指针的经典题

4.1 迭代反转：三个指针的接力

“python 单链表逆序”是热搜经常出现的题，面试里也几乎必考。它的要求是：不新建链表，只改指针方向，把链表整个反过来。

迭代法的核心思路是三个指针：prev记录当前节点的前驱，cur记录当前节点，nxt记录当前节点的后继。每到一个节点，先把后继存下来，再把当前节点的 next 指向 prev，然后三个指针整体前移：

def reverse_list(head): prev = None cur = head while cur is not None: nxt = cur.next # 先保存后继 cur.next = prev # 指针反转 prev = cur # prev 前移 cur = nxt # cur 前移 return prev # 新的头节点

很多初学者在循环里不知道第三步该干什么，硬生生把cur = cur.next写进去。问题在于cur.next已经在第二步被改成了prev，你再cur = cur.next就回到了原来的前驱，永远在原地打转。所以必须提前用nxt保存好原来的后继。

代码返回的是prev而不是cur，因为循环结束时cur已经变成None，prev停在原链表的尾节点上。尾节点反转后变成了头节点，它就是新链表的头。

建议画图走一遍：输入1 -> 2 -> 3 -> None，手动模拟指针变化。我在给学生讲这块时发现，只要能在纸上完整画出每一轮三个指针的位置，迭代反转就算真正学会了。

4.2 递归反转：函数栈帮你完成一半工作

递归法代码更短，但对初学者来说更难理解：

def reverse_recursive(head): if head is None or head.next is None: return head new_head = reverse_recursive(head.next) head.next.next = head head.next = None return new_head

理解递归反转有两个关键点。

第一，递归函数返回的是“反转后的新头节点”。假设链表是1 -> 2 -> 3 -> None，调用reverse_recursive(1)时，它先调用reverse_recursive(2)，后者又调用reverse_recursive(3)。最深层递归到节点 3 时，3.next是 None，直接返回 3，此时3就是整条链表反转后的头。

第二，回溯时只看两层。从节点 3 回到节点 2 那一层时，head是 2，head.next是 3。代码做的事是2.next.next = 2，也就是让 3 的 next 指向 2，形成3 -> 2，然后把2.next置为 None，防止出现循环。每一层都做同样的操作，最后整条链就反过来了。

4.3 逆序操作里最容易踩的三个坑

这个题几乎每个新手都会踩坑，我总结三个最常见的：

坑一：返回错了节点。迭代法最后返回prev，递归法返回new_head。有人写迭代时图省事返回cur，但此时cur是 None，等于返回了一个空链表，打印出来什么都没有。

坑二：递归深度过大。Python 默认递归深度限制在 1000 左右，链表长度超过这个数就会抛RecursionError。面试时用递归写法没问题，但如果你在真实项目里反转一个上万元素的链表，老老实实用迭代。

坑三：忘了把原来的头节点 next 置空。反转前头节点变成了尾节点，它的 next 必须指向 None。迭代法里因为prev初始是 None，反转后原头节点的 next 自然变成 None，没问题。但递归法必须手动写head.next = None，否则链表末尾会成环，遍历时直接死循环。

5. 已知两个长度为 m 和 n 的升序单链表：合并操作的完整拆解

5.1 合并升序链表的基本思路

这个热搜题给的背景是“已知两个长度为 m 和 n 的升序单链表”，任务通常是合并成一个升序链表。这是面试里链表题的常客，也是归并排序在链表上的基础操作。

核心思路一句话：两个链表同时从头往后走，谁的当前节点值小，谁就接到结果链表后面，然后那个链表的指针往后走一步，重复这个过程，直到某个链表走完，把另一个链表剩下的一整段接上。

前提条件是两个链表都已经是升序的。如果其中一个为空，合并结果就是另一个链表本身。

5.2 迭代实现：哨兵节点让代码变得优雅

def merge_two_sorted_lists(l1, l2): dummy = ListNode() cur = dummy while l1 is not None and l2 is not None: 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 is not None else l2 return dummy.next

这段代码里的哨兵节点dummy发挥了巨大作用。没有它，你要费心思判断“结果链表的第一个节点到底是谁”；有了它，所有新节点一律挂在cur.next上，最后dummy.next就是结果链表的头。

cur.next = l1 if l1 is not None else l2这一行很巧妙。因为两个链表都是升序的，剩下的部分也必然是升序的，而且剩下来的所有节点一定比已经接好的节点都大，可以直接整段拼接。不需要再一个个遍历。

5.3 递归实现：更短，但不是所有场景都适合

递归的思路更数学化：比较两个头节点的大小，小的那个作为结果头节点，它的 next 指向“剩余两个链表合并后的结果”。

def merge_two_sorted_lists_recursive(l1, l2): if l1 is None: return l2 if l2 is None: return l1 if l1.val < l2.val: l1.next = merge_two_sorted_lists_recursive(l1.next, l2) return l1 else: l2.next = merge_two_sorted_lists_recursive(l1, l2.next) return l2

递归方法和迭代方法的时间复杂度一样，都是 O(m+n)，因为每个节点都被比较了一次。但空间复杂度有区别：迭代法只用常数个指针，空间 O(1)；递归法每一次调用都会占用函数栈空间，最坏情况递归深度达到 m+n，空间 O(m+n)。所以大数据量或者面试要求 O(1) 空间时，用迭代。

5.4 合并后的变种问题

理解了基本合并，几个变种也就顺了：

• 合并 k 个升序链表：可以用“两两合并”的方式，也可以借助最小堆，每次从 k 个头节点中取最小值。时间复杂度是 O(N log k)，N 是节点总数。
• 两个升序链表求交集/并集：思路和合并几乎一样，只是拼接条件变成“值相等才接”“值小时移动指针”。
• 合并后去除重复节点：合并时如果发现cur.val和结果链表最后一个节点的 val 一样，就不接这个重复节点。

面试时如果遇到这些变种题，先在纸上写出基本合并模板，再改条件，比硬背答案靠谱得多。

6. 实操经验：那些经常让人调一晚上的问题

6.1 指针丢失：链表世界里最贵的“手滑”

指针丢失往往只有一个原因：在连接新指针之前，把旧指针提前覆盖了。就像你搬家具，先把旧柜子推倒再准备搬新柜子，结果旧柜子里的东西全散了。

最常见的两处：

插入时没保存后继。在中间插入节点，如果先执行prev.next = new_node，原来的prev.next指向的节点就找不到了，后面整段链表全部丢失。正确做法是先new_node.next = prev.next，再prev.next = new_node。

反转或换位时没保存后继。凡是“把某个节点的 next 指向别处”的操作，都要先想清楚：原来的 next 还有没有人保存？如果没人保存，先存到一个临时变量里。

判断“会不会丢指针”，我有个笨办法：每次写完一个操作，问自己一个连环问题——有没有节点在操作后同时被两个指针指向？有没有节点一个指针都不指向？如果一个节点一个指针都不指向了，要么它马上被垃圾回收（Python），要么它就从链表里永久消失了。

6.2 边界条件：空链表、单节点、头节点和尾节点

我在批改学生的实验报告时，发现很多 bug 根本不是逻辑错，而是边界条件没处理。链表题必须养成的肌肉记忆是，每次写完代码立刻检查四类情况：

• 链表为空：head是 None，遍历循环一次都不执行。
• 链表中只有一个节点：循环条件cur.next和cur的区别会在这里暴露。
• 操作头节点：插入、删除、反转都需要单独看头节点逻辑是否成立。
• 操作尾节点：cur.next is None的处理，比如在删除时要把前驱的 next 置为 None，而不能是野指针。

一个偷懒的通用解法：给链表加哨兵节点。有了dummy，空表和头节点特判基本都能消除。我刷题时几乎每个关于删除、插入、合并的题都会先定义一个dummy = ListNode(0)，省下大量脑力。

6.3 Python 和 C 在链表操作上的差异

很多教材用 C 语言讲链表，你照着写成 Python 时会有几个明显差异，照着下面这个表对照检查就行：

Python 没有指针运算，所以“链表的 next 指向谁”就体现在引用赋值上。另外 Python 里一切变量都是对象引用，写new_node = old_node之后改任意一个的 next，另一个也会跟着变，除非你显式创建一个新节点。这个特性在 C 里不容易搞混，Python 里容易踩。

6.4 调试链表的几种实用手段

链表出 bug 时，不要用眼睛硬抠代码。我通常按这个顺序来：

先打印。在每次循环末尾打印当前链表所有节点的值，看哪一步开始不对。这个方法最土但最有效。为了打印方便，提前写好display函数，平时无所谓，调试时它就是你的命根子。

再画图。在纸上把几个关键节点画成方块，上面写数据，下面写 next 指向，手动模拟代码一行行执行。特别是反转、插入、删除这类改指针的操作，画一遍基本就能定位问题。

最后写测试用例。不要只测正常链表，把空链表、单节点链表、两个节点链表、目标在头节点、目标在尾节点这五类情况都测一遍。很多边界 bug 都是这样测出来的。

链表的问题几乎都是“画一画就通了”的问题。很多人觉得链表难，其实是卡在“不动笔只动脑”。你如果真的拿纸笔把指针的变化从头到尾画上几遍，后面再遇到环形链表、双向链表、跳表，上手都会比身边人快一大截。