当前位置：首页 > article >正文

数据结构之【无头单向非循环链表】(C语言实现)

article 2025/3/3 10:22:47

下面将无头单向非循环链表简称为单链表

头指针：指向链表第一个节点的指针

链表为空时，头指针也为空

要实现单链表，就是要实现单链表的增删查改

一、无头单向非循环链表的c语言实现

1.准备工作

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataTypde;

typedef struct SLTNode
{
	SLTDataTypde data;
	struct SLTNode* next;
}SLTNode;

(1)重定义 数据类型的名称

方便后续只改这一处，就可以实现数据类型的改变

(2)定义节点，并简化名称

(3)包含相应头文件(动态开辟、库函数、断言)

2.动态申请一个节点

SLTNode* BuyNewNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
		return NULL;

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

(1)注意申请失败的情况

3.打印单链表

void SLTPrint(SLTNode* plist)
{
	SLTNode* cur = plist;
	while (cur)
	{
		printf("%d->", cur->data);

		cur = cur->next;
	}

	printf("NULL\n");
}

(1)传入头节点的地址

(2)创建一个新变量用以遍历链表

防止后续找不到头节点

(3)打印格式看需求

4.单链表尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	//断言
	assert(pphead);
	//创建新节点尾插
	SLTNode* newnode = BuyNewNode(x);
	//尾插
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}

}

(1)当指针不能为空时，断言一下，减少调试成本

(2)考虑尾插的实际情况：

链表为空：直接赋值

此时需要改变头指针的值，传入二级指针

链表至少有一个节点：先找尾，再尾插

5.单链表头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	//断言
	assert(pphead);
	//创建
	SLTNode* newnode = BuyNewNode(x);
	//头插
	newnode->next = *pphead;
	*pphead = newnode;
}

(1)显然，需要改变头指针的指向

即，改变头指针的值，所以传入二级指针

6.单链表尾删

void SLTPopBack(SLTNode** pphead)
{
	//断言
	assert(pphead);
	assert(*pphead);
	//尾删
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		/*SLTNode *tail = *pphead;
		SLTNode *prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}

		prev->next = tail->next;
		free(tail);
		tail = NULL;*/
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

(1) 对于第二个断言：

链表不为空才可以尾删

(2) 分情况尾删：

只有一个节点：直接释放内存，然后置空头指针

要改变头指针，传入二级指针

至少两个节点：

先找到倒数第二个节点，再释放尾节点，然后将倒数第二个节点的next置空

直接释放尾节点，会导致倒数第二个节点的next成为野指针

(3) 展示了两种找尾的方法

7.单链表头删

void SLTPopFront(SLTNode** pphead)
{
	//断言
	assert(pphead);
	assert(*pphead);
	//头删
	SLTNode* first = (*pphead)->next;
	free(*pphead);
	*pphead = first;
}

(1)直接释放头节点会找不到下一个节点

先存储下一个节点，再释放，然后再改变头指针的值

8.单链表查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;

		cur = cur->next;
	}
	return NULL;
}

(1)只是查找到第一个，有局限

9.单链表在pos位置之后插入x

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = BuyNewNode(x);

	newnode->next = pos->next;
	pos->next = newnode;
}

(1) 链表为空，直接头插就行，不用调用该函数

(2)不在pos位置之前插入，

第一，需要考虑头插和中间插的情况

第二，可能需要保存前一个节点

总体来说，效率不高

10.单链表删除pos位置之后的值

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);

	SLTNode* del = pos->next;
	SLTNode* next = pos->next->next;
	pos->next = next;
	free(del);
	del = NULL;
}

(1)pos为空或pos之后的第一个节点为空

肯定时不能进行删除的

(2)直接释放下个节点会导致找不到下下个节点

需要提前保存下下个节点

(3)如果删除pos位置的节点

第一，需要考虑头删和中间删的情况

第二，可能需要保存前一个节点

总体来说，这样的效率不高

二、链表面试题及其体会

1.203. 移除链表元素 - 力扣（LeetCode）

本题选用尾插的思路，

做题用到尾插时，带上哨兵位，减少情况的讨论

只是需要注意释放该内存

2.206. 反转链表 - 力扣（LeetCode）

本题选用头插的思路

头插不用考虑哨兵位问题

3.876. 链表的中间结点 - 力扣（LeetCode）

本题选用快慢指针的思路

注意奇偶性的不同情况

4.面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

本题注意

倒数第k个节点与倒数第1个节点的距离是k-1

一样采用双指针的思路

快的先走k-1步，此时，快慢指针之间相差k-1步

再同时走，直到快指针到尾即可

5.21. 合并两个有序链表 - 力扣（LeetCode）

两两比较，小的弄下来尾插

6.链表分割_牛客题霸_牛客网

小于x的节点尾插到一个链表

大于等于x的节点尾插到另一个链表

再连接两个链表

注意使用哨兵位减少空链表的讨论

注意链表的尾节点指向空

7.链表的回文结构_牛客题霸_牛客网

找到中间节点，反转后半段

再进行比较

本题需运用第2题和第3题的思想方法

8.160. 相交链表 - 力扣（LeetCode）

判断链表相交，那么它们的尾节点一定相同

指向长的链表的指针先走差距步，

然后再同时走，

直到指向长的链表的指针和指向短的链表的指针相同就结束

9.141. 环形链表 - 力扣（LeetCode）

采用快慢指针的方法

注意

最好让快指针一次走两步，

慢指针一次走一步，

如果有环，那么它们终会相遇

不然快指针就会先为空或先到尾节点

其他情况，链表有环，但是，

快指针一次比慢指针多走x步

（x>=2)

这时需要考虑

1.慢指针刚进环时，与快指针的差距

2.如果错过，又比较第二次的差距

3.以此类推......

根据每次的差距与x的关系，才能得出

快慢指针究竟是错过还是相遇

10.142. 环形链表 II - 力扣（LeetCode）

依据

链表有环并且快指针一次走2步

慢指针一次走1步的前提，设

(1)链表从头节点到入环的第一个节点的距离为L

(L>=1)

(2)快慢指针相遇的位置与入环的第一个节点的距离为X

(3）环的周长为C

则，

(1)慢指针走的距离为：L+X

(0 <= X < C）

因为快慢指针最开始的差距最大为 C - 1

慢指针在起点，快指针多走一步

(2)慢指针走的距离为：L+X+n*C

(n >= 1)

假设 n 最小为 0，

那么此时快慢指针走的距离相等，这不符合逻辑，错误

那么快指针要走到相遇点至少要走1圈的长度

(3)快指针走的距离是慢指针的2倍

2 * (L+X) = L+X+n*C

L + X = n*C

L = n*C - X

L = (n - 1)*C + C - X