数据结构 单向链表进阶
一、链表基础定义
首先定义链表节点的数据类型和结构体，这是所有操作的基础，头文件linklist.h内容如下：
#ifndef __LINKLIST_H__
#define __LINKLIST_H__
// 链表节点存储的数据类型（可根据需求修改）
typedef int DataType;
// 链表节点结构体
typedef struct node
{
DataType Data; // 节点数据域
struct node *pNext; // 节点指针域（指向下一个节点）
}Node_t;
// 进阶操作函数声明
extern Node_t *FindMidNode(Node_t *pHead); // 找中间节点
extern Node_t *FindLastNthNode(Node_t *pHead, int Nth); // 找倒数第N个节点
extern int ReveiseLinkList(Node_t *pHead); // 反转链表
extern int BubbleSortLinkList(Node_t *pHead); // 冒泡排序链表
extern int SelectSortLinkList(Node_t *pHead); // 选择排序链表
extern int IsCircleList(Node_t *pHead, int *plen, Node_t **ppTmpNode); // 判断链表是否有环
// 基础操作（依赖）
extern Node_t *CreateEmptyLinkList(void); // 创建空链表
extern int InsertHeadLinkNode(Node_t *pHead, DataType TmpData); // 头插法
extern int InsertTailLinkNode(Node_t *pHead, DataType TmpData); // 尾插法
extern int ShowLinkList(Node_t *pHead); // 打印链表
extern int DestroyLinkList(Node_t **ppHead); // 销毁链表
#endif
二、核心进阶操作实现（linklist.c）
1. 找链表中间节点（快慢指针法）
思路：定义两个指针pFast（快指针）和pSlow（慢指针），快指针每次走 2 步，慢指针每次走 1 步。当快指针走到链表末尾时，慢指针恰好指向链表中间节点（偶数个节点时指向靠后的中间节点）。
#include "linklist.h"
#include
#include
// 找链表中间节点
Node_t *FindMidNode(Node_t *pHead)
{
Node_t *pFast = NULL;
Node_t *pSlow = NULL;
pFast = pSlow = pHead->pNext;
while (pFast != NULL)
{
pFast = pFast->pNext;
if (NULL == pFast)
{
return pSlow;
}
pFast = pFast->pNext;
pSlow = pSlow->pNext;
}
return pSlow;
}
2. 找链表倒数第 N 个节点（快慢指针法）
思路：让快指针先提前走 N 步，然后快慢指针同时走，当快指针走到链表末尾时，慢指针恰好指向倒数第 N 个节点。
// 找链表倒数第N个节点
Node_t *FindLastNthNode(Node_t *pHead, int Nth)
{
Node_t *pFast = NULL;
Node_t *pSlow = NULL;
int i = 0;
pFast = pSlow = pHead;
// 快指针先移动N步
for (i = 0; pFast != NULL && i < Nth; i++)
{
pFast = pFast->pNext;
}
// N超过链表长度，返回NULL
if (NULL == pFast)
{
return NULL;
}
// 快慢指针同步移动，直到快指针到末尾
while (pFast != NULL)
{
pFast = pFast->pNext;
pSlow = pSlow->pNext;
}
return pSlow;
}
3. 反转链表（头插法）
思路：将原链表的节点逐个 “摘下来”，用头插法插入到新的链表头部，最终实现链表反转。
// 反转链表
int ReveiseLinkList(Node_t *pHead)
{
Node_t *pTmpNode = NULL;
Node_t *pInsertNode = NULL;
pTmpNode = pInsertNode = pHead->pNext;
pHead->pNext = NULL; // 清空原链表头节点的指针
while (pTmpNode != NULL)
{
pTmpNode = pTmpNode->pNext; // 保存下一个节点
pInsertNode->pNext = pHead->pNext;// 待插入节点指向新链表头部
pHead->pNext = pInsertNode; // 头节点指向待插入节点
pInsertNode = pTmpNode; // 更新待插入节点
}
return 0;
}
4. 链表冒泡排序
思路：和数组冒泡排序逻辑一致，通过相邻节点的比较和数据交换，将最大的元素逐步 “冒泡” 到链表末尾；引入pEnd标记排序边界，优化循环次数。
// 链表冒泡排序
int BubbleSortLinkList(Node_t *pHead)
{
Node_t *pTmpNode1 = NULL;
Node_t *pTmpNode2 = NULL;
Node_t *pEnd = NULL;
DataType TmpData;
// 空链表或只有一个节点，无需排序
if (NULL == pHead->pNext || NULL == pHead->pNext->pNext)
{
return 0;
}
while (1)
{
pTmpNode1 = pHead->pNext;
pTmpNode2 = pHead->pNext->pNext;
// 排序边界重合，结束排序
if (pEnd == pTmpNode2)
{
break;
}
// 未到排序边界，继续比较交换
while (pTmpNode2 != pEnd)
{
if (pTmpNode1->Data > pTmpNode2->Data)
{
// 交换节点数据（无需移动节点，仅交换数据）
TmpData = pTmpNode1->Data;
pTmpNode1->Data = pTmpNode2->Data;
pTmpNode2->Data = TmpData;
}
pTmpNode1 = pTmpNode1->pNext;
pTmpNode2 = pTmpNode2->pNext;
}
pEnd = pTmpNode1; // 更新排序边界
}
return 0;
}
5. 链表选择排序
思路：遍历链表，找到当前未排序区间的最小节点，将其数据与未排序区间的第一个节点数据交换；逐步缩小未排序区间，直到整个链表有序。
// 链表选择排序
int SelectSortLinkList(Node_t *pHead)
{
Node_t *pSwapNode = NULL;
Node_t *pTmpNode = NULL;
Node_t *pMinNode = NULL;
DataType TmpData;
// 空链表或只有一个节点，无需排序
if (NULL == pHead->pNext || NULL == pHead->pNext->pNext)
{
return 0;
}
pSwapNode = pHead->pNext; // 未排序区间的第一个节点
while (pSwapNode->pNext != NULL)
{
pMinNode = pSwapNode; // 初始化最小节点为未排序区间第一个节点
pTmpNode = pSwapNode->pNext;
// 找未排序区间的最小节点
while (pTmpNode != NULL)
{
if (pTmpNode->Data < pMinNode->Data)
{
pMinNode = pTmpNode;
}
pTmpNode = pTmpNode->pNext;
}
// 交换最小节点和未排序区间第一个节点的数据
if (pSwapNode != pMinNode)
{
TmpData = pSwapNode->Data;
pSwapNode->Data = pMinNode->Data;
pMinNode->Data = TmpData;
}
pSwapNode = pSwapNode->pNext; // 缩小未排序区间
}
return 0;
}
6. 判断链表是否有环（并找环入口 / 环长度）
思路：
- 判环：快慢指针法，快指针每次走 2 步，慢指针每次走 1 步，若两指针相遇则链表有环；
- 找环长度：相遇后，固定一个指针，另一个指针继续走，再次相遇时走过的步数即为环长度；
- 找环入口：相遇后，将其中一个指针重置到链表头，两指针以相同步长走，相遇点即为环入口。
// 判断链表是否有环，返回1有环/0无环；plen返回环长度；ppTmpNode返回环入口节点
int IsCircleList(Node_t *pHead, int *plen, Node_t **ppTmpNode)
{
Node_t *pFast = NULL;
Node_t *pSlow = NULL;
Node_t *pMeetNode = NULL;
int len = 0;
pSlow = pFast = pHead->pNext;
while (1)
{
pFast = pFast->pNext;
if (NULL == pFast) return 0;
pFast = pFast->pNext;
if (NULL == pFast) return 0;
pSlow = pSlow->pNext;
if (pSlow == pFast) // 快慢指针相遇，存在环
{
pMeetNode = pSlow;
break;
}
}
// 计算环长度
pSlow = pMeetNode->pNext;
len++;
while (pSlow != pMeetNode)
{
len++;
pSlow = pSlow->pNext;
}
*plen = len;
// 找环入口
pFast = pMeetNode;
pSlow = pHead->pNext;
while (pFast != pSlow)
{
pFast = pFast->pNext;
pSlow = pSlow->pNext;
}
*ppTmpNode = pSlow;
return 1;
}
三、测试代码（main.c）
以下测试代码覆盖所有进阶操作，可直接编译运行：
#include "linklist.h"
#include
int main(void)
{
Node_t *plinklist = NULL;
Node_t *pTmpNode = NULL;
int len = 0;
// 1. 创建空链表
plinklist = CreateEmptyLinkList();
// 2. 头插法插入节点
InsertHeadLinkNode(plinklist, 1);
InsertHeadLinkNode(plinklist, 2);
InsertHeadLinkNode(plinklist, 3);
InsertHeadLinkNode(plinklist, 4);
InsertHeadLinkNode(plinklist, 5);
printf("初始链表（头插）：");
ShowLinkList(plinklist);
// 3. 尾插法扩展链表
InsertTailLinkNode(plinklist, 6);
InsertTailLinkNode(plinklist, 7);
InsertTailLinkNode(plinklist, 8);
InsertTailLinkNode(plinklist, 9);
InsertTailLinkNode(plinklist, 10);
printf("尾插后链表：");
ShowLinkList(plinklist);
// 4. 找中间节点
pTmpNode = FindMidNode(plinklist);
printf("链表中间节点值：%d
", pTmpNode->Data);
// 5. 找倒数第3个节点
pTmpNode = FindLastNthNode(plinklist, 3);
printf("链表倒数第3个节点值：%d
", pTmpNode->Data);
// 6. 反转链表
ReveiseLinkList(plinklist);
printf("反转后链表：");
ShowLinkList(plinklist);
// 7. 选择排序（注释掉可切换为冒泡排序）
// BubbleSortLinkList(plinklist);
SelectSortLinkList(plinklist);
printf("排序后链表：");
ShowLinkList(plinklist);
// 8. 测试链表判环（可选）
#if 1
// 手动制造环：尾节点指向第5个节点
pTmpNode = plinklist->pNext;
while (pTmpNode->pNext != NULL)
{
pTmpNode = pTmpNode->pNext;
}
pTmpNode->pNext = plinklist->pNext->pNext->pNext->pNext->pNext;
if (IsCircleList(plinklist, &len, &pTmpNode))
{
printf("链表有环 | 环长度：%d | 环入口节点值：%d
", len, pTmpNode->Data);
}
else
{
printf("链表无环
");
}
#endif
// 9. 销毁链表
DestroyLinkList(&plinklist);
printf("链表销毁后头指针：%p
", plinklist);
return 0;
}
四、编译运行结果
初始链表（头插）：5 4 3 2 1
尾插后链表：5 4 3 2 1 6 7 8 9 10
链表中间节点值：1
链表倒数第3个节点值：8
反转后链表：10 9 8 7 6 1 2 3 4 5
排序后链表：1 2 3 4 5 6 7 8 9 10
链表有环 | 环长度：6 | 环入口节点值：6
链表销毁后头指针：(nil)
