上一篇下一篇单链表的两个核心缺点目 录单向循环链表Circular Linked List1什么是循环链表2常用操作2.1初始化空循环链表2.2在末尾插入新节点2.3删除第一个值为 target 的节点2.4打印整个循环链表避免死循环3完整示例程序单向循环链表Circular Linked List1什么是循环链表循环链表是单链表的一种变形其特点是最后一个节点的next指针不再指向NULL而是指向链表的第一个节点或头节点从而形成一个闭环结构其余结构和操作方法和单链表很类似只是为尾节点判断方式变了。主要特点无真正“尾部”从任意节点出发沿next指针遍历最终都会回到起点空链表判断特殊若使用带头节点的结构空表满足head-next head适合循环场景如约瑟夫问题、轮询调度、环形缓冲区等2常用操作假设采用带哨兵头节点的单向循环链表头节点不存有效数据仅作起始标记空表时head-next head。2.1初始化空循环链表/** * brief: initCircularList —— 创建并初始化一个带头节点的空循环链表 * return: 指向头节点的指针失败时返回 NULL * note: 头节点 data 无意义其 next 指向自身表示空表。 */ListNode*initCircularList(){ListNode*head(ListNode*)malloc(sizeof(ListNode));if(headNULL)returnNULL;// 没有空间造成分配内存失败head-nexthead;// 关键空循环链表中头节点指向自己returnhead;}2.2在末尾插入新节点/** * brief: insertAtTail —— 在循环链表尾部插入新节点 * param[in,out]: head - 链表头指针不可为 NULL * param[in]: value - 要插入的数据 * return: 成功返回 true失败返回 false * note: 尾部即头节点的前一个位置。时间复杂度 O(n)。 */boolinsertAtTail(ListNode*head,intvalue){if(headNULL)returnfalse;// 创建新节点ListNode*newNode(ListNode*)malloc(sizeof(ListNode));if(newNodeNULL)returnfalse;newNode-datavalue;// 找到当前尾节点即 head 的前驱ListNode*tailhead;while(tail-next!head){tailtail-next;}// 插入新节点tail-nextnewNode;newNode-nexthead;// 新尾节点指向头保持循环returntrue;}2.3删除第一个值为 target 的节点/** * brief: deleteByValue —— 删除循环链表中第一个值等于 target 的节点 * param[in,out]: head - 链表头指针不可为 NULL * param[in]: target - 要删除的目标值 * return: 成功删除返回 true未找到返回 false * note: 若删除后链表为空则 head-next 仍指向 head。 */booldeleteByValue(ListNode*head,inttarget){if(headNULL||head-nexthead){returnfalse;// 空表}ListNode*prevhead;ListNode*currenthead-next;// 遍历直到回到 headwhile(current!head){if(current-datatarget){prev-nextcurrent-next;free(current);returntrue;}prevcurrent;currentcurrent-next;}returnfalse;// 未找到}2.4打印整个循环链表避免死循环/** * brief: printCircularList —— 安全打印循环链表内容 * param[in]: head - 链表头指针 * return: 链表长度不含头节点 * note: 从 head-next 开始遇到 head 停止防止无限循环。 */intprintCircularList(ListNode*head){if(headNULL||head-nexthead){printf(循环链表为空。\n);return0;}printf(循环链表: );ListNode*currenthead-next;intcount0;while(current!head){printf(%d - ,current-data);currentcurrent-next;count;}printf((回到头)\n);returncount;}3完整示例程序#includestdio.h#includestdlib.h#includestdbool.h// 定义链表节点结构typedefstructListNode{intdata;structListNode*next;}ListNode;/** * brief: initCircularList —— 创建并初始化一个带头节点的空循环链表 * return: 指向头节点的指针失败时返回 NULL * note: 头节点 data 无意义其 next 指向自身表示空表。 */ListNode*initCircularList(){ListNode*head(ListNode*)malloc(sizeof(ListNode));if(headNULL)returnNULL;head-nexthead;// 关键空循环链表中头节点指向自己returnhead;}/** * brief: insertAtTail —— 在循环链表尾部插入新节点 * param[in,out]: head - 链表头指针不可为 NULL * param[in]: value - 要插入的数据 * return: 成功返回 true失败返回 false * note: 尾部即头节点的前一个位置。时间复杂度 O(n)。 */boolinsertAtTail(ListNode*head,intvalue){if(headNULL)returnfalse;ListNode*newNode(ListNode*)malloc(sizeof(ListNode));if(newNodeNULL)returnfalse;newNode-datavalue;// 找到当前尾节点即 head 的前驱ListNode*tailhead;while(tail-next!head){tailtail-next;}// 插入新节点tail-nextnewNode;newNode-nexthead;// 新尾节点指向头保持循环returntrue;}/** * brief: deleteByValue —— 删除循环链表中第一个值等于 target 的节点 * param[in,out]: head - 链表头指针不可为 NULL * param[in]: target - 要删除的目标值 * return: 成功删除返回 true未找到返回 false * note: 若删除后链表为空则 head-next 仍指向 head。 */booldeleteByValue(ListNode*head,inttarget){if(headNULL||head-nexthead){returnfalse;// 空表}ListNode*prevhead;ListNode*currenthead-next;// 遍历直到回到 headwhile(current!head){if(current-datatarget){prev-nextcurrent-next;free(current);returntrue;}prevcurrent;currentcurrent-next;}returnfalse;// 未找到}/** * brief: printCircularList —— 安全打印循环链表内容 * param[in]: head - 链表头指针 * return: 链表长度不含头节点 * note: 从 head-next 开始遇到 head 停止防止无限循环。 */intprintCircularList(ListNode*head){if(headNULL||head-nexthead){printf(循环链表为空。\n);return0;}printf(循环链表: );ListNode*currenthead-next;intcount0;while(current!head){printf(%d - ,current-data);currentcurrent-next;count;}printf((回到头)\n);returncount;}/** * brief: destroyCircularList —— 销毁整个循环链表并释放内存 * param[in,out]: head - 链表头指针的地址 * return: 无 * note: 释放所有节点后将头指针置为 NULL。 */voiddestroyCircularList(ListNode**headRef){if(headRefNULL||*headRefNULL)return;ListNode*head*headRef;if(head-nexthead){// 空表只释放头节点free(head);*headRefNULL;return;}// 从第一个有效节点开始释放ListNode*currenthead-next;while(current!head){ListNode*nextcurrent-next;free(current);currentnext;}// 最后释放头节点free(head);*headRefNULL;}// 主函数完整示例intmain(){// 1. 初始化空循环链表ListNode*headinitCircularList();if(headNULL){printf(初始化失败\n);return-1;}printf( 初始化空链表 \n);printCircularList(head);// 2. 插入元素printf(\n 插入元素 10, 20, 30 \n);insertAtTail(head,10);insertAtTail(head,20);insertAtTail(head,30);intlenprintCircularList(head);printf(链表长度: %d\n,len);// 3. 删除中间元素printf(\n 删除元素 20 \n);if(deleteByValue(head,20)){printf(删除成功\n);}else{printf(未找到要删除的元素。\n);}printCircularList(head);// 4. 删除不存在的元素printf(\n 尝试删除不存在的元素 99 \n);if(deleteByValue(head,99)){printf(删除成功\n);}else{printf(未找到要删除的元素。\n);}printCircularList(head);// 5. 清理内存printf(\n 销毁链表 \n);destroyCircularList(head);if(headNULL){printf(链表已成功销毁。\n);}return0;}运行结果为 初始化空链表 循环链表为空。 插入元素 10, 20, 30 循环链表: 10 - 20 - 30 - (回到头) 链表长度: 3 删除元素 20 删除成功 循环链表: 10 - 30 - (回到头) 尝试删除不存在的元素 99 未找到要删除的元素。 循环链表: 10 - 30 - (回到头) 销毁链表 链表已成功销毁。提示实际应用中若频繁在尾部操作可使用尾指针rear代替头指针使尾部插入变为 O(1)。此时空表条件为rear-next rear。