1. package com.soke.demo6;
   
2. 
   
3. public class PlayHandkerchief {
   
4. 
   
5. /**
   
6. * 功能：解决丢手绢问题，采用不带头结点的双链表来解决
   
7. */
   
8. public static void main(String[] args) {
   
9. DLinkList c1 = new DLinkList();
   
10. c1.setLength(10);
    
11. c1.setK(2);
    
12. c1.setM(2);
    
13. c1.createDLinkList();
    
14. c1.show();
    
15. c1.play();
    
16. 
    
17. }
    
18. }
    
19. //创建一个结点类
    
20. class Child{
    
21. int no;//结点数据域上的数
    
22. Child priorChild;//当前结点的前一个结点
    
23. Child nextChild;//当前结点的下一个结点
    
24. public Child(int no){
    
25. this.no = no;
    
26. }
    
27. }
    
28. //创建一个双链表类
    
29. class DLinkList{
    
30. Child firstChild = null;//定义一个头结点
    
31. Child temp = null;//定义一个跑龙套的结点
    
32. int length = 0 ; //定义双链表的长度
    
33. int k = 0;//从第K个人开始游戏的
    
34. int m = 0;//数到第m个数的人就退出游戏
    
35. public void setLength(int length) {
    
36. this.length = length;
    
37. }
    
38. public void setK(int k) {
    
39. this.k = k;
    
40. }
    
41. public void setM(int m) {
    
42. this.m = m;
    
43. }
    
44. //初始化双链表
    
45. public void createDLinkList(){
    
46. for(int i=1;i<=length;i++){
    
47. if(i==1){//表示创建第一个结点
    
48. Child ch = new Child(i);
    
49. this.firstChild=ch;//创建了第一个结点的同时，将头结点指向第一个结点
    
50. this.temp=ch;//也将跑龙套的结点指向第一个结点
    
51. }else{//继续创建新的结点
    
52. if(i==length){//表示创建的是尾结点
    
53. Child ch = new Child(i);
    
54. temp.nextChild=ch;
    
55. temp.nextChild.priorChild=temp;
    
56. temp=ch;
    
57. temp.nextChild=this.firstChild;
    
58. this.firstChild.priorChild=temp;
    
59. }else{
    
60. Child ch = new Child(i);
    
61. temp.nextChild=ch;
    
62. temp.nextChild.priorChild=temp;
    
63. temp=ch;
    
64. }
    
65. }
    
66. }
    
67. }
    
68. public void play(){//开始玩游戏
    
69. temp = this.firstChild;
    
70. //先找到开始数数的那个人
    
71. for(int i=1;i<k;i++){
    
72. temp=temp.nextChild;
    
73. }
    
74. while(length!=1){
    
75. //数m下
    
76. for(int j=1;j<m;j++){
    
77. temp=temp.nextChild;
    
78. }
    
79. System.out.println("当前出局的小孩是："+temp.no);
    
80. temp.priorChild.nextChild=temp.nextChild;
    
81. temp.nextChild.priorChild=temp.priorChild;
    
82. temp=temp.nextChild;
    
83. this.length--;
    
84. }
    
85. System.out.println("最后出局的小孩是："+temp.no);
    
86. }
    
87. public void show(){
    
88. //定义一个跑龙套的结点
    
89. temp = this.firstChild;
    
90. do{
    
91. System.out.print(" "+temp.no);
    
92. temp = temp.nextChild;
    
93. }while(temp!=this.firstChild);
    
94. System.out.println();
    
95. }
    
96. }

复制代码

附上测试结果：
1 2 3 4 5 6 7 8 9 10
当前出局的小孩是：3
当前出局的小孩是：5
当前出局的小孩是：7
当前出局的小孩是：9
当前出局的小孩是：1
当前出局的小孩是：4
当前出局的小孩是：8
当前出局的小孩是：2
当前出局的小孩是：10
最后出局的小孩是：6

package MyPro;

public class Shoupa
{

        /**
         * @param args
         */
        public static void main(String[] args)
        {
                // TODO Auto-generated method stub
  CycLink cyclink=new CycLink();
  cyclink.setLen(6);
  cyclink.createLink();
  cyclink.setK(4);
  cyclink.setM(3);
  cyclink.show();
  cyclink.play();
        }

}


//孩子节点
class Child
{
        int no;
        Child nextChild=null;
        public Child(int no)
        {
                this.no=no;
        }
}

//环形链表
class CycLink
{
        Child firstChild=null;
        Child temp=null;
        int len=0;
        int k=0;
        int m=0;
       
        //设置链表大小
        public void  setLen(int len)
        {
                this.len=len;
        }
       
        //设置第k人开始数数
        public void setK(int k)
        {
                this.k=k;
        }
       
        //设置数m下
        public void setM(int m)
        {
        this.m=m;
        }
       
        //初始化环形链表
        public void createLink()
        {
                for(int i=1;i<=len;i++)
                {
                        if(i==1)
                        {
                                Child ch=new Child(i);
                                this.firstChild=ch;
                                this.temp=ch;
                        }
                        else
                        {
                                if(i==len)
                                {
                                        Child ch=new Child(i);
                                        temp.nextChild=ch;
                                        temp=ch;
                                        temp.nextChild=this.firstChild;
                                }
                                else
                                {
                                        Child ch=new Child(i);
                                        temp.nextChild=ch;
                                        temp=ch;
                                }
                        }
                }
        }       


//打印该环形链表

        public void show()

        {
        Child temp=this.firstChild;
        System.out.print("当前做游戏的小孩子是：");
        do
        {
                System.out.print(temp.no+"   ");
                temp=temp.nextChild;
        }while(temp!=this.firstChild);
        System.out.println();
    }
       
        //执行游戏
        public void play()
        {
                //招开始数数的人
                Child temp=this.firstChild;
                Child temp2=this.firstChild;//用来找到出圈的前一个小孩
                for(int i=1;i<k;i++)
                {
                        temp=temp.nextChild;
                }
                while(this.len!=1)
                {
                        //数m下
                        for(int j=1;j<m;j++)
                        {  if(j!=m-1)
                           {temp=temp.nextChild;}
                           else
                           {
                            temp2=temp;//出圈的前一个 小孩
                            temp=temp.nextChild;
                           }          
                        }
                        temp2.nextChild=temp.nextChild;//第m个小孩退出圈
                        temp=temp.nextChild;
                        this.len--;
                }
                System.out.println("最后剩下的那个孩子是："+temp.no);
        }
}

韩顺平老师java基础视频里面有，不过不是用的双向链表

孙百鑫 发表于 2013-6-12 11:59
楼主应该写一下需求更好啦就好啦

就是小朋友玩得丢手绢问题，用程序来模拟这个过程

楼主应该写一下需求更好啦就好啦

其实不懂丢手绢游戏是怎么玩的