当前位置: 代码迷 >> 综合 >> 第二章 链表问题(环形单链表的约瑟夫问题)
  详细解决方案

第二章 链表问题(环形单链表的约瑟夫问题)

热度:57   发布时间:2023-10-11 12:20:54.0

【题目】

  据说著名犹太历史学家Josephus有过如下故事:在罗马人占领乔塔帕特后,39个犹太人和Josephus及他的朋友躲进一个洞里,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第一个人开始报数,报数到3的人就自杀,再由下一个人重新报1,报数到3的人就自杀,这样依次下去,知道剩下最后一个人时,那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向链表描述该结构并呈现整个自杀过程。
  
输入:一个环形单向链表的头节点head和报数的值m
返回:最后生存下来的节点,且这个节点自己组成环形单向链表,其他节点都删掉。

    Node<Integer> josephKill(Node<Integer> head, int num) {// 找到尾节点Node<Integer> last = head;while (last.next != head) {last = last.next;}int count = 0;while (last != head) {// 头节点和尾节点随着数数,不断的向前移动if (++count == num) {System.out.println("移除:" + head.value);last.next = head.next; //移除头节点count = 0;} else {last = last.next;}head = head.next;}return head;}

  相关解决方案