27.环形链表介绍和约瑟夫问题

单向环形链表应用场景：约瑟夫问题

单项环形列表案例：

约瑟夫问题分析：

• 使用单项环形链表完成约瑟夫问题（数组取模也可以完成 ）
• 数到n的节点出列，下一个节点继续报数
• 最后只剩一个节点时依旧是单项环形链表，它的next指向自己，且它会最后一个出列

28.约瑟夫问题分析图解和实现1，构建，添加元素，遍历

• first指针指向第一个节点
  单项环形链表的构建和遍历思路：
  疑问：创建时为什仫需要两个辅助变量：一个curBoy指向当前节点，另一个boy指向要加入链表的节点curBoy.next=boy，boy.next=first，curBoy=boy，

• 创建一个boy类，表示一个节点
• 创建一个环形单向链表class CircleSingleLinkedList，内部添加一个first节点

• 遍历当前环形链表方法
• 判断当前链表是否为空，if（first==null）：first初始值设置为null，链表为空

29.约瑟夫问题分析图解和实现，出列

出列实现难点思考：

• 节点出列后，如何将当前节点的上一个节点与下一个节点相连
• 为了解决上一个问题，如何设置对节点是否出队列的判断，是否需要提前对下一个节点是否出队列进行判断（链表单向，不能往回找）
• 特殊情况：从第一个节点就开始出队列又如何实现，如何将末尾节点node：node.next==first与下一个节点first.next相连

出列实现思路分析：

• 一个辅助节点helper指向链表的最后一个节点，helper.next==first
• 移动时，helper和first同时移动，移动m-1次
• 将当前first指向的节点出列

出列具体实现问题：

• helper怎么实现，需要先遍历一遍链表，取到最后一个节点？
• 出圈前helper和first先移动k-1次，移动到报数小孩的位置（实现了helper后才做）
• 循环出圈，当圈中只剩一个节点时（helper==first）结束循环，最后一个节点也出圈