约瑟环求解问题
孩子们的游戏(圆圈中最后剩下的数)
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; }
}