数据结构：单向链表的六大核心操作详解
这篇主要讲解数据结构中，单向链表，主要有单向链表的销毁，查找中间节点，查找倒数第K个节点，链表的倒置，链表的排序（冒泡和选择），以及判断列表是否有环。
单向链表是数据结构中最基础也最常用的线性结构之一 它由一系列节点组成 每个节点包含数据域存储数据 指针域存储下一个节点的地址 节点间通过指针串联形成链式结构 相比数组 链表插入删除高效 但随机访问需遍历 本文将详细讲解单向链表的核心操作 结合代码示例与通俗讲解 助你彻底掌握
一 单向链表的基本结构
先定义链表节点结构 这是所有操作的基础
#include
#include
// 定义链表节点结构
typedef struct Node {
int data; // 数据域 存储节点数据
struct Node* next; // 指针域 指向下一个节点
} Node;
// 创建新节点 返回节点指针
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node)); // 分配内存
if (newNode == NULL) { // 检查内存分配是否成功
printf("内存分配失败
");
exit(1);
}
newNode->data = data; // 初始化数据域
newNode->next = NULL; // 初始化指针域为空
return newNode;
}
节点通过next指针连接 例如节点A的next指向节点B 节点B的next指向节点C 以此类推 最后一个节点的next为NULL 表示链表结束
二 单向链表的销毁
销毁链表需释放所有节点内存 避免内存泄漏 步骤 遍历链表 逐个释放节点
// 销毁链表 head为头节点指针的指针（需修改头节点指向）
void destroyList(Node** head) {
if (head == NULL || *head == NULL) return; // 空链表直接返回
Node* current = *head; // 当前节点指针
Node* nextNode; // 临时保存下一个节点
while (current != NULL) {
nextNode = current->next; // 保存下一个节点地址
free(current); // 释放当前节点内存
current = nextNode; // 移动到下一个节点
}
*head = NULL; // 头节点指针置空 避免野指针
}
// 示例 销毁链表并打印状态
void exampleDestroy() {
Node* head = createNode(1); // 创建头节点（此处简化 实际可带头节点或不带头节点）
head->next = createNode(2);
head->next->next = createNode(3);
printf("销毁前链表存在
");
destroyList(&head); // 传入头节点指针的地址
if (head == NULL) printf("销毁后链表已为空
");
}
讲解 销毁时需用nextNode暂存下一个节点 否则释放当前节点后会丢失后续节点地址 传入Node**是为了将销毁后的头节点设为NULL
三 查找中间节点
常用快慢指针法 快指针每次走2步 慢指针每次走1步 快指针到尾时 慢指针在中点
// 查找中间节点 返回中间节点指针（奇数长度返回中间 偶数长度返回第一个中间节点）
Node* findMiddleNode(Node* head) {
if (head == NULL || head->next == NULL) return head; // 空链表或单节点直接返回
Node* slow = head; // 慢指针 每次走1步
Node* fast = head; // 快指针 每次走2步
while (fast != NULL && fast->next != NULL) { // 快指针未到尾
slow = slow->next; // 慢指针走1步
fast = fast->next->next; // 快指针走2步
}
return slow; // 慢指针即为中间节点
}
// 示例 查找中间节点
void exampleFindMiddle() {
// 创建链表 1->2->3->4->5
Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
head->next->next->next->next = createNode(5);
Node* middle = findMiddleNode(head);
printf("中间节点数据为 %d
", middle->data); // 输出3（奇数长度中间）
// 偶数长度链表 1->2->3->4
head->next->next->next->next = createNode(4); // 此时链表1-2-3-4-5-4？修正 重新创建
Node* head2 = createNode(1);
head2->next = createNode(2);
head2->next->next = createNode(3);
head2->next->next->next = createNode(4);
Node* middle2 = findMiddleNode(head2);
printf("偶数链表中间节点数据为 %d
", middle2->data); // 输出3（第一个中间节点）
}
讲解 快指针速度是慢指针2倍 路程相同则时间为1/2 故慢指针到中点时快指针到尾 偶数长度时返回靠后的中间节点（如1-2-3-4返回3） 若需靠前则返回第一个中间节点（调整初始fast=head->next即可）
四 查找倒数第K个节点
双指针法 先让指针p1走K步 再p1和p2同步走 p1到尾时p2为倒数第K个
// 查找倒数第K个节点 返回节点指针 K从1开始计数
Node* findKthFromEnd(Node* head, int k) {
if (head == NULL || k <= 0) return NULL; // 空链表或k无效返回NULL
Node* p1 = head; // 先行指针
Node* p2 = head; // 后行指针
// p1先走k步
for (int i = 0; i < k; i++) {
if (p1 == NULL) return NULL; // k大于链表长度 返回NULL
p1 = p1->next;
}
// p1和p2同步走 直到p1到尾
while (p1 != NULL) {
p1 = p1->next;
p2 = p2->next;
}
return p2; // p2即为倒数第k个节点
}
// 示例 查找倒数第2个节点
void exampleFindKth() {
// 创建链表 1->2->3->4->5
Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
head->next->next->next->next = createNode(5);
Node* kthNode = findKthFromEnd(head, 2);
if (kthNode != NULL) printf("倒数第2个节点数据为 %d
", kthNode->data); // 输出4
// 测试k=6（超过长度）
Node* invalid = findKthFromEnd(head, 6);
if (invalid == NULL) printf("k=6 节点不存在
");
}
讲解 若链表长n 倒数第k个即正数第n-k+1个 p1先走k步后 剩余n-k步 p2同步走n-k步到达目标 需注意k合法性（k<=0或k>n时返回NULL）
五 链表的倒置
将链表方向反转 如1->2->3变为3->2->1 常用迭代法（三指针）
// 迭代法倒置链表 返回新头节点
Node* reverseList(Node* head) {
Node* prev = NULL; // 前驱节点 初始为NULL
Node* curr = head; // 当前节点 从原头节点开始
Node* next = NULL; // 后继节点 临时保存
while (curr != NULL) {
next = curr->next; // 保存当前节点的下一个节点
curr->next = prev; // 当前节点指向前驱（反转）
prev = curr; // 前驱后移
curr = next; // 当前节点后移
}
return prev; // 循环结束后prev为新头节点
}
// 示例 倒置链表并打印
void exampleReverse() {
// 创建链表 1->2->3->4
Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
printf("倒置前 ");
Node* temp = head;
while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } // 1 2 3 4
head = reverseList(head); // 倒置后新头节点为4
printf("
倒置后 ");
temp = head;
while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } // 4 3 2 1
}
讲解 迭代法核心是三个指针配合 每次反转当前节点指向 逐步后移 时间复杂度O(n) 空间O(1) 递归法也可实现（先递归到尾节点 再逐层反转）但易栈溢出
六 链表的排序（冒泡与选择）
1 冒泡排序
相邻节点比较交换 每轮将最大节点沉底
// 冒泡排序链表 升序
void bubbleSortList(Node* head) {
if (head == NULL || head->next == NULL) return; // 空或单节点无需排序
int swapped;
Node* ptr;
Node* last = NULL; // 已排序部分的尾节点
do {
swapped = 0;
ptr = head;
while (ptr->next != last) { // 遍历未排序部分
if (ptr->data > ptr->next->data) { // 前大后小则交换数据
int temp = ptr->data;
ptr->data = ptr->next->data;
ptr->next->data = temp;
swapped = 1; // 标记发生交换
}
ptr = ptr->next;
}
last = ptr; // 本轮最大节点已沉底 更新last
} while (swapped); // 无交换则排序完成
}
2 选择排序
每轮找最小节点 与当前位置交换
// 选择排序链表 升序
void selectionSortList(Node* head) {
if (head == NULL || head->next == NULL) return;
Node* curr = head;
while (curr != NULL && curr->next != NULL) {
Node* minNode = curr; // 当前最小节点
Node* temp = curr->next; // 遍历后续节点找最小
while (temp != NULL) {
if (temp->data < minNode->data) minNode = temp;
temp = temp->next;
}
// 交换当前节点与最小节点数据
if (minNode != curr) {
int tempData = curr->data;
curr->data = minNode->data;
minNode->data = tempData;
}
curr = curr->next; // 处理下一节点
}
}
// 示例 链表排序并打印
void exampleSort() {
// 创建无序链表 3->1->4->2
Node* head = createNode(3);
head->next = createNode(1);
head->next->next = createNode(4);
head->next->next->next = createNode(2);
printf("排序前 ");
Node* temp = head;
while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } // 3 1 4 2
bubbleSortList(head); // 冒泡排序后 1 2 3 4
printf("
冒泡排序后 ");
temp = head;
while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; }
// 重置为无序链表 再次选择排序
head->data = 3; head->next->data = 1; head->next->next->data = 4; head->next->next->next->data = 2;
selectionSortList(head); // 选择排序后 1 2 3 4
printf("
选择排序后 ");
temp = head;
while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; }
}
讲解 冒泡排序通过相邻交换 稳定排序 选择排序每轮找最小 不稳定但交换次数少 链表排序可直接交换数据（简单）或交换节点（复杂）
七 判断链表是否有环
快慢指针法 快指针每次2步 慢指针每次1步 相遇则有环
// 判断链表是否有环 有环返回1 无环返回0
int hasCycle(Node* head) {
if (head == NULL || head->next == NULL) return 0; // 空或单节点无环
Node* slow = head; // 慢指针
Node* fast = head; // 快指针
while (fast != NULL && fast->next != NULL) {
slow = slow->next; // 慢指针走1步
fast = fast->next->next; // 快指针走2步
if (slow == fast) return 1; // 相遇则有环
}
return 0; // 快指针到尾无环
}
// 示例 创建有环链表并判断
void exampleHasCycle() {
// 创建链表 1->2->3->4->5 并让5指向3形成环
Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
Node* node5 = createNode(5);
head->next->next->next->next = node5;
node5->next = head->next->next; // 5指向3 形成环
if (hasCycle(head)) printf("链表有环
"); else printf("链表无环
"); // 输出有环
// 无环链表测试
node5->next = NULL; // 断开环
if (hasCycle(head)) printf("链表有环
"); else printf("链表无环
"); // 输出无环
}
讲解 若有环 快指针会追上慢指针（类似操场跑步套圈） 若无环 快指针先到尾 时间复杂度O(n) 空间O(1)
总结
单向链表核心操作围绕指针 manipulation 展开 销毁释放内存 快慢指针解决中间/倒数第K/环检测 迭代反转链表 冒泡选择排序链表 掌握这些操作需理解指针指向变化 多画图模拟过程 结合实际示例调试代码 方能融会贯通 链表是更复杂结构（双向链表 循环链表）的基础 务必扎实掌握
