数据结构（三）---单向循环链表

 单向循环链表（Circular Linked List）

一、基本概念

循环链表是一种特殊的链表，其末尾节点的后继指针指向头结点，形成一个闭环。

循环链表的操作与普通链表基本一致，但需注意循环特性的处理。

二、代码实现

clList.h

#ifndef _CLLIST_H
#define _CLLIST_H#include <stdio.h>
#include <stdlib.h>
#include <string.h>//定义节点数据的类型
typedef int DATA;//定义一个单向循环链表的节点
typedef struct node
{DATA data;     //节点数据域struct node *next;     //指针域，指向后继节点
}NODE;//函数原型的声明
/*** 创建链表* @param head 待操作的链表* @param data 待插入的数据* @return 成功返回0，否则返回-1*/
extern int cllist_create(NODE **head, DATA data);/*** 在循环链表插入新节点（把新节点插入到头节点之前）* @param head 待操作的链表（默认是头节点）* @param data 待插入的数据* @return 成功返回0，否则返回-1*/
extern int cllist_insert(NODE **head, DATA data);/*** 实现无头节点的头插法（插入在头节点之前）* @param head 待操作的链表（默认是头节点）* @param data 待插入的数据* @return 成功返回0，否则返回-1*/
extern int cllist_insertAthead(NODE **head, DATA data);/*** 遍历链表数据* @param head 待遍历的链表* @return 成功返回0，否则返回-1*/
extern int cllist_showAll(const NODE *head);/*** 根据data返回查找对应的节点* @param head 待操作的链表* @param data 需要查找的节点数据* @return 查找到的节点*/
extern NODE *cllist_find(const NODE *head, DATA data);/*** 根据newdata修改old对应的节点数据* @param head 待操作的链表* @param old 待修改的原数据* @param newdata 待修改的新数据* @return 成功返回0，否则返回-1*/
extern int cllist_update(const NODE *head, DATA old, DATA newdata);/*** 根据data删除对应的节点* @param head 待操作的链表* @param data 待删除的节点数据* @return 成功返回0，否则返回-1*/
extern int cllist_delete(NODE **head, DATA data);/*** 销毁整个链表* @param head 待销毁的链表*/
extern void cllist_destroy(NODE **head);#endif //_CLLIST_H

clList.c

#include "clList.h"//函数原型的声明
/*** 创建链表* @param head 待操作的链表(head是指向头节点指针的地址)* @param data 待插入的数据* @return 成功返回0，否则返回-1*/
int cllist_create(NODE **head, DATA data)
{//如果链表存在，就无需创建if(*head){//打印错误信息到标准错误流（避免影响正常输出）fprintf(stderr, "链表已存在，无需创建！\n");return -1;}//单向循环链表//创建一个新节点NODE *p = (NODE*)malloc(sizeof(NODE));//校验新节点是否创建成功if(!p)return -1;//初始化新节点p->data = data;p->next = p;     //循环特性：单个节点的next指向自身(即使单个节点也形成环）//设置头指针*head = p;     //将头指针设置为自己
}/*** 实现无头节点的头插法（插入在头节点之前）* @param head 待操作的链表（默认是头节点）* @param data 待插入的数据* @return 成功返回0，否则返回-1*/
int cllist_insertAthead(NODE **head, DATA data)
{//创建一个新节点NODE *pNew = (NODE*)malloc(sizeof(NODE));if(!pNew){fprintf(stderr, "创建新节点失败！\n");return -1;}//初始化新节点的数据域，指针域暂不赋值pNew->data = data;NODE *p = *head;     //创建一个遍历指针用来遍历链表寻找尾节点//如果是空链表if(!p){pNew->next = pNew;*head = pNew;return 0;}//非空链表pNew->next = *head;     //新节点的next指向原头节点//查找尾节点(原链表的最后一个节点）while(p->next != *head)     //单向循环链表的尾节点next永远指向头节点（非NULL）{p = p->next;}//此时p是尾节点p->next = pNew;*head = pNew;return 0;
}/*** 在循环链表插入新节点（把新节点插入到头节点之前）* @param head 待操作的链表（默认是头节点）* @param data 待插入的数据* @return 成功返回0，否则返回-1*/
int cllist_insert(NODE **head, DATA data)
{//创建新节点NODE *p = (NODE*)malloc(sizeof(NODE));//校验节点是否创建成功if(!p)return -1;//初始化新节点p->data = data;p->next = p;     //此时创建的新节点与链表还无关//情景1：若待插入的链表是空链表if(*head == NULL){*head = p;     //设置头指针，相当于创建了一个新链表return 0;}//情景2：若待插入的链表是非空链表（在头节点和头节点的next之间插入，头节点不变）p->next = (*head)->next;     //新节点指向原头节点的下一个节点(*head)->next = p;     //头节点指向新节点}/*** 遍历链表数据* @param head 待遍历的链表* @return 成功返回0，否则返回-1*/
int cllist_showAll(const NODE *head)
{//创建临时指针用于遍历（保持头指针不变）const NODE *p = head;     //p指向当前遍历的节点//空链表if(!p){fprintf(stderr, "空链表，没有数据!\n");return -1;}//遍历列表do     //使用do—while保证至少执行依次（应对单节点循环链表）{printf("%d\t", p->data);p = p->next;}while(p != head);     //循环终止条件：回到起始节点printf("\n");return 0;
}/*** 根据data返回查找对应的节点* @param head 待操作的链表* @param data 需要查找的节点数据* @return 查找到的节点*/
NODE *cllist_find(const NODE *head, DATA data)
{//使用const指针避免意外修改节点const NODE *p = head;//空链表if(!head)return NULL;//遍历列表（确保至少执行一次）do{if(memcmp(&(p->data), &data, sizeof(DATA)) == 0){return (NODE*)p;     //强转，避免类型不匹配}p = p->next;}while(p != head);return NULL;
}/*** 根据newdata修改old对应的节点数据* @param head 待操作的链表* @param old 待修改的原数据* @param newdata 待修改的新数据* @return 成功返回0，否则返回-1*/
int cllist_update(const NODE *head, DATA old, DATA newdata)
{NODE *p = cllist_find(head, old);if(!p){fprintf(stderr, "数据未找到！\n");return -1;}//找到旧数据的节点更新为新数据p->data = newdata;return 0;
}/*** 根据data删除对应的节点* @param head 待操作的链表* @param data 待删除的节点数据* @return 成功返回0，否则返回-1*/
int cllist_delete(NODE **head, DATA data)
{//尾随法(p为当前节点，q为前驱节点)NODE *p = *head, *q = NULL;//空链表if(!*head)return -1;//遍历节点while(p){//找到要删除数据的位置if(memcmp(&(p->data), &data, sizeof(DATA)) == 0){//若要删除的节点是头节点if(q == NULL)     //指针还没有进行尾随，证明是头节点{q = p->next;     //获取头节点的下一个节点//如果此头节点是唯一的头节点(p的next执行自身--头节点）if(p->next == *head){//链表置空*head = NULL;}else     //链表中除了要删除的头节点还有其他节点{//替换法（复制下一节点的数据并删除下一节点）p->data = q->data;     //用头节点的后续节点数据替换头节点的数据，删除后续节点p->next = q->next;free(q);}return 0;}//如果要删除的节点是非头节点q->next = p->next;     //前驱节点跳过当前节点free(p);     //释放当前节点return 0;}q = p;p = p->next;//因为是循环链表，所以要想办法终结循环链表if(p == *head)break;}return -1;
}/*** 销毁整个单向循环链表* @param head 待销毁的链表*/
void cllist_destroy(NODE **head)
{//空链表if(!*head)return;//在链表中找节点就用指针尾随法NODE *p = *head, *q = NULL;     //p指向当前节点，q用于保存待释放节点while(p){q = p;p = p->next;free(q);//解除循环链表if(p == *head)break;}*head = NULL;     //将头节点置空，不然会产生野指针
}

app.c

#include "clList.h"int main(int argc,char *argv[])
{NODE *head = NULL;//测试创建和插入cllist_create(&head, 111);     //创建头节点cllist_insert(&head, 222);cllist_insert(&head, 333);cllist_insert(&head, 444);cllist_showAll(head);     //111 444 333 222cllist_insertAthead(&head, 222);cllist_insertAthead(&head, 333);cllist_insertAthead(&head, 444);cllist_showAll(head);     //444 333 222 111 444 333 222//测试更新cllist_update(head, 333, 3333);cllist_showAll(head);     //444 3333 222 111 444 333 222//测试删除cllist_delete(&head, 444);cllist_showAll(head);     //3333 222 111 444 333 222//销毁链表cllist_destroy(&head);cllist_showAll(head);     //空链表，没有数据return 0;
}

三、优缺点总结

• 优点

  1. 动态内存：无需预分配固定大小，适合数据量不确定的场景。

  2. 高效操作

     • 头插/头删：O(1)时间复杂度

     • 尾插：O(1)（维护尾指针时）或O(n)

     • 中间插入：O(1)（定位后）

  3. 循环特性：适合周期性访问场景（如：轮询调度、循环缓冲区）

  4. 内存效率：按需分配，无扩容浪费

• 缺点：

  1. 随机访问 ：必须遍历，时间复杂度O(n)

  2. 存储开销 ：每个节点需额外存储指针

  3. 循环陷阱 ：未正确处理终止条件会导致死循环

  4. 缓存不友好 ：节点内存不连续，访问速度低于数组。

  5. 边界处理 ：需特殊处理头尾节点的指针更新。

四、常见问题

1、数据结构的应用场景

所有编程领域都会涉及，例如

• 链表：内存管理、任务队列

• 树/图：数据库索引、路径规划

• 哈希表：高速缓存、字典实现

2、面试题--单次遍历找到倒数第50个节点

解法：使用双指针技术

1. 初始化指针fast和slow指向头节点

2. fast先移动50步

3. 然后fast和slow同步移动，当fast到达末尾时，slow即指向倒数第50个节点

//单链表找倒数第k节点
NODE *findLastKth(NODE *head, int k)
{NODE *fast = head, *slow = head;//先让快指针前进k步for(int i = 0; i < k; i++){//若快指针提前变空，说明链表长度不足kif(!fast)return NULL;     fast = fast->next;}while(fast != NULL){//循环链表终止条件fast = fast->next;slow = slow->next;}return slow;
}

//循环链表找倒数第k节点
NODE *findLastKth_Circular(NODE *head, int k)
{if(!head || k <= 0)return NULL;NODE *fast = head, *slow = head;//快指针先快走n步for(int i = 0; i < k; i++){if(fast == head)return NULL;fast = fast->next;}//同步移动直到fast回到起点while(fast != head){fast = fast->next;slow = slow->next;}return slow;
}

时间复杂度O(n),空间复杂度O(1)

练习题

【1】（单向链表）

• 题目：建立一个包含若干整数的单向链表，比如: 1,2,3,4,51,2,3,4,5

  通过某些算法将其中各个节点逆转，比如: 5,4,3,2,15,4,3,2,1

• 分析：（约瑟夫环、单向循环链表）主要分析如何将链表倒转

• 代码：

  /#include <stdio.h>
  #include <stdlib.h>#define MAX_LENGHT 20// 链表节点结构体
  typedef struct ListNode 
  {int data;               // 节点数据域struct ListNode *next;  // 指向下一节点的指针
  } Node;//尾插法创建链表
  Node* createList(int arr[], int size) {if (size == 0) return NULL;Node *head = NULL, *tail = NULL;for (int i = 0; i < size; i++) {Node *newNode = (Node*)malloc(sizeof(Node));newNode->data = arr[i];newNode->next = NULL;if (head == NULL) {  // 链表为空时初始化头尾指针head = tail = newNode;} else {             // 尾插法维护尾指针tail->next = newNode;tail = newNode;}}return head;
  }//迭代反转法（三指针法）
  Node* reverseByIteration(Node *head) {Node *prev = NULL, *current = head, *next = NULL;while (current) {next = current->next;  // 保存下一节点指针current->next = prev;  // 反转指针方向prev = current;        // 前驱指针后移current = next;        // 当前指针后移}return prev;  // 新头节点是原链表尾节点
  }//头插法反转
  Node* reverseByHeadInsert(Node *head) {Node *newHead = NULL, *current = head;while (current) {Node *next = current->next;   // 保存下一节点current->next = newHead;      // 头插操作newHead = current;            // 更新新头节点current = next;               // 移动当前指针}return newHead;
  }//递归反转法
  Node* reverseByRecursion(Node *current, Node *prev) {if (!current) return prev;        // 递归终止条件Node *next = current->next;       // 保存下一节点current->next = prev;             // 反转指针方向return reverseByRecursion(next, current); // 递归调用
  }//打印链表
  void printList(Node *head) {Node *current = head;while (current) {printf("%d\t", current->data);current = current->next;}printf("\n");
  }//释放内存
  void freeList(Node *head) {Node *current = head;while (current) {Node *temp = current;current = current->next;free(temp);}
  }int main(int argc,char *argv[])
  {//动态分配数组int *arr = (int*)malloc(MAX_LENGHT * sizeof(int));int n;printf("Please enter the number of digits you want to reverse:>");scanf("%d", &n);printf("Please enter %d numbers:>\n", n);for(int i = 0; i < n; i++){scanf("%d", &arr[i]);}// 创建原始链表Node *original = createList(arr, n);printf("原链表: ");printList(original);// 迭代反转测试Node *reversed1 = reverseByIteration(original);printf("迭代反转: ");printList(reversed1);// 头插法反转测试Node *reversed2 = reverseByHeadInsert(reversed1);printf("头插法反转: ");printList(reversed2);// 递归反转测试Node *reversed3 = reverseByRecursion(reversed2, NULL);printf("递归反转: ");printList(reversed3);freeList(reversed3);return 0;
  }
  

【2】约瑟夫环问题

• 题目：罗马人占领乔塔帕特后，犹太人与 Josephus 及他的朋友躲到一个洞中，族人决定宁愿死 也不要被敌人找到，于是决定了一个自杀方式，所有人排成一个圆圈，由第 1 个人开始报数， 每报数到第 3 人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

  然而Josephus和他的朋友并不想死，Josephus要他的朋友先假装遵从，他将朋友与自己安排在两个 特殊的位置，于是逃过了这场死亡游戏。

现在假设有n个人形成一个单向循环链表，求最后剩余的两个节点。

• 解析：主要是分析有头结点和没有头结点，对本题的影响。一般情况下链表带头结点是比较方便的，但是 对于本题，约瑟夫环问题，带上头结点的链表反而不利于操作，画图讲解。

• 约瑟夫环问题（Josephus Problem）是一个精度的数学与数据结构问题，其核心在于通过特定规则在循环队列中淘汰元素（删除元素），最终找到幸存者的位置

  • 基本设定：

    1. n个人围成一个环形队列，编号通常为1到n（或0到n-1）

    2. 从第一个人开始报数，每次数到m（或动态变化的密码值）时，该人出列

    3. 从出列者的下一位重新开始报数，每次数到m（或动态变化的密码值）时，该人出列

    4. 目标：确定幸存者的初始编号

  • 使用循环链表模拟环形队列，每次遍历到第m个节点时删除该节点

• 代码：

  //yuesefu.h#ifndef _YUESEFU_H
  #define _YUESEFU_H#include <stdio.h>
  #include <stdlib.h>
  #include <string.h>//创建节点结构体
  typedef struct node
  {int number;     //人员编号（1~n）struct node *next;     //指针域
  }NODE;//创建无头循环链表
  NODE *createCircle(int n);//约瑟夫环淘汰逻辑
  void joseph(NODE **head, int m);#endif //_YUESEFU_H
  

  //yuesefu.c#include "yuesefu.h"//创建无头循环链表
  NODE *createCircle(int n)
  {//定义头指针和前驱节点指针（初始化为空）NODE *head = NULL, *prev = NULL;//循环创建n个节点，人员编号从1开始递增for(int i = 1; i <= n; i++){//创建新节点NODE *new_node = (NODE*)malloc(sizeof(NODE));//检查节点是否创建成功if(!new_node)return NULL;//设置节点编号new_node->number = i;//如果链表为空则将新节点设为头节点if(!head){//头指针执行新节点head = new_node;//头指针指向自身，形成单个节点的循环结构head->next = head;}//非空链表（尾插法插入元素）else{//将新节点插入到prev节点之后prev->next = new_node;     //前驱节点连接新节点new_node->next = head;     //新节点指向头节点形成闭环}//更新前驱节点为当前新节点prev = new_node;}return head;
  }//约瑟夫环淘汰逻辑
  void joseph(NODE **head, int m)
  {//指针尾随法寻找待删除节点NODE *p = *head, *q = NULL;//当剩余节点数>2时循环while(p->next->next != p){//移动m-1次寻找待删除节点for(int i = 1; i < m; i++){q = p;p = p->next;}//删除当前节点q->next = p->next;     //跳过当前节点printf("处死：%d\n", p->number);//释放被淘汰节点的内存free(p);//从下一节点继续p = q->next;}//输出最后两个幸存者printf("幸存者1：%d\t幸存者2：%d\n", p->number, p->next->number);
  }

  //app.c#include "yuesefu.h"int main()
  {//经典的约瑟夫问题参数int n = 41, m = 3;NODE *p = createCircle(n);joseph(&p, m);//释放最后两个节点free(p->next);free(p);return 0;
  }