环形单链表的约瑟夫问题

文章目录

输入：一个环形单链表的头结点head和报数的值m。
返回：最后生存下来的节点，且这个节点自己组成环形单向链表，其他节点都删掉。
进阶：如果链表节点数为N，想在时间复杂度O(N)时完成原问题的要求，该如何实现？

public class JosephusKill1 {
	public class Node{
		public int value;
		public Node next;
		public Node(int data){
			this.value=data;
		}
	}
public Node josephusKill1(Node head,int m){
	if(head==null||head.next==head||m<1){
		return head;
	}
	Node last=head;
	while(last.next!=head){
		last=last.next;
	}
	int count=0;
	while(head!=last){
		if(++count==m){
			last.next=head.next;
			count=0;
		}else{
			last=last.next;
		}
		head=last.next;
	}
	return head;
}
public Node josephusKill2(Node head,int m){
	if(head==null||head.next==head||m<1){
		return head;
	}
	Node cur=head.next;
	int tmp=1;//tmp指向list size
	while(cur!=head){
		tmp++;
		cur=cur.next;
	}
	tmp=getLive(tmp,m);//tmp指向service node position
	while(--tmp!=0){
		head=head.next;
	}
	head.next=head;
	return head;
}
public int getLive(int i,int m){
	if(i==1){
		return 1;
	}
	return (getLive(i-1,m)+m-1)%i+1;
}
}