深圳积分商城网站建设网页设置快捷键

约瑟夫问题描述：

       编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。下一个人继续从 1 开始报数。n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

约瑟夫问题例子：

       开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开 1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开 1，3，5，从5开始报数，5->1，1->2编号为1的人离开 3，5，从3开始报数，3->1，5->2编号为5的人离开 最后留下人的编号是3。

#include <iostream>using namespace std; typedef struct ListNode
{int value;ListNode* next;ListNode(int val, ListNode* node) : value(val), next(node) {}
}ListNode;ListNode* createList(int nodeNum)
{ListNode* pHead = nullptr;ListNode* pNew = nullptr;for (int i = nodeNum; i > 0; i--){pNew = new ListNode(i, pHead);pHead = pNew;}return pHead;
}ListNode* createCycleList(int nodeNum)
{ListNode* pHead = nullptr;ListNode* pNew = nullptr;ListNode* pTail = nullptr; for (int i = nodeNum; i > 0; i--){	pNew = new ListNode(i, pHead);pHead = pNew;if (i == nodeNum){pTail = pNew;}}pTail->next = pHead;return pHead;
}ListNode* createList(int arr[], int arrLen)
{ListNode* pHead = nullptr;ListNode* pNew = nullptr;for (int i = arrLen - 1; i >= 0; i--){pNew = new ListNode(arr[i], pHead);pHead = pNew;}return pHead;
}void printList(ListNode* pNode)
{while (pNode){std::cout << pNode->value << " ";pNode = pNode->next;}std::cout << std::endl;}ListNode* SloveJosephProblem(ListNode* pHead, int m)
{if (m < 0){return nullptr;}if (!pHead || !pHead->next)return pHead;int inc = 1;//环形链表的判断while (pHead != pHead->next){if (inc == m - 1 ){std::cout << "leaver: " << pHead->next->value << std::endl;pHead->next = pHead->next->next;inc = 1;}else{inc++;}pHead = pHead->next;}pHead->next = nullptr;return pHead;
}int main()
{ListNode* pHead = createCycleList(5);//printList(pHead);ListNode* pLast = SloveJosephProblem(pHead, 2);printList(pLast);return 0;
}