约瑟环求解问题

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

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

}

全部评论

相关推荐

SinyWu:七院电话面的时候问我有没有女朋友,一听异地说你赶紧分。我:???
点赞 评论 收藏
分享
10-07 20:48
门头沟学院 Java
听说改名就会有offer:可能是实习上着班想到后面还要回学校给导师做牛马,看着身边都是21-25的年纪,突然emo了了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务