循环链表介绍
先不急着看约瑟夫问题是什么，先了解循环链表的结构，那什么是循环链表？
循环，顾名思义，从链表中第一个节点出发，还会遇到第一个节点，形成循环的一环。也就是说链表中最后一个节点的下一个节点是第一个节点，但是头节点也是一个节点，所以最后一个节点的下一个节点应该是头节点才对。
如下图，有两种情况：
其中更大的长方形是节点的数据域，更小的长方形是节点的指针域，指向链表中的下一个节点。
循环链表的代码实现
因为解决约瑟夫问题，只需要初始化、插入、打印功能，所以别的功能就没实现。
节点定义
首先，循环链表和普通链表节点的结构体定义一模一样，那就写出来吧。
typedef struct _LoopLinkList //循环链表
{
int date;
struct _LoopLinkList* next;
}LinkNode,LinkList;循环链表的初始化
初始化循环链表，其中函数的参数是一个指向头节点的指针，如图所示：
两个箭头有些重叠了，不过无伤大雅。
函数参数中的取地址符 & 是引用的意思，为C++特有的，相当于就在使用这个一级指针 L ，无需使用二级指针来接收这个一级指针 L 的地址，如果去掉这个 & ，会发生什么事呢？那就是 L 这个指针所指向的地址无法改变，但是可以改变所指向的变量的值。
bool initLinkList(LinkList *&L)
{
L = new LinkNode; //为头结点申请空间
if (!L) return false; // L为空指针,生成头结点失败
L->next = L; //头结点指向自己
L->date = -1;
return true;
}如果上面那段话不太明白，可以先跳过，等写完所有代码，然后把初始化函数参数中的 & 去掉，在 IDE 中调试一下即可得出答案。
循环链表的插入（尾插法）
其中函数的参数节点指针 node 指向新加节点。
bool InsertBack(LinkList* &L, LinkNode* node)
{
if (!L || !node) return false; //如果链表头结点未创建或者传入的结点指针指向空
//分两种情况,一是链表为空,只有头结点存在
if (L->next == L)
{
node->next = L;
L->next = node;
}
else
{
LinkNode* p = L;
while (p->next != L)
{
p = p->next;
} //找到最后一个节点
p->next = node;
node->next = L;
}
return true;
}循环链表的打印
从头节点开始打印，直到又为头节点。
bool LinkPrint(LinkList* L)
{
if (!L) return false;
LinkNode* p = L;
p = L ->next;
while (p != L)
{
printf("%d ", p->date);
p = p->next;
}
return true;
}
约瑟夫问题
解决了循环链表，就开始约瑟夫问题了，哈哈，这故事有很多的分支，我之前听过的不是下面这种。
据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
——摘自约瑟夫问题_百度百科
不过看完这个故事应该大概了解了约瑟夫问题，这个问题可以用循环链表解决，每一个人都是链表中一个节点，只要某个节点报数报到出圈的那个号码，就把这个节点从链表中删除。
由于原问题的人数实在太多，我这里就简化一下，一共 10 人，报数报到 9 的人出圈，并且要求求出第五轮出圈的号码，还有最后一个出圈的人的号码，所以添加了两个整型变量 loops、num来记录。
首先在进入这个函数之前已经把 10 个节点插入了链表，第 n 个节点的值为 n ，例如：第一个节点的数据域为 1 。
代码实现
其中函数参数 interval 为间隔，也就是出圈的号码 9 。
bool Joseph(LinkList* &L,int interval)
{
if ( !L || L->next == L) return false; // 头节点未初始化或者是空链表
if (interval < 1) return false; //报数的间隔也不能小于 1 ， 1 的话还能玩，也就是一报数就死
LinkNode* p = L , *q = NULL ; // q 指向要删除的节点， p 指向要删除的节点的前一个节点
int loops = 0 , num = 0 ; //loops表示进行到第几轮，num保存着出圈的人的号码
int j = 1;
while (L->next != L) //不为空链表
{
while ( j < interval ) //一直报数，除非j等于出圈的数-1，这时候指针p就指向了要删除的节点的前一个节点
{
if (p->next != L)
{
j++;
}
p = p->next;
}
if (p->next == L) //如果p指向最后一个节点，那肯定不能删除头节点，应该删除第一个节点，所以p赋值为头节点
{
p = L;
}
//删除
q = p->next;
num = q->date;
p->next = q->next;
delete q;
j = 1;
loops++;
cout <<endl<< "这是第"<<loops<<"轮:" ;
LinkPrint(L);
if (loops == 5)
{
printf("\n第5轮出圈的是:%d", num);
}
}
printf("最后一个出圈的是:%d\n", num);
return true;
}可能有人会想为什么其中循环的条件不是 i <= j 呢？因为在单向链表中，你删除一个节点前，必须要让删除节点的上一个节点的next 指针指向删除节点的下一个节点。
所以指向要删除的节点的上一个节点就方便很多了
如下图：
完整代码以及运行结果
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
//结点结构体
typedef struct _LoopLinkList
{
int date;
struct _LoopLinkList* next;
}LinkNode,LinkList;
//初始化
bool initLinkList(LinkList* &L)
{
L = new LinkNode;
if (!L) return false;
L->next = L; //指向自己
L->date = -1;
return true;
}
//尾插法
bool InsertBack(LinkList* L, LinkNode* node)
{
if (!L || !node) return false;
if (L->next == L) //链表为空,只有头结点
{
node->next = L;
L->next = node;
}
else
{
LinkNode* p = L;
while (p->next != L)
{
p = p->next;
}
p->next = node;
node->next = L;
}
return true;
}
//打印
bool LinkPrint(LinkList* L)
{
if (!L) return false;
LinkNode* p = L;
p = L ->next;
while (p != L)
{
printf("%d ", p->date);
p = p->next;
}
return true;
}
//解决joseph问题
bool Joseph(LinkList*& L, int interval)
{
if (!L || L->next == L) return false; // 头节点未初始化或者为空链表
if (interval < 1) return false; //报数的间隔
LinkNode* p = L, * q = NULL;
int loops = 0, num = 0; //loops表示进行到第几轮，num保存着最后一个出圈的人的号码
int j = 1;
while (L->next != L)
{
while (j < interval)
{
if (p->next != L)
{
j++;
}
p = p->next;
}
if (p->next == L)
{
p = L;
}
//此时 p 指向要删除节点的前一个节点（不为最后一个节点）
q = p->next;
num = q->date;
p->next = q->next;
delete q;
j = 1;
loops++;
cout << endl << "这是第" << loops << "轮:";
LinkPrint(L);
if (loops == 5)
{
printf("\n第5轮出圈的是:%d", num);
}
}
printf("最后一个出圈的是:%d\n", num);
return true;
}
int main(void)
{
LinkList* L = NULL ;
LinkNode* e = NULL;
//1.初始化循环链表
initLinkList(L);
//2.尾插循环链表
for (int i = 1; i <= 10; i++)
{
e = new LinkNode;
e->date = i;
e->next = NULL;
InsertBack(L, e);
}
//3.打印链表
LinkPrint(L);
Joseph(L, 9);
return 0;
}---------------------------------------------------------------------------------------------------------------------------------
