【说明】：
本文是左程云老师所著的《程序员面试代码指南》第二章中“环形单链表的约瑟夫问题”这一题目的C++复现。
本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。
感谢左程云老师的支持。
【题目】：
据说著名的犹太历史学家Josephus有过以下故事：在罗马人占领桥塔帕特后，39个犹太人与Josephus 及他的朋友躲到一个洞中，39个犹太人宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第一个人开始报数，报数到3的人就自杀，然后再有下一个人重新报1，报数到3的人再自杀。这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表描述该结构并呈现整个自杀过程。
输入：一个环形单向链表的头节点head 和报数的值m。
返回：最后生存下来的节点，且这个节点自己组成环形单向链表，其他节点都删掉。
【进阶】：
如果链表的节点数为N，想在时间复杂度为O(N)时内完成原问题的要求，该怎么实现？
【思路】：
- 对于普通解法：遍历链表，不停转圈；
- 对于进阶解法：已知条件为链表长度n、报数值m、最后剩得1个节点。那么可以寻找杀死一个节点前这个链表的各个节点的编号与杀死一个节点后整个链表的各个节点的编号之间的关系。图（表）示说明如下：
| 初始编号 | 一次后编号 | 二次后编号 | 三次后编号 | 四次后编号 |
| 1 | 3 | --- | --- | --- |
| 2 | 4 | 1 | 1 | --- |
| 3 | --- | --- | --- | --- |
| 4 | 1 | 2 | 2 | 1 |
| 5 | 2 | 3 | --- | --- |
其中：---表示已被删除。
由此表可知，最后（四次后）剩下的节点编号为1，那么这个节点在三次后中的编号为2，二次后中的编号为2，一次后中的编号为1，初始编号为4。
倒推过程如下： 1-->2-->2-->1-->4
那么最后剩下的节点即为初始编号为4的节点。
有公式如下：old = (new + m - 1) % n + 1
其中：new 为本次中的节点编号；
m 为报数值；
n 为本次中未被删除的节点的数量（初始为5，一次后为4、二次后为3、三次后为2）；
old为上一次本节点的序号。
【编译环境】：
CentOS6.7（x86_64）
gcc 4.4.7
【实现】：
实现及测试代码：
1 /* 2 *文件名：josephusKill.cpp 3 *作者： 4 *摘要：约瑟夫环问题 5 */ 6 7 #include <iostream> 8 9 using namespace std; 10 11 struct Node 12 { 13 int value; 14 Node *next; 15 }; 16 17 Node* josephusKill1(Node *head,int m) 18 { 19 if(NULL == head || head->next == head || m < 1) 20 return head; 21 Node *last = head; 22 while(last->next != head) //找到最后一个节点（head的前一个节点） 23 last = last->next; 24 int count = 0; 25 cout << " Kill order is :"; 26 while(head != last) 27 { 28 if(++count == m) //++置于前的目的是找到待删除节点的前一个节点 29 { 30 Node *ptr = last->next; 31 last->next = head->next; //再次构成环 32 count = 0; 33 cout << ptr->value << "->" ; 34 delete ptr; 35 } 36 else 37 { 38 last = last->next; 39 } 40 head = head->next; //head与last要保持同时向后移动 41 } 42 cout << endl; 43 return head; 44 } 45 46 //进阶解法 47 int getLive(int n,int m) //找到幸存节点的初始编号 48 { 49 if(1==n) 50 return 1; 51 return (getLive(n-1,m) + m -1) % n +1; 52 } 53 54 Node* josephusKill2(Node *head,int m) 55 { 56 if(NULL == head || head->next == head || m < 1) 57 return head; 58 Node *cur = head->next; 59 int count = 1; 60 while(cur != head) 61 { 62 count++; 63 cur = cur->next; 64 } 65 int live = getLive(count,m); 66 Node *dst = NULL; 67 for(int i=1;i<=count;i++) 68 { 69 if(i == live) 70 { 71 dst = head; 72 head = head->next; 73 continue; 74 } 75 Node *tmp = head; 76 head = head->next; 77 delete tmp; 78 } 79 return dst; 80 } 81 82 int main() 83 { 84 Node *head1 = NULL; 85 Node *head2 = NULL; 86 Node *ptr = NULL; 87 88 for(int i =1;i<6;i++)//构造链表 89 { 90 if(NULL == head1) 91 { 92 head1 = new Node; 93 head1->value = i; 94 head1->next = NULL; 95 ptr = head1; 96 continue; 97 } 98 ptr->next = new Node; 99 ptr = ptr->next; 100 ptr->value = i; 101 ptr->next = NULL; 102 } 103 ptr->next = head1; //构造环形链表 104 Node* dst; 105 dst = josephusKill1(head1,3); 106 cout << "survival Node is: " << dst->value << endl; 107 108 for(int i =1;i<6;i++)//构造链表 109 { 110 if(NULL == head2) 111 { 112 head2 = new Node; 113 head2->value = i; 114 head2->next = NULL; 115 ptr = head2; 116 continue; 117 } 118 ptr->next = new Node; 119 ptr = ptr->next; 120 ptr->value = i; 121 ptr->next = NULL; 122 } 123 ptr->next = head2; //构造环形链表 124 dst = josephusKill2(head2,3); 125 cout << "survival Node is: " << dst->value << endl; 126 return 0; 127 }
注：
转载请注明出处；
转载请注明源思路来自于左程云老师的《程序员代码面试指南》。