丢手绢的算法问题之单链表 - 黑马程序员技术交流社区

package com.soke.demo5;
/*
* 功能：解决丢手绢问题，采用不带头结点的链表来解决
*/
public class PlayHandkerchief {
public static void main(String []args){
CycleLinkList c1 = new CycleLinkList();
c1.setLen(10);
c1.setK(2);
c1.setM(2);
c1.createLinkList();
c1.show();
c1.play();
}
}
//创建一个结点类
class Child{
int no; //结点数据域上的数
Child nextChild=null; //当前结点的下一个结点
public Child(int no){
this.no=no;//初始化给它一个值
}
}
//创建一个单链表类
class CycleLinkList{
Child firstChild=null;//定义一个头结点
Child temp=null;//定义一个跑龙套的结点
int length=0;//单链表的长度,也即是丢手绢问题中人的个数
int k = 0;//从第k个人开始的
int m = 0;//数到第m下，踢走这个人
//设置单链表的大小
public void setLen(int length){
this.length=length;
}
public void setK(int k){
this.k=k;
}
public void setM(int m){
this.m=m;
}
//初始化环形链表
public void createLinkList(){
for(int i=1;i<=length;i++){
if(i==1)
{//创建第一个小孩
Child ch = new Child(i);
this.firstChild = ch;//创建了第一个结点的同时，将头结点指向第一个结点
this.temp = ch;//也将跑龙套的结点指向第一个结点
}else{//继续创建新的结点
if(i==length){ //如果是最后一个结点
Child ch = new Child(i);
this.temp.nextChild = ch;//将上一个结点的next结点指向刚创建的新结点
this.temp = ch;//还是将跑龙套的结点指向刚创建的新结点
temp.nextChild = this.firstChild;//将刚创建的新结点的next指针指向firstChild结点
}else{
Child ch = new Child(i);
this.temp.nextChild = ch;//将上一个结点的next结点指向刚创建的新结点
this.temp = ch; //还是将跑龙套的结点指向刚创建的新结点
}
}
}
}
public void play(){//开始玩游戏的方法
temp = this.firstChild;
//先找到开始数数的那个人
for(int i=1;i<k;i++){
temp = temp.nextChild;
}
while(length!=1){
//数m下
for(int j=1;j<m;j++){
temp = temp.nextChild;
System.out.println("当前出局的小孩是："+temp.no);
}
//如果是单链表的话，问题有点棘手，我怎么要删的结点的上一个结点呢？
//方法就是从要删除的结点开始遍历整个链表，直到找到一个结点它的next结点指向我们删除的结点
Child temp2 = temp;
while(temp2.nextChild!=temp){
temp2 = temp2.nextChild;
}
//将数到m的小孩从链表中删除
temp2.nextChild = temp.nextChild;
//继续要将temp指向下一个结点，不能让链表断了
temp = temp.nextChild;
this.length--;
}
System.out.println("最后出局的小孩是："+temp.no);
}
public void show(){
//定义一个跑龙套的结点
temp = this.firstChild;
do{
System.out.print(" "+temp.no);
temp = temp.nextChild;
}while(temp!=this.firstChild);
System.out.println();
}
}

复制代码