Lazy loaded image
C++
单链表实现约瑟夫环问题
Words 559Read Time≈ 2 min
2022-9-2
2024-7-5
type
status
date
slug
summary
tags
category
icon
password
经典的约瑟夫环问题，用单链表实现竟然这么简单！？

问题

使用单链表实现约瑟夫环(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时找到要出局的节点，我们就可以删除它，循环往复直到只有一个节点。
跳出循环后记得将此节点的指针域赋空，返回即可。

代码

 
💡
以上就是用单链表实现约瑟夫环问题的全部过程啦，是不是肥常简单！
上一篇
寻路：使用队列广度优先找到出口及最优路径
下一篇
C++中的深拷贝和浅拷贝
Comments
Loading...
Catalog