链表之单链表约瑟夫问题（一）

  

   

    

     

    
    

     

      package com.chenyu.zuo.linkedList;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      import com.chenyu.zuo.linkedList.RemoveMidNode.Node; 
     
    
   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * 环形单链表的约瑟夫问题
     
    
   

    

     

    
    

     

       * 比如5个人，报数第3个就删除，从第一个人开始报数
     
    
   

    

     

    
    

     

       * 1、2、3、4、5
     
    
   

    

     

    
    

     

       * 1、2、4、5
     
    
   

    

     

    
    

     

       * 2、4、5
     
    
   

    

     

    
    

     

       * 2、4
     
    
   

    

     

    
    

     

       * 4
     
    
   

    

     

    
    

     

       * 最后4留下来了
     
    
   

    

     

    
    

     

       * 输入：一个单向环形链表的头节点head和报数的值m
     
    
   

    

     

    
    

     

       * 返回：最后生存下来的节点，且这个节点自己组成环形单向链表，其他节点都删掉
     
    
   

    

     

    
    

     

       * 
     
    
   

    

     

    
    

     

       * 思路：
     
    
   

    

     

    
    

     

       * 1、先把不满足条件的时候返回头节点
     
    
   

    

     

    
    

     

       * 2、得到我们链表的最后一个节点，然后遍历每个节点，不断转圈，不断让每个节点报数。
     
    
   

    

     

    
    

     

       * 3、当报数到达m时，就删除当前报数的节点
     
    
   

    

     

    
    

     

       * 4、删除节点后，别忘了还要把剩下的节点继续连接成环状，继续转圈报数，继续删除。
     
    
   

    

     

    
    

     

       * 5、不停的删除，直到环形链表中只剩下一个节点，过程结束
     
    
   

    

     

    
    

     

       * 只不过我们的时间复杂度是（n*m）,下一篇博客进阶时间复杂度O(N)
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      public class GosephusKill {
     
    
   

    

     

    
    

     

       static class Node{
     
    
   

    

     

    
    

     

       int val;
     
    
   

    

     

    
    

     

       Node next;
     
    
   

    

     

    
    

     

       public Node(int  val){
     
    
   

    

     

    
    

     

       this.val=val;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       public Node kill1(Node head,int m){
     
    
   

    

     

    
    

     

       if(head==null || head.next==head || m<0){
     
    
   

    

     

    
    

     

       return head;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       Node last=head;
     
    
   

    

     

    
    

     

       while(last.next!=head){ /
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/50438014