标题写的“单列表”我猜大概率是“单链表”的笔误。单链表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 缓存命中率低大数据量下遍历性能不如数组。对比项数组单链表随机访问O(1)O(n)头部插入O(n)O(1)头部删除O(n)O(1)内存连续性要求连续不要求额外内存开销基本没有每个节点一个指针域我见过不少同学一上来就纠结“哪个更好”。没有更好只有合适。频繁查找、数量稳定用数组频繁增删、数量动态用链表。这也是为什么实际项目里两种都会用。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, val0, nextNone): self.val val self.next nextC 语言版本用结构体typedef struct Node { int data; struct Node *next; } Node;两个版本一一对应。val存数据next存下一个节点的位置。最后一个节点的next指向NonePython或者NULLC表示链表结束。这里有个细节节点定义里的nextNone是默认参数。这样创建单个节点时可以不传 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 按值查找和按下标访问按值查找就是遍历一遍比较每个节点的 valdef 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已经变成Noneprev停在原链表的尾节点上。尾节点反转后变成了头节点它就是新链表的头。建议画图走一遍输入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是 2head.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(mn)因为每个节点都被比较了一次。但空间复杂度有区别迭代法只用常数个指针空间 O(1)递归法每一次调用都会占用函数栈空间最坏情况递归深度达到 mn空间 O(mn)。所以大数据量或者面试要求 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 时会有几个明显差异照着下面这个表对照检查就行操作C 语言Python节点定义struct typedefclass指向下一个指针变量对象引用空链表判断head NULLhead is None删除节点手动 free(node)自动垃圾回收访问字段node-nextnode.next指针运算支持不支持Python 没有指针运算所以“链表的 next 指向谁”就体现在引用赋值上。另外 Python 里一切变量都是对象引用写new_node old_node之后改任意一个的 next另一个也会跟着变除非你显式创建一个新节点。这个特性在 C 里不容易搞混Python 里容易踩。6.4 调试链表的几种实用手段链表出 bug 时不要用眼睛硬抠代码。我通常按这个顺序来先打印。在每次循环末尾打印当前链表所有节点的值看哪一步开始不对。这个方法最土但最有效。为了打印方便提前写好display函数平时无所谓调试时它就是你的命根子。再画图。在纸上把几个关键节点画成方块上面写数据下面写 next 指向手动模拟代码一行行执行。特别是反转、插入、删除这类改指针的操作画一遍基本就能定位问题。最后写测试用例。不要只测正常链表把空链表、单节点链表、两个节点链表、目标在头节点、目标在尾节点这五类情况都测一遍。很多边界 bug 都是这样测出来的。链表的问题几乎都是“画一画就通了”的问题。很多人觉得链表难其实是卡在“不动笔只动脑”。你如果真的拿纸笔把指针的变化从头到尾画上几遍后面再遇到环形链表、双向链表、跳表上手都会比身边人快一大截。