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;
}