经典的约瑟夫环问题，用单链表实现竟然这么简单！？

目录

前言

问题

思路

代码

前言

        这两天想到了之前自己用数组实现约瑟夫环问题时写了好多的代码，然后想到数据结构中的但链表好像也可以实现，于是去实践了一下，发现果然可以实现，而且还代码还简洁明了不少。

问题

        使用单链表实现约瑟夫环(JosephCircle)问题。(约瑟夫环：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为1的人开始报数，数到k的那个人出列；他的下一个人又从1开始报数，数到k的那个人又出列；依此规律重复下去，直到圆桌周围的人只剩下一个人。)

//链表节点声明
struct ListNode
{
	int m_nKey;
	ListNode * m_pNext;
};
//题目：使用链表实现约瑟夫环(JosephCircle)问题。
ListNode* JosephCircle(ListNode* pHead, unsigned int k)
{

}

思路

        首先我们需要构建一个环，用一个节点pCur变量遍历到链表的尾节点，然后将pCur的指针域指向头节点，这样我们的环就构建完成了。

        然后我们将头节点赋值给pCur，用pCur节点进行约瑟夫环问题的实现。我们需要使用一个while循环，当pCur的指针域指向的是自己时，说明只剩下了一个人，此时可以跳出循环，否则我们就将k赋值给变量i，i自减一个则pCur偏移到下一节点，当i自减为0时找到要出局的节点，我们就可以删除它，循环往复直到只有一个节点。

        跳出循环后记得将此节点的指针域赋空，返回即可。

代码

ListNode* JosephCircle(ListNode* pHead,unsigned int k)
{
	ListNode* pCur = pHead;                 //构建环
	while (pCur->m_pNext != NULL)
	{
		pCur = pCur->m_pNext;
	}
	pCur->m_pNext = pHead;
	pCur = pHead;
	while (pCur ->m_pNext != pCur) // 只有一个结点时跳出循环
	{
        unsigned int i = k;
		while (--i)
		{
			pCur = pCur ->m_pNext;
		}
		//将后一个结点的数据域和指针域赋值给要删除的结点，删除后一个节点
		ListNode* pDel = pCur ->m_pNext;
		pCur ->m_pNext = pDel ->m_pNext;
		pCur ->m_nKey = pDel->m_nKey;
		delete pDel ;
		pDel = NULL;
	}
	pCur ->m_pNext = NULL;
	return pCur;
}

总结