约瑟环求解问题

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

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;
}

}

全部评论

相关推荐

07-02 13:50
闽江学院 Java
点赞 评论 收藏
分享
半解316:内容充实,细节需要修改一下。 1,整体压缩为一页。所有内容顶格。 2,项目描述删除,直接写个人工作量 修改完之后还需要建议,可以私聊
点赞 评论 收藏
分享
Yki_:你要算时间成本呀,研究生两三年,博士三四年,加起来就五六年了,如果你本科去腾讯干五年,多领五年的年薪,加上公司内涨薪,可能到时候十五年总薪资也跟博士差不多
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务