淘先锋技术网

首页 1 2 3 4 5 6 7

经典的约瑟夫环问题,用单链表实现竟然这么简单!?

目录

前言

问题

思路

代码


前言

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

问题

        使用单链表实现约瑟夫环(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;
}


总结

       以上就是用单链表实现约瑟夫环问题的全部过程啦,是不是肥常简单!