循环链表的基本操作

什么是单循环链表？

在单链表中，终端结点的指针域NULL指向表头结点或开始结点
图示：
在循环链表中依旧存在头指针和首元节点，循环链表和普通链表相比，唯一的不同就是循环链表首尾相连，其他都完全一样。

单循环链表的基本操作：

单循环链表的一些操作与单向链表的一些操作思路类似，详情请看 单链表的就基本操作 在这里不过多介绍，就讲讲单循环链表的创建，相邻节点交换以及遍历。

准备工作

    #include<stdio.h>             
    #include<stdlib.h>
    #define N 5  
    typedef struct node{
        int data;
        struct node* next;
    }node,* List;
    List L2;

创建单循环链表

    List CreateCirculList(List L2)      //创建单向循环链表并写入N个值 
    {
        int i;
        node* tail;
        
        L2=(List)malloc(sizeof(node));
        L2->next=L2;                                      
        tail=L2;
        printf("Enter %d elements for your circul list:\n",N);
        scanf("%d",&L2->data);
        for(i=1;i<N;i++)
        {
            node *p=(node*)malloc(sizeof(node));
            scanf("%d",&p->data); 
            tail->next=p;                  //tail->next指向最新结点 
            p->next=L2;                    //最新结点的next指向链表头，整个链表完成循环 
            tail=p;
        }
        
        return L2; 
    }

将单循环链表相邻的两个结点交换

        void ExchangeNodeOfCirculList(List L2)       // 将循环链表中的某个结点与其下一个结点交换 
    {
        node *p,*q;
        p=L2->next;                              //p是L2的后继结点
        q=p->next;                               //q是p的后继结点，要将结点p和结点q交换 
        
        L2->next=q;
        p->next=q->next;
        q->next=p;  
    }

单循环链表的遍历(单链表也可以用)

        void PrintList(List L)           //打印链表 
    {
        int i;
        node *p=L->next,*q=L;
        while(p)        
        {
            printf("%d ",p->data);
            p=p->next;
            if(p==L->next)           //如果是遍历循环链表，p往后遍历到表头处结束 
            {
                break;
            }
        }
        printf("\n");
    }

一个有趣的实例：约瑟夫环(也叫丢手绢问题)

题意：

已知 n 个人（分别用编号 1，2，3，…，n 表示）沿顺时针围坐在一张圆桌周围，从编号为 k 的人开始从1顺时针报数，数到 m 的那个人出列，他的下一个人又从 1 开始沿顺时针报数，数到 m 的那个人又出列，依次重复下去，直到圆桌上剩余一个人，输出最后一个人的编号。
约瑟夫环问题是一个经典的循环链表例题，当然用其他方法也可以实现，这里只讲用循环链表怎么实现。

代码如下：

首先创建一个循环链表来存放编号，详情请见上文 创建单循环链表

int JosephCircle(List L2)   //返回最后剩下人的编号 
{
    int i,k,m;
    L2=CreateCirculList(L2);  //创建一个循环链表来存放编号
    node *p=L2,*q;            //p最终指向每一轮报数m的人，q指向p的前一个结点 
    
    printf("Enter the beginer's number k and end-counting number m:\n"); 
    scanf("%d%d",&k,&m);       //输入k和m
    
    while(p->data!=k)
    {
        p=p->next;
    }
    while(p->next!=p)      //当循环链表中只有一个结点即只剩下一个人时结束循环 
    {
        for(i=1;i<m;i++)
        {
            q=p;       //p指向每一轮报数的人，q指向p的前一个结点
            p=p->next;
        }
        q->next=p->next;
        free(p);     //删去报数m的人
        p=q->next;   //下一轮报数从报数m的下一个人即q->next开始 
    }
    
    return (p->data);  //返回最后一个人的编号 
}

main 函数根据需求写，程序运行结果无误。