链表基础详解：从数组短板到C++/Python实现与高频考点

你是不是也困惑过：学了数组之后，为什么还要搞出一个链表来？数据结构课上老师讲“链表”的时候，很多人的第一反应是——数组用得好好的，下标随便访问，遍历一个for循环搞定，链表到底解决什么问题？

我直接说结论：数组的“连续内存”既是它的优势，也是它的天花板。一旦涉及频繁的插入和删除操作，数组的代价大得离谱——你想想，在数组头部插一个元素，后面所有元素都得往后退一位。而链表用“不连续的内存 + 指针串起来”的方式，把插入删除的代价降到了O(1)。这就是链表最核心的价值。

这篇内容把链表基础完整捋一遍，包含底层原理、三种链表形态的选型思路、C++和Python两套实操代码、反转链表和有序链表合并这些高频考点，以及我自己踩过的坑和排查经验。不管你是刚接触数据结构的新手，还是准备面试想复习链表核心操作的选手，这篇都适合按顺序读完。

1. 链表的本质：为什么我们要把“每个数据”额外放一个“指针”

1.1 从数组的短板说起

数组是连续内存，这意味着它有两个先天的限制。第一，你创建数组的时候，大小基本确定了。你开了个int a[100]，数据超过100就崩了，你说我用动态数组，那底层扩容也是“复制到新内存”，这个操作本身是O(n)。第二，在任意位置插入或删除元素，需要把后面的元素整体搬移。数据量一上来，这个成本非常肉疼。

链表就是在这两个场景里换了个思路登场。它不要求内存连续，每个节点存储“数据”和“下一个节点的地址”。地址，也就是C/C++里的指针、Python里的引用，把一个个节点串成一条链。插入和删除只需要改前后节点的指针，不需要搬动任何“物理位置”上的数据。

1.2 节点与指针的关系

简单说，链表的基本单元叫“节点”（Node）。一个节点至少包含两个部分：

• 数据域：存储实际的数据，可以是int、字符串、甚至一个结构体对象。
• 指针域：存储下一个节点的地址（C/ C++叫next指针，Python里就是一个引用变量）。

当你拥有第一个节点的地址时，你就可以顺着next指针走到第二个节点、第三个节点……一直走到某个节点的next为nullptr（NULL / None），那就说明链表到尾部了。这个“顺着地址走”的过程，就是链表的遍历。

提示：C语言里我们常说“指针”，C++里讲“指针”或“智能指针”，Python里其实叫“引用”。归根结底就是“存着另一个对象在哪里”的东西，你要记住这个抽象概念，后面的理解会顺很多。

1.3 三种基本形态：单链表、双链表、循环链表

链表不是只有一种形态，面试和实际项目里常见的有三种：

形态	结构特点	优点	缺点	典型场景
单链表	每个节点有next，只能从前往后走	结构简单，内存省	无法回退，删除当前节点需要知道前驱	入门学习、栈和队列的底层
双链表	节点有prev和next，可双向遍历	双向操作方便，删除容易	多一个指针，内存占用翻倍	LRU缓存、浏览器前进后退
循环链表	尾节点next指向头节点	可以从任意节点出发遍历整个链表	处理不好容易死循环	约瑟夫环、任务轮询调度

从“链表基础”这个角度说，我建议先把单链表彻底吃透。单链表的思路一旦通了，双链表就是多维护一个prev指针，循环链表就是把尾部边界处理改成回到头部。核心逻辑完全一样，凭空多出来的只是细节。

2. 核心操作拆解：遍历、插入、删除、反转，每个动作背后的细节

2.1 遍历：最基础也最容易出小错的动作

链表遍历的代码模板几乎是固定的：

Node* cur = head; while (cur != nullptr) { // 处理cur->data cur = cur->next; }

核心逻辑就是两个：第一步用while判断当前节点是否存在，第二步处理完一个节点后把cur指向下一个节点。顺序绝对不能反。必须先把当前节点的next拿到，再移动指针。很多新手喜欢写成cur->next = cur，或者直接把next覆盖掉了，链表就断了。

对于双链表，遍历多了一个方向。对于循环链表，你需要一个额外的计数器或者记录起点，否则会无限循环。

2.2 插入操作：头插、尾插、中间插，三种方式各有什么讲究

先说头插。新节点的next指向原来的头节点，然后更新head指向新节点。这个操作是O(1)，也是最简单的一种，但会让链表的顺序和输入顺序相反。如果你想用链表做栈，这种插入方式正好合适。

再说尾插。你得先找到链表的最后一个节点，让它的next指向新节点。问题是，如果链表的头是head，尾部没有额外记录一个tail指针，每次尾插都要从头遍历一次，时间复杂度是O(n)。所以在频繁尾插的场景里，我建议在结构体里多存一个tail指针，让尾插降到O(1)。

最后说中间插入。这个操作的核心是：指定一个位置（通常是某个节点p），在p的后面插入新节点。第一步，新节点的next指向p->next；第二步，p->next指向新节点。顺序依然是铁律，必须先连新节点，再改原节点的next。如果你先改了p->next，那么p原来后面的那一整段链表就找不回来了，直接丢失。

2.3 删除操作：单链表删除的核心难点是找前驱

单链表删除一个节点，表面上是把“前一个节点的next”指到“被删除节点的next”上。但问题在于，单链表只能往前走，你拿着被删除节点的地址，是拿不到它的前驱的。这就意味着，你删除的时候必须从头遍历，或者在一个循环里同时维护prev和cur两个指针。

如果直接给一个节点指针让你删除它后面的那个节点，这种“后继删除”倒是简单：

Node* tmp = p->next; p->next = tmp->next; delete tmp;

这个技巧在面试题里叫“O(1)删除节点”，前提是待删节点不是尾节点。如果是尾节点，你还得老老实实找到它的前驱。双链表就没这个困扰，因为每个节点都有prev直接指向前驱，删除一个已知节点是真正的O(1)。

2.4 反转链表：高频考点的核心是“三指针”

反转链表为什么高频？因为它同时考了“指针修改”的理解、循环边界条件的控制，还考了你是否真正理解了单链表的结构。

思路很简单：你要把每个节点的next改为指向自己的前一个节点，但你不能直接改，因为你一改，后面的节点就丢了。所以必须有一个指针提前保存“后一个节点”。于是经典的“三指针”方案出现了：

• pre：当前节点的前一个节点。
• cur：当前要处理next指向的节点。
• next：提前记录cur原本的下一个节点。

每一轮循环做三件事：第一，用next暂存cur->next；第二，把cur->next指向pre；第三，pre和cur整体前移一位。循环结束后，pre就是新的头节点。

注意：C语言版本的这句“pre和cur整体前移”，顺序必须是先pre=cur，再cur=next。反过来就出大问题。我已经见过太多人在这两个赋值语句的顺序上栽跟头了。

3. 动手实践：C++ 结构体链表从语法到完整实现

3.1 C++ 结构体链表的基本语法

在C语言里，链表节点一般用struct定义。到了C++，struct被允许包含构造函数，这让初始化变得方便很多。我看很多教材还在用C语言风格手写一个init函数，其实C++里直接写构造函数更省事：

struct ListNode { int val; // 数据域 ListNode* next; // 指针域 ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode* next) : val(x), next(next) {} };

这里有三个构造函数，是LeetCode里默认的节点风格。第一个是无参构造，第二个是给定值构造，第三个是给定值也给next，方便快速创建节点。写完这三个构造函数之后，创建节点就变成一行：

ListNode* head = new ListNode(1); ListNode* second = new ListNode(2); head->next = second;

这就是C++结构体链表最基本的语法。你可能问为什么节点里有两个名称相同但参数列表不同的函数，这叫构造函数重载，是C++类的特性，现在不理解也不影响，先会用它写链表就好。

3.2 单链表的完整操作实现

我直接给一套可直接运行的核心代码，包含创建、遍历、插入、删除、反转：

#include <iostream> struct ListNode { int val; ListNode* next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode* next) : val(x), next(next) {} }; // 遍历打印 void printList(ListNode* head) { ListNode* cur = head; while (cur != nullptr) { std::cout << cur->val; if (cur->next != nullptr) std::cout << " -> "; cur = cur->next; } std::cout << std::endl; } // 头插 ListNode* insertAtHead(ListNode* head, int val) { ListNode* newNode = new ListNode(val); newNode->next = head; return newNode; // 新的头返回出去 } // 尾插 ListNode* insertAtTail(ListNode* head, int val) { ListNode* newNode = new ListNode(val); if (head == nullptr) return newNode; ListNode* cur = head; while (cur->next != nullptr) { cur = cur->next; } cur->next = newNode; return head; } // 指定节点p之后插入 void insertAfter(ListNode* p, int val) { if (p == nullptr) return; ListNode* newNode = new ListNode(val); newNode->next = p->next; p->next = newNode; } // 删除指定值的第一个节点（考虑头节点） ListNode* deleteNode(ListNode* head, int val) { if (head == nullptr) return nullptr; if (head->val == val) { ListNode* tmp = head; head = head->next; delete tmp; return head; } ListNode* cur = head; while (cur->next != nullptr && cur->next->val != val) { cur = cur->next; } if (cur->next != nullptr) { ListNode* tmp = cur->next; cur->next = tmp->next; delete tmp; } return head; } // 反转链表 ListNode* reverseList(ListNode* head) { ListNode* pre = nullptr; ListNode* cur = head; while (cur != nullptr) { ListNode* next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; } int main() { ListNode* head = nullptr; head = insertAtHead(head, 3); head = insertAtHead(head, 2); head = insertAtHead(head, 1); printList(head); // 1 -> 2 -> 3 head = insertAtTail(head, 4); printList(head); // 1 -> 2 -> 3 -> 4 head = reverseList(head); printList(head); // 4 -> 3 -> 2 -> 1 head = deleteNode(head, 3); printList(head); // 4 -> 2 -> 1 return 0; }

注意几个细节。

头插和删除操作里，我都会返回新的头节点，为什么？因为头插之后head变了，删除头节点之后head也变了。如果你不接收返回值，调用方手里的head就还是旧地址，后果就是访问到错误内存甚至崩溃。经验丰富的人都会习惯性地把“会改变头节点地址”的函数设计成返回ListNode*，这也是C++链表里最常见的实践。

遍历打印里为什么要判断cur->next不是nullptr才输出箭头？为了让结尾不出现多余的“->”，这个细节挺小，但面试手写代码时，打印结果干净会让面试官印象好很多。

deleteNode函数的核心是先找到目标节点的前驱，所以while条件是cur->next存在且cur->next->val不等于目标值。很多人写的循环条件搞反了，最后cur空了还去访问cur->next，直接segment fault。

3.3 C++ 模板类链表：为什么要用模板

结构体链表有个限制：ListNode的val如果是int，你就只能装int；想装double，就得复制代码再写一个struct。模板类就是来解决这个问题的。

用模板类定义一个通用的链表，C++里常见的写法是这样：

template <typename T> struct Node { T data; Node<T>* next; Node(const T& value) : data(value), next(nullptr) {} }; template <typename T> class LinkedList { private: Node<T>* head; int size; public: LinkedList() : head(nullptr), size(0) {} ~LinkedList() { Node<T>* cur = head; while (cur != nullptr) { Node<T>* next = cur->next; delete cur; cur = next; } } void insertAtHead(const T& value) { Node<T>* newNode = new Node<T>(value); newNode->next = head; head = newNode; size++; } void print() const { Node<T>* cur = head; while (cur != nullptr) { std::cout << cur->data << " "; cur = cur->next; } std::cout << std::endl; } };

为什么要写析构函数？因为new出来的节点必须delete，否则每创建一次链表就泄漏一批内存。链表的析构要从头到尾把所有节点都释放，这一步非常容易被忽略。你别看代码量不大，但析构逻辑写错（比如漏了先保存next再delete），照样会访问野指针。

模板的好处是链表的类型变成“可复用组件”。你定义LinkedList 是整数链表，LinkedList 是字符串链表，同一个实现，任意类型都能用。这就是搜索词里“c++模板类链表”的核心价值所在。

4. 换种语言看链表：Python 的实现思维完全不一样

4.1 Python 链表实现的语法差异

Python没有指针这个说法，没有直接访问内存地址的概念，它用“引用”实现链表的串联。本质上是把一个对象赋给另一个对象的属性，让它们“互相引用”从而串成链。

最基本的Python链表节点长这样：

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

这段代码里next默认是None，正好对应C++里的nullptr。在Python里创建一个单链表：

head = ListNode(1) head.next = ListNode(2) head.next.next = ListNode(3)

看起来比C++清爽得多，但是底层还是要理解“head只是一个引用，它指向第一个节点对象；head.next又是另一个引用，指向第二个节点对象”。这一层概念想清楚，Python链表其实就通了。

4.2 Python 单链表逆序实现

Python的反转链表，逻辑和C++一模一样，也是三指针：

def reverse_list(head): pre = None cur = head while cur: nxt = cur.next cur.next = pre pre = cur cur = nxt return pre

Python这里有一个好处：不需要像C++那样手动delete，GC会自动回收没有引用指向的对象。但坏处也有——如果链表很长，递归式反转或递归式遍历容易超出Python的递归深度，这时必须用循环版本。所以面试手写的时候，我建议你优先用循环版本。

4.3 有序链表合并：一个高频但不算难的问题

两个“长度分别为m和n的升序单链表”合并成一个升序链表，这段也是热词里的。思路不复杂：双指针分别指向两个链表的头，每次比较两个指针指向的val，小的取下来接到结果链表尾部，然后指针往后移。如果某一个链表先走完，直接把另一条剩下的接到末尾。

Python版本很清晰：

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

这里有个典型的技巧：dummy节点，也叫“哑节点”或“哨兵节点”。因为合并后的链表头是不确定的（可能来自l1也可能来自l2），与其每次判断头节点是谁，不如先创建一个dummy，让cur从dummy开始，所有节点统一用cur.next接到后面。最后直接返回dummy.next就行。

这个技巧在链表的很多场景都适用，比如删除链表中的某个节点、按位置插入、合并多个链表。我强烈建议你把dummy节点当作链表操作的基本工具之一记住，能少写一半的边界判断代码。

5. 常见问题与排查技巧实录

5.1 新手最容易犯的错误，我在教学里反复看到

典型错误	场景	后果	正确做法
遍历时先改了cur->next再移动cur	反转链表、插入节点	后半段链表丢失，程序运行结果不对	先用临时变量保存原来next
删除节点后没有delete	C/C++里忘记释放内存	内存泄漏	delete tmp后再返回
访问空指针的next	遍历到尾部还继续执行cur=cur->next	段错误(segment fault)	while判断条件写清楚
头插/头删后没有更新外部头指针	调用方手里的head还是旧地址	整个链表访问异常	函数返回新head并接收
在循环链表里没有记录起始位置	遍历循环链表	死循环	记录起点或加计数器
Python里把pre设成0而不是None	反转链表	类型错误或结果错误	pre初始化为None
C++模板类忘记写析构函数	动态创建节点	内存泄漏	主动遍历释放所有节点

5.2 排查思路：链表程序出错的快速定位法

链表问题的bug，归纳起来无非三类：一是指针没有正确移动，二是边界条件没处理好，三是内存管理出了问题。

我个人的排查步骤是这样的：先用printList输出当前链表状态，在每个操作前后都打印一遍，看哪一步输出和预期不符，问题就缩小到那一步。

如果第一轮打印没用，就把代码里的核心循环加临时计数，限制最多循环1000次，防止死循环卡死程序。如果你用的是调试器，可以在循环里下断点，观察pre、cur、next在每一轮的变化，尤其是反转链表这种改指针密集的算法。

还有一个很容易被忽略的点：C++里delete之后一定要把指针置为nullptr，否则这个指针就成了“悬空指针”。虽然delete之后不去访问它似乎没影响，但如果在复杂代码里不小心用它，排查问题的时间是几何级数增长的。

5.3 双链表和循环链表的避坑提示

双链表比单链表多的操作是处理prev指针。插入一个节点时，要同时修改四个指针：新节点的next和prev，前驱的next，后继的prev。少改一个都是灾难。删除节点时，要同时让前驱的next越过该节点、后继的prev越过该节点。逻辑不难，难在容易漏。

循环链表的尾部判断不再是cur==nullptr，而是cur==head。如果你按单链表的习惯去遍历，就会无限循环。如果你要做“从链表中间开始遍历”，正确的做法是先记录起始节点，然后每次移动后都判断是否回到了起点。

双链表和循环链表之所以在面试里出现频率不低，就是因为它比单链表多出来的是“细节处理能力”，而不是更难的算法。先掌握单链表，再去写这两个变体，你会发现底层逻辑完全复用得上。

6. 实操总结：链表基础学习路径的建议

链表这部分内容，我自己当初学的时候走了很多弯路，现在给后来的读者一个清晰的路径建议。

第一步，用C++或C把单链表从头到尾写一遍，包含创建、遍历、插入、删除、反转。不要看代码抄，而是自己回忆逻辑写。写完把指针打印出来验证结果。这一步的意义是建立“指针操作”的肌肉记忆。

第二步，用Python再写一遍同样的操作。这一步的意义是理解“语言不同，底层抽象不同，操作思路是相通的”。Python的引用和C++的指针是不同世界的东西，但链表的串联思想是一样的。

第三步，做几个经典题目巩固：反转链表、合并两个有序链表、找链表中间节点、判断链表是否有环。这四类题目基本覆盖了链表操作的大多数考点。

第四步，如果时间充裕，手动实现一下双链表和循环链表，感受一下多指针维护和边界条件的变化。

还有一个建议：学习过程中把每个操作的时间复杂度写在旁边，头插O(1)，尾插带tail就是O(1)、不带就是O(n)，中间插入O(1)到O(n)不等，按值查找肯定是O(n)。这能帮助你在后续学习更复杂的算法时形成“复杂度直觉”。

链表这块内容看起来多，但本质就一句话：用指针（或引用）把分散的内存串成逻辑上有序的结构，所有操作的难点都在“修改顺序”和“边界条件”上。把今天这篇里列出的代码都亲手敲一遍，再对照着排查自己犯的错，链表基础就基本稳了。