一篇带你干翻单链表（C++版）

斌斌不爱敲代码

1687人浏览 · 2025-10-29 22:26:52

斌斌不爱敲代码 · 2025-10-29 22:26:52 发布

这篇文章会从链表的基础构造开始，总结一些基础题型，并总结了常见错误。

首先从链表基础开始，我们先来学习构建链表。

链表的构建分为以下几个部分：

创建链表节点

创建链表

对链表的操作又分为：

增：插入链表节点

删：删除链表节点

改：更改链表节点的值

查：根据下标查询，根据链表的值查询。

首先我们来了解一下什么是链表

链表的基本概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域存储实际数据，指针域存储指向下一个节点的地址。与数组不同，链表在内存中是非连续存储的，通过指针连接各个节点。

链表的特点

动态大小：链表的大小可以动态调整，无需预先分配内存。
插入/删除高效：在已知位置插入或删除节点的时间复杂度为O(1)，无需移动其他元素。
内存利用灵活：节点分散存储，但需要额外空间存储指针。
随机访问低效：访问特定节点需要从头遍历，时间复杂度为O(n)。

其中val是数据域，指针域指向下一个节点。

定义数据类型

首先用define定义链表数据类型，这样在修改数据类型时方便进行全局修改。

#define eleType int    //这里千万不要加分号！！！

链表节点的定义

既然每个链表节点的结构都相同，那么我们不难想象到用结构体去定义链表节点。节点的核心作用就是单纯地存储数据和指针，而没有复杂的逻辑关系。所以用结构体更适合轻量存储需求。

-----------------------

单个节点本身不需要插入删除等操作，仅仅是存储。结构体的设计初衷就是聚合数据，更符合节点的需求，因此用结构体来定义单个节点。

-----------------------

其中每个节点都包含数据域和指针域。

struct ListNode{
eleType data; //定义链表节点数据域
ListNode* next;//定义节点指针域

ListNode(eleType x):data(x),next(NULL) {};//调用结构体自身为节点赋值
}

仅仅是定义出来肯定不够，我们得在后面初始化这个节点。所以我们加入了一个结构体的构造函数，这样在创建结构体对象时就一定会调用该构造函数来完成节点初始化。在 C++ 中，只有名称与结构体名完全相同的成员函数，才能被称为结构体的构造函数。

构造链表

单有一个节点肯定不够，我们还需要将节点连接成一条链表。

链表的操作就比较复杂了。我们需要用链表来对数据进行管理，提供增删改查操作，同时一些重要的数据标志不希望被随意更改。类的特性更符合这种“数据管理+提供逻辑+隐藏关键信息”的需求。

因此我们选择用类来对链表进行封装。

class LinkedList
{
private:
    ListNode* head;
    int size;
public:
    LinkedList():head(NULL),size(0) {};
    ~LinkedList();
    void Insert(int index,eleType value);
    void Delete(int index);
    ListNode *find(int index);
    ListNode *search(eleType value);
    void Update(int index,eleType value);
}

LinkedList():head(NULL),size(0) {};代码解释：

因为head是ListNode类型，所以这里面调用head就是调用ListNode的默认构造函数，也就是我们定义结构体的时候，它的构造函数ListNode(eleType x):data(x),next(NULL) {};

注意：这里的ListNode(eleType x):data(x),next(NULL) {};是有参数的，所以我们在写LinkedList():head(NULL),size(0) {};时，head里面的NULL和size里面的0不可省略!

我们在后期也不需要专门去调用这个函数，因为它是类的构造函数。在 C++ 中，只有名称与类名完全相同的成员函数，才能被称为类的构造函数。它在我们调用这个类时会被自动调用执行。

~LinkedList();析构函数，当节点被Delete，或者离开了类的作用对象，或程序结束时自动销毁内存。

后面的其他函数我们下面会一一讲解。

我们先从最简单的开始，查找节点。

find查找第n个节点

我们现在只有头节点head，各个节点之间通过指针连接，因此我们想要找到某个位置的节点，必须要“从头开始”。

这里需要说明一下，头指针的原始状态时非常重要的，标志着链表开始的位置，所以我们除了改变头节点之外，我们一般不动头节点指针，让head永远是链表的头节点。但我们又需要来遍历这个链表，我们只能创建一个新的指针来从头节点开始遍历。

ListNode* cur = head;

创建一个新的结构体指针cur，并让其指向头节点，从头结点开始遍历。

for(int i=0;i<index;i++)
{
    cur=cur->next;
}

让cur不断等于下一位，i<index,就可以让cur正确遍历到下标为index的位置。

最后我们再返回该位置即可.

return cur;

find最终代码：

ListNode* LinkedList::find(int index)
{
	if (index<0 || index>size-1)   //异常处理
	{
		throw std::out_of_range("Invalid position");
	}
	ListNode* cur = head;
	for (int i = 0; i < index; i++)
	{
		cur = cur->next;
	}
	return cur;
}

search查找节点值为value的节点所在位置。

这个就不用解释了，遍历整个链表去寻找，如果没找到返回NULL即可

Search部分最终代码

ListNode *LinkedList::Search(int value)
{
	ListNode* cur = head;
	while (cur)
	{
		if (cur->val == value) return cur;
		cur = cur->next;
	}
	return NULL;
}

Insert插入节点

插入节点分为从头插入和从其他位置插入两部分。（一会

儿我们会探究为什么不单独分出来一个尾插）

我们先讲从中间插入步骤。

中间节点插入

现在我们想在下标为2（index==2）的位置插入val为4的节点。我们需要先让新节点指向2所在的节点。

然后我们再让val为1所在的节点指向新节点。

如此我们就完成了节点4的插入。

如果转换成代码呢？

我们先创建一个节点值为4的新节点。

ListNode *newNode = new ListNode(4);//这里会调用结构体构造函数来创建并初始化节点

然后我们需要让新节点接到原下标为2(index==2)的位置，并且还需要将4接到原下标为1(index-1)的位置的节点,因此我们肯定是要遍历到1(index-1)的位置而不是2(index==2)，如果我们遍历到index==2就没有办法对index==1进行操作了。

所以我们先遍历到index-1的位置

for(int i=0;i<index-1;i++)
{
    cur=cur->next;
}

然后将新节点接入到cur的下一个位置上。

（如果频繁的next很容会很混乱，所以我们定义一个新节点放到cur->next上）

ListNode* tmp=cur->next;
newNode->next=tmp;//tmp接到cur的下一个节点上

再将新节点接到cur上。

cur->next = newNode;

这样就完成了中间节点的插入。

中间节点插入总代码:最后不要忘了size+1

for (int i = 0; i < index - 1; i++)
{
	cur = cur->next;
}
ListNode* tmp = cur->next;
cur->next = newNode;
newNode->next = tmp;
size++;

如果是头节点插入呢？

头节点插入

头节点的插入其实很简单，我们只需要让新节点指向原头节点，并把head更新为新节点的位置即可。（不要忘记size+1）

newNode->next = head;
head = newNode;
size++;

Insert最终代码

void LinkedList::insert(int index, eleType value)
{
	if (index<0 || index>size)                        //异常处理
	{
		throw std::out_of_range("Invalid position");
	}
	ListNode* newNode = new ListNode(value);
	ListNode* cur = head;
	if (index == 0)
	{
		newNode->next = head;
		head = newNode;
		size++;
	}
	else
	{
		for (int i = 0; i < index - 1; i++)
		{
			cur = cur->next;
		}
		ListNode* tmp = cur->next;
		cur->next = newNode;
		newNode->next = tmp;
		size++;
	}
}

现在我们来探讨一下为什么不需要单独进行尾插：

假如我们要在最后一个节点位置（index=size）插入，也就是在index=5的位置插入。我们可以参照上图把index=5代入到插入中间节点的操作中，发现一样可以完成尾插。因此不需要单独进行尾插。

Delete删除节点

删除节点依然是分为删除头节点和中间节点两部分

我们想要删除下标为2(index==2)的节点，要怎么操作呢？

删除的逻辑其实也很简单

我们让1(index-1)直接指向5，然后删除2即可。

也就是说我们需要先遍历到下标为1的位置，然后让下标为1的位置指向原链表下标为3的位置。我们这里跳过了下标为2的位置，我们依然用tmp做过渡。

ListNode* cur=head;
for(int i=0;i<index-1;i++)
{
    cur=cur->next;
}
ListNode*tmp = cur->next;
cur->next=tmp->next;
delete tmp;
size--;

如果是删除头节点那也会更简单。我们直接用tmp临时存储原来的head，让第二个节点作为head，然后删除掉tmp即可。

ListNode* tmp=head;
head=tmp->next;
delete tmp;
size--;

Delete最终代码：

void LinkedList::Delete(int index)
{
	if (index<0 || index>size - 1)
	{
		throw std::out_of_range("Invalid position");
	}
	ListNode* cur = head;
	if (index == 0)
	{
		ListNode* tmp = head;
		cur = cur->next;
		head = cur;
		delete tmp;
		size--;
	}
	else
	{
		for (int i = 0; i < index - 1; i++)
		{
			cur = cur->next;
		}
		ListNode* tmp = cur->next;
		cur->next = tmp->next;
		delete tmp;
		size--;
	}

}

Update更新节点值

最后更新部分代码就不用多说了，这个很简单的。直接找到对应节点然后赋值即可。

Update最终代码

void LinkedList::Update(int index, eleType value)
{
	if (index<0 || index>size - 1)
	{
		throw std::out_of_range("Invalid position");
	}
	ListNode* cur = head;
	for (int i = 0; i < index; i++)
	{
		cur = cur->next;
	}
	cur->data = value;
}

题型总结

1.遍历单链表

题型一：返回倒数第k个节点

参考题目：LCR 140. 训练计划 II - 力扣（LeetCode）

思路：这一题我们就直接遍历整个链表，遍历两次，第一次算出size，第二次直接遍历到size-k的位置得出答案即可。

题型二：返回链表中间节点

参考题目：876. 链表的中间结点 - 力扣（LeetCode）

思路：同样遍历两遍，第一遍算出size，第二遍遍历到size/2即可。

2.删除链表节点

题型一：删除中间节点

参考题目：面试题 02.03. 删除中间节点 - 力扣（LeetCode）

思路：本题的难点在于没有给出头节点，而是给出了需要删除的节点，我们可以直接把下一个节点的值赋值给当前节点，然后删掉下一个节点即可。最后得到的结果是一样的。

而且本题的中间不是正中间的意思，而是非头节点非尾节点，我们可以直接让cur->next=cur->next->next;不用考虑会不会出现空节点访问的问题。而且力扣给出的测试样例中不需要考虑内存，也就是说，至于中间那个节点，不用管了。但我们在实际开发中一定要考虑内存释放！

题型二：删除重复节点

参考题目：83. 删除排序链表中的重复元素 - 力扣（LeetCode）

思路：本题给出的是已经排序好的链表，会更简单一些。当遇到下一个节点的值等于当前节点时，直接跳过下一个节点即可。这里有一个难点需要考虑，比如说删除8-5-4-4-1这个链表，当遍历到第一个4时，我们的cur是应该跳到最后一个1还是留在当前的4？再看看8-5-4-4-4-1这个链表，如果跳过中间的那个4，直接跳到倒数第二位置上的那个4了，那最后还是会留下两个4；

3.单链表插入

题型一：构建新链表

参考题目：面试题 02.01. 移除重复节点 - 力扣（LeetCode）

思路：本题中给出的节点是未排序的，未排序的节点进行删除就很麻烦了。所以我们直接创建一个不含重复元素的新节点即可。

4.反转链表

题型一：反转链表

参考题目：LCR 024. 反转链表 - 力扣（LeetCode）

思路：自己看吧

ListNode* cur = head;
ListNode* pre = nullptr; 
while (cur) {
    ListNode* tmp = cur->next;
    cur->next = pre;
    pre = cur;
    cur = tmp;
}
head = pre;