本文主要是介绍C++ 环形链表(解决约瑟夫问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
约瑟夫问题描述:
编号为 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;
}
这篇关于C++ 环形链表(解决约瑟夫问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!