C语言实现无头单向非循环链表：接口与经典算法解析

链表结构与内存特性

链表是一种物理存储结构上非连续、非顺序的存储结构，其数据元素的逻辑顺序依赖于节点间的指针链接。简单来说，链表由一系列结构体组成，通过指针指向下一个节点的地址来串联数据。

相比于顺序表（数组），链表具有以下显著特点：

• 内存利用率：顺序表通常预分配较大内存块，易造成浪费；链表则是按需动态申请节点（malloc/realloc），用多少存多少，无明显预留空间浪费。
• 操作效率：顺序表在头部或中间插入/删除元素时，需移动大量数据，时间复杂度为 O(N)；链表只需修改相邻节点的指针指向，即可实现插入和删除，不受数据量影响。

实际开发中，链表结构可根据不同维度组合出多种形态，主要取决于三个要素的组合：

1. 方向：单向、双向。
2. 带头情况：带头（存在哨兵位节点）、不带头。
3. 循环情况：循环、非循环。

以下是几种典型链表结构的示意：

带头节点： 链表包含一个不存储有效数据的哨兵位头节点。其优势在于统一了操作入口，例如头插时无需处理二级指针，因为头指针始终指向该固定节点。

双向链表： 每个节点包含两个指针，分别指向前驱和后继节点，支持双向遍历。

循环链表： 尾节点的指针不再指向 NULL，而是指向头节点（或哨兵节点），形成闭环。

无头单向非循环链表接口实现

无头单向非循环链表是最基础的链表形式，由于没有哨兵节点，头指针 phead 直接指向第一个有效数据节点。在实现涉及头结点变化的操作时（如头删、头插），通常需要传入二级指针 **pphead。

第1步：定义节点与动态创建

首先定义链表节点结构体，并提供一个辅助函数用于动态申请节点。该函数负责分配内存、初始化数据域和指针域，并在分配失败时输出错误提示。

// 假设已定义 SLTNode 结构和 SLDataType 类型
SLTNode* BuySListNode(SLDataType x)
{
	SLTNode* newnode = malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

第2步：链表打印与遍历

遍历链表是后续所有操作的基础。打印函数从头节点开始，逐个访问直至空指针，直观展示当前链表状态。

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

第3步：尾部插入与删除（尾插 & 尾删）

尾插（PushBack）： 若链表为空，直接令头指针指向新节点；否则遍历至尾部节点，将原尾节点的 next 指向新节点。

void SListPushBack(SLTNode** pphead, SLDataType x)
{
	if (*pphead == NULL)
	{
		*pphead = BuySListNode(x);
		return;
	}
	SLTNode* tail = *pphead;
	// 寻找尾节点
	while (tail->next)
	{
		tail = tail->next;
	}
	tail->next = BuySListNode(x);
}

尾删（PopBack）： 需注意链表为空（直接返回）、链表仅有一个节点（置头指针为空）和多个节点三种情况。多节点时需找到倒数第二个节点（prev），释放尾节点（tail），并将 prev->next 置为 NULL。

void SListPopBack(SLTNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else if((*pphead)->next == NULL)
	{
		free(*pphead); // 建议释放最后一个节点防止内存泄漏
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

第4步：头部插入与删除（头插 & 头删）

头插（PushFront）： 创建一个新节点，让其 next 指向当前头节点，然后更新头指针指向新节点。

void SListPushFront(SLTNode** pphead, SLDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

头删（PopFront）： 保存当前头节点指针，头指针后移指向下一个节点，最后释放被删除的节点。

void SListPopFront(SLTNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	SLTNode* temp = *pphead;
	(*pphead) = (*pphead)->next;
	free(temp);
}

第5步：查找、指定位置前插入与删除

查找（Search）： 从头开始遍历，比对数据，返回匹配节点的指针，未找到返回 NULL。

SLTNode* SListSearch(SLTNode* phead, SLDataType x)
{
	while (phead)
	{
		if (phead->data == x)
		{
			return phead;
		}
		phead = phead->next;
	}
	return NULL;
}

在 pos 之前插入（Insert）： 特殊处理需插入到头部的情况（pos == *pphead）；其他情况遍历找到 pos 的前驱节点，修改指针指向。

void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL || pos == NULL)
	{
		return;
	}
	// 插在头部特殊情况
	if (*pphead == pos)
	{
		newnode->next = pos;
		*pphead = newnode;
	}
	else
	{
		SLTNode* cur = *pphead;
		// 确保能找到pos的前驱，否则无法在非头部插入
		while (cur && cur->next != pos)
		{
			cur = cur->next;
		}
		if (cur != NULL) 
		{
			newnode->next = pos;
			cur->next = newnode;
		}
	}
}

删除 pos 位置节点（Erase）： 同样需要处理 pos 为头节点的情况。若非头节点，需找到前驱节点 cur，令 cur->next 指向 pos->next，再释放 pos。

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	if (*pphead == NULL || pos == NULL)
	{
		return;
	}
	if (*pphead == pos)
	{
		*pphead = (*pphead)->next;
		free(pos);
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur && cur->next != pos)
		{
			cur = cur->next;
		}
		if (cur != NULL)
		{
			cur->next = pos->next;
			free(pos);
		}
	}
}

基于链表的经典算法训练

算法1：移除链表元素（LeetCode 203）

问题描述： 给定链表头节点 head 和整数 val，删除所有 Node.val == val 的节点，返回新的头节点。

思路分析：

采用前后指针（prev 和 cur）配合遍历。若 cur 值匹配：
- 若 cur 是头节点，则更新 head 指针跳过该节点并释放内存。
- 若非头节点，则让 prev->next 跳过 cur。

优化代码：

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    while(cur) {
        if(cur->val == val) {
            if(cur == head) {
                head = cur->next;
                free(cur);
                cur = head; // 继续检查新的头节点是否也需要删除
            } else {
                prev->next = cur->next;
                free(cur);
                cur = prev->next; // 释放后的cur可能为NULL，需重新判断循环条件，但此处逻辑简单可简化为cur=prev->next
            }
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

注意：上述代码在删除非头节点时，cur 指向的位置已被释放，应谨慎处理指针跳跃或直接复用更清晰的迭代模式。更简洁的做法是使用虚拟头节点或者如下调整：

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    struct ListNode* prev = dummyHead;
    struct ListNode* cur = head;
    while(cur) {
        if(cur->val == val) {
            prev->next = cur->next;
            free(cur);
            cur = prev->next;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
    head = dummyHead->next;
    free(dummyHead);
    return head;
}

算法2：反转单链表（LeetCode 206）

问题描述： 反转链表并返回新头节点。

思路分析： 使用“头插法”的思路最为直观。维护一个新的空链表头 newhead，依次取出原链表节点，将其作为新链表的头节点插入。

关键步骤：

1. 记录当前节点 cur 的下一个节点 next，防止断链。
2. 将 cur->next 指向 newhead。
3. 更新 newhead = cur。
4. 移动 cur = next 继续下一轮。

完整实现：

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;
    while(cur) {
        struct ListNode* next = cur->next; // 备份下一个节点
        cur->next = newhead;               // 当前节点指向前一个新头节点
        newhead = cur;                     // 更新新头节点
        cur = next;                        // 继续向后遍历
    }
    return newhead;
}

此方法避免了复杂的空指针判断，逻辑清晰且执行效率高。需要注意的是，每次循环开始时先备份 next 是防止断开原始链表路径的关键。

总结

无头单向非循环链表是学习数据结构的基石。掌握其内存分布特性以及各接口的指针操作细节（特别是涉及头指针变化时的二级指针处理），对于解决复杂指针问题至关重要。通过练习移除元素和反转链表等经典算法，可以进一步巩固对双指针技巧和头插法的理解。

以上就是C语言实现无头单向非循环链表的详细内容，更多关于C语言链表算法的资料请关注本站其它相关文章！