约瑟环求解问题

孩子们的游戏(圆圈中最后剩下的数)

http://www.nowcoder.com/questionTerminal/f78a359491e64a50bce2d89cff857eb6

//利用链表模拟约瑟夫环,来求解该问题;
public class Solution {
public int LastRemaining_Solution(int n, int m) {
CircleList cl= new CircleList();
cl.add(n);
int val=cl.method(n,m);
return val;
}
}

class CircleList{
private ListNode first=null;

public void add(int maxSize){
     ListNode curNode=first;
     for(int i=0;i<maxSize;i++){
         ListNode node= new ListNode(i);
         if(i==0){
             first=node;
             node.next=first;
             curNode=first;
         }else{
             curNode.next=node;
             node.next=first;
             curNode=node;
         }
     }
}

public int getLength(){
    ListNode temp=first;
    int len=1;
    while(temp.next!=first){
        len++;
        temp=temp.next;
    }
    return len;
}
public int method(int n,int m){
    if(m<1 || n<1) return -1;
    ListNode helper=first;
   // ListNode temp=first;
    while(helper.next!=first){
        helper=helper.next;
    }

    while(true){
        for(int i=0;i<m-1;i++){
            first=first.next;
            helper=helper.next;
        }                
            first=first.next;
            helper.next=first;

        if(helper==first){
            break;
        }
    }
    return helper.val;
}

}

class ListNode{
public int val;
public ListNode next;

public ListNode(){

}

public ListNode(int val){
    this.val=val;
}

}

全部评论

相关推荐

诨号无敌鸭:恭喜佬,但是有一个小问题:谁问你了?我的意思是,谁在意?我告诉你,根本没人问你,在我们之中0人问了你,我把所有问你的人都请来 party 了,到场人数是0个人,誰问你了?WHO ASKED?谁问汝矣?誰があなたに聞きましたか?누가 물어봤어?我爬上了珠穆朗玛峰也没找到谁问你了,我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒,在找到谁问你之前我连癌症的解药都发明了出来,我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务