//利用链表模拟约瑟夫环,来求解该问题;
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;
}}

京公网安备 11010502036488号