简而言之
首先初始化环形单向链表并且定义两个指针一个指向链表的首结点一个指向链表的尾结点
然后确定第一个开始数数的人的位置(本题以M=2为例)
找到数到K的人(本题K=5)
杀掉数到K的人
接下里依次循环上述步骤
public class PersonNode {
//人的编号
private int no;
//指向下一个结点
private PersonNode next;
//构造方法
public PersonNode(int no) {
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public PersonNode getNext() {
return next;
}
public void setNext(PersonNode next) {
this.next = next;
}
@Override
public String toString() {
return "PersonNode{" +"no=" + no +'}';
}
}
public class PersonCircleLinkList {
//初始化首结点
private PersonNode first = new PersonNode(-1);
/** * 初始化单向循环链表 * @num 初始化环形链表的长度 */
public void init(int num){
if (num<1){
//链表长度小于1没有意义
System.out.println("结点的数量不能小于1");
return;
}
PersonNode temp = first;
for (int i = 1; i <=num ; i++) {
if(i == 1){
//如果只有一个结点就让首结点的next指向自己
temp.setNo(1);
temp.setNext(first);
}else{
//当环形链表长度大于2时每次循环都会创建一个结点加在链表的尾部
//再让尾部结点的next指向首结点
PersonNode personNode = new PersonNode(i);
temp.setNext(personNode);
personNode.setNext(first);
temp=temp.getNext();
}
}
}
/** * 遍历链表 */
public void show(){
if (first.getNext() == null){
System.out.println("当前链表为空");
return;
}
PersonNode temp = first;
while(true){
System.out.println(temp);
if (temp.getNext() == first){
//遍历到链表的最后一个结点
return;
}
temp = temp.getNext();
}
}
/** * * @param start 开始数数的人 * @param num 每次数几个数 * @param count 一共几个人参与 */
public void killPerson(int start,int num,int count){
init(count);
if(first == null||start<0||num<0||start>count){
System.out.println("参数不正确");
}
PersonNode last = first;
while(true){
if (last.getNext() == first) {
//last指向环形链表中的最后一个元素
break;
}
last = last.getNext();
}
//确定开始报数的位置
for (int i = 0; i < start-1 ; i++) {
first = first.getNext();
last = last.getNext();
}
while(true){
if (last == first){
//只有一个结点就结束循环(剩下最后一个人)
break;
}
//开始数数 for循环结束first指向数到K的人
for (int i = 0; i < num - 1; i++) {
first = first.getNext();
last = last.getNext();
}
System.out.println(first.getNo()+"号kill");
first=first.getNext();
last.setNext(first);
}
//最后一个存活下来的人
System.out.println(first.getNo()+"号存活");
}
}
public class PersonCircleTest {
public static void main(String[] args) {
PersonCircleLinkList linkList = new PersonCircleLinkList();
linkList.killPerson(2,5,6);
}
}
输出结果
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/m0_60117382/article/details/121887816
内容来源于网络,如有侵权,请联系作者删除!