1. package com.soke.demo5;
   
2. /*
   
3. * 功能：解决丢手绢问题，采用不带头结点的链表来解决
   
4. */
   
5. public class PlayHandkerchief {
   
6. public static void main(String []args){
   
7. CycleLinkList c1 = new CycleLinkList();
   
8. c1.setLen(10);
   
9. c1.setK(2);
   
10. c1.setM(2);
    
11. c1.createLinkList();
    
12. c1.show();
    
13. c1.play();
    
14. }
    
15. }
    
16. 
    
17. //创建一个结点类
    
18. class Child{
    
19. int no; //结点数据域上的数
    
20. Child nextChild=null; //当前结点的下一个结点
    
21. public Child(int no){
    
22. this.no=no;//初始化给它一个值
    
23. }
    
24. }
    
25. 
    
26. //创建一个单链表类
    
27. class CycleLinkList{
    
28. Child firstChild=null;//定义一个头结点
    
29. Child temp=null;//定义一个跑龙套的结点
    
30. int length=0;//单链表的长度,也即是丢手绢问题中人的个数
    
31. int k = 0;//从第k个人开始的
    
32. int m = 0;//数到第m下，踢走这个人
    
33. //设置单链表的大小
    
34. public void setLen(int length){
    
35. this.length=length;
    
36. }
    
37. public void setK(int k){
    
38. this.k=k;
    
39. }
    
40. public void setM(int m){
    
41. this.m=m;
    
42. }
    
43. //初始化环形链表
    
44. public void createLinkList(){
    
45. for(int i=1;i<=length;i++){
    
46. if(i==1)
    
47. {//创建第一个小孩
    
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. this.temp.nextChild = ch;//将上一个结点的next结点指向刚创建的新结点
    
55. this.temp = ch;//还是将跑龙套的结点指向刚创建的新结点
    
56. temp.nextChild = this.firstChild;//将刚创建的新结点的next指针指向firstChild结点
    
57. }else{
    
58. Child ch = new Child(i);
    
59. this.temp.nextChild = ch;//将上一个结点的next结点指向刚创建的新结点
    
60. this.temp = ch; //还是将跑龙套的结点指向刚创建的新结点
    
61. }
    
62. }
    
63. }
    
64. }
    
65. public void play(){//开始玩游戏的方法
    
66. temp = this.firstChild;
    
67. //先找到开始数数的那个人
    
68. for(int i=1;i<k;i++){
    
69. temp = temp.nextChild;
    
70. }
    
71. while(length!=1){
    
72. //数m下
    
73. for(int j=1;j<m;j++){
    
74. temp = temp.nextChild;
    
75. System.out.println("当前出局的小孩是："+temp.no);
    
76. }
    
77. //如果是单链表的话，问题有点棘手，我怎么要删的结点的上一个结点呢？
    
78. //方法就是从要删除的结点开始遍历整个链表，直到找到一个结点它的next结点指向我们删除的结点
    
79. Child temp2 = temp;
    
80. while(temp2.nextChild!=temp){
    
81. temp2 = temp2.nextChild;
    
82. }
    
83. //将数到m的小孩从链表中删除
    
84. temp2.nextChild = temp.nextChild;
    
85. //继续要将temp指向下一个结点，不能让链表断了
    
86. temp = temp.nextChild;
    
87. this.length--;
    
88. }
    
89. System.out.println("最后出局的小孩是："+temp.no);
    
90. }
    
91. public void show(){
    
92. //定义一个跑龙套的结点
    
93. temp = this.firstChild;
    
94. do{
    
95. System.out.print(" "+temp.no);
    
96. temp = temp.nextChild;
    
97. }while(temp!=this.firstChild);
    
98. System.out.println();
    
99. }
    
100. }

复制代码

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

1. package com.soke.demo5;
   
2. /*
   
3. * 功能：解决丢手绢问题，采用不带头结点的链表来解决
   
4. */
   
5. public class PlayHandkerchief {
   
6. public static void main(String []args){
   
7. CycleLinkList c1 = new CycleLinkList();
   
8. c1.setLen(10);
   
9. c1.setK(2);
   
10. c1.setM(2);
    
11. c1.createLinkList();
    
12. c1.show();
    
13. c1.play();
    
14. }
    
15. }
    
16. 
    
17. //创建一个结点类
    
18. class Child{
    
19. int no; //结点数据域上的数
    
20. Child nextChild=null; //当前结点的下一个结点
    
21. public Child(int no){
    
22. this.no=no;//初始化给它一个值
    
23. }
    
24. }
    
25. 
    
26. //创建一个单链表类
    
27. class CycleLinkList{
    
28. Child firstChild=null;//定义一个头结点
    
29. Child temp=null;//定义一个跑龙套的结点
    
30. int length=0;//单链表的长度,也即是丢手绢问题中人的个数
    
31. int k = 0;//从第k个人开始的
    
32. int m = 0;//数到第m下，踢走这个人
    
33. //设置单链表的大小
    
34. public void setLen(int length){
    
35. this.length=length;
    
36. }
    
37. public void setK(int k){
    
38. this.k=k;
    
39. }
    
40. public void setM(int m){
    
41. this.m=m;
    
42. }
    
43. //初始化环形链表
    
44. public void createLinkList(){
    
45. for(int i=1;i<=length;i++){
    
46. if(i==1)
    
47. {//创建第一个小孩
    
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. this.temp.nextChild = ch;//将上一个结点的next结点指向刚创建的新结点
    
55. this.temp = ch;//还是将跑龙套的结点指向刚创建的新结点
    
56. temp.nextChild = this.firstChild;//将刚创建的新结点的next指针指向firstChild结点
    
57. }else{
    
58. Child ch = new Child(i);
    
59. this.temp.nextChild = ch;//将上一个结点的next结点指向刚创建的新结点
    
60. this.temp = ch; //还是将跑龙套的结点指向刚创建的新结点
    
61. }
    
62. }
    
63. }
    
64. }
    
65. public void play(){//开始玩游戏的方法
    
66. temp = this.firstChild;
    
67. //先找到开始数数的那个人
    
68. for(int i=1;i<k;i++){
    
69. temp = temp.nextChild;
    
70. }
    
71. while(length!=1){
    
72. //数m下
    
73. for(int j=1;j<m;j++){
    
74. temp = temp.nextChild;
    
75. System.out.println("当前出局的小孩是："+temp.no);
    
76. }
    
77. //如果是单链表的话，问题有点棘手，我怎么要删的结点的上一个结点呢？
    
78. //方法就是从要删除的结点开始遍历整个链表，直到找到一个结点它的next结点指向我们删除的结点
    
79. Child temp2 = temp;
    
80. while(temp2.nextChild!=temp){
    
81. temp2 = temp2.nextChild;
    
82. }
    
83. //将数到m的小孩从链表中删除
    
84. temp2.nextChild = temp.nextChild;
    
85. //继续要将temp指向下一个结点，不能让链表断了
    
86. temp = temp.nextChild;
    
87. this.length--;
    
88. }
    
89. System.out.println("最后出局的小孩是："+temp.no);
    
90. }
    
91. public void show(){
    
92. //定义一个跑龙套的结点
    
93. temp = this.firstChild;
    
94. do{
    
95. System.out.print(" "+temp.no);
    
96. temp = temp.nextChild;
    
97. }while(temp!=this.firstChild);
    
98. System.out.println();
    
99. }
    
100. }

复制代码

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