约瑟夫环问题可以简单的使用数组的方式实现，但是现在我使用循环链表的方法来实现，因为上午看到一道面试题规定使用循环链表解决约瑟夫环问题。
什么是约瑟夫环？
“约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。”（百度百科中的解决办法列出了很多，可以看到循环链表并不是最简单的方法）
这道面试题考察了循环链表的“创建”，“遍历”和“删除”。
创建的循环链表的结构图：
解决约瑟夫环问题的过程
C++实现代码如下：
循环链表解决约瑟夫问题
1 /**循环链表解决约瑟夫环问题
2 * 问题：约瑟夫环
3 * 有编号从1到N的N个人坐成一圈报数，从第K个人开始报数，报到M的人出局，
4 * 下一位再从1开始报数，如此持续，直止剩下一位为止，报告此人的编号X。
5 * 输入N,K,M，求出X。
6 */
7
8 #include <iostream>
9 using namespace std;
10
11 struct MyNode
12 {
13 MyNode(int a_data):m_data(a_data),m_pNext(NULL) {}
14
15 int m_data;
16 MyNode *m_pNext;
17 };
18
19 class Josephus
20 {
21 public:
22 Josephus(int a_N, int a_K, int a_M):m_N(a_N),m_K(a_K),m_M(a_M)
23 {
24 createList();
25 outputList();
26 }
27
28 protected:
29 void createList();
30 void outputList();
31
32 private:
33 MyNode *m_pHead;//循环链表的头节点
34 int m_N; //链表节点个数
35 int m_K; //第一个报数人的序号
36 int m_M; //报数出局的数
37 };
38
39 void Josephus::createList()
40 {
41 MyNode *pre = NULL;
42 MyNode *cur = NULL;
43 MyNode *p = new MyNode(1);
44 m_pHead = p;
45 cur = p;
46 for (int i=2; i<=m_N; i++)
47 {
48 p = new MyNode(i);
49 pre = cur;
50 cur = p;
51 pre->m_pNext = cur;
52 }
53 cur->m_pNext = m_pHead;
54
55 int n=m_N;
56 p = m_pHead;
57 while (n--)
58 {
59 cout << p->m_data << ",";
60 p = p->m_pNext;
61 }
62 cout << endl;
63 }
64
65 void Josephus::outputList()
66 {
67 MyNode *pre = NULL;
68 MyNode *cur = m_pHead;
69 m_K--;
70 while (m_K--) //寻找第K个人（开始报数的人）
71 {
72 pre = cur;
73 cur = cur->m_pNext;
74 }
75 while (m_N--) //输出链表中所有的节点值
76 {
77 int s = m_M-1;
78 while (s--) //寻找间隔M的人
79 {
80 pre = cur;
81 cur = cur->m_pNext;
82 }
83 MyNode *p = cur;
84 cout << p->m_data << ",";
85 cur = cur->m_pNext; //删除节点的过程
86 pre->m_pNext = cur;
87 delete p;
88 p=NULL;
89 }
90 }
91
92 int main()
93 {
94 Josephus josephus(100,5,5);
95 return 0;
96 }
测试结果：
