本文主要是介绍经典面试题之单链表实现约瑟夫环（杀人游戏），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
约瑟夫环运作如下：
1、一群人围在一起坐成 [2] 环状（如：N）
2、从某个编号开始报数（如：K）
3、数到某个数（如：M）的时候，此人出列，下一个人重新报数
4、一直循环，直到所有人出列 [3] ，约瑟夫环结束
下来我们用单链表来实现约瑟夫环：
解决思路: 首先单链表本身不是一个环，所以第一步要构环，第二步实现报数，第三步将报到某个数的节点删除，直到环中剩下一个节点或者没有节点为止，第三步解环。看代码;
//单链表实现约瑟夫环
void Josephcricle(PNode* ppHead, int M){assert(ppHead);if (NULL== *ppHead){return;}circle(*ppHead);//构环PNode pcurnode = *ppHead;while (pcurnode->_pNext != pcurnode){int count = M;while (--count){pcurnode = pcurnode->_pNext;}PNode pdelnode = pcurnode->_pNext;pcurnode->_data = pdelnode->_data;pcurnode->_pNext = pdelnode->_pNext;free(pdelnode);}pcurnode->_pNext = NULL;//解环*ppHead = pcurnode;
}
这篇关于经典面试题之单链表实现约瑟夫环（杀人游戏）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
