链表LinkedList

1.单向链表

1.1 定义HeroNode对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//定义HeroNode对象
class HeroNode{
	
	//英雄编号
	public int no;
	
	//英雄名字
	public String name;
	
	//英雄别名
	public String nickName;
	
	//指向下一个节点
	public HeroNode next;
	
	//构造器
	public HeroNode(int no,String name,String nickName) {
		this.no = no;
		this.name = name;
		this.nickName = nickName;
	}

	
	//显示方便--重写toString
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
	}	
}

1.2 定义一个单向链表

  • public void add(HeroNode heroNode);添加节点的方法
  • public void addByOrder(HeroNode heroNode);根据排名将英雄插入到指定位置–如果有这个排名则添加失败–给出提示
  • public void update(HeroNode newHeroNode);修改节点的信息
  • public void showList();显示链表
  • public void del(int no); 删除节点的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
//定义一个单向链表
class SingleLinkedList {
	
	//初始化头结点--头结点不动，不存放具体的数据
	HeroNode head = new HeroNode(0,"","");
	
	/**
	 * 添加节点到单向链表：
	 * 思路：当不考虑编号数据时
	 * 1.找到当前链表的最后节点
	 * 2.将最后这个节点的next指向新的节点
	 * */
	public void add(HeroNode heroNode) {
		
		//因为head节点不能动，因为我们需要一个辅助遍历temp
		HeroNode temp = head;
		
		//遍历链表，找到最后
		while(true) {
			
			//找到链表的最后
			if(temp.next == null) {
				break;
			}
			
			//如果没找到将temp后移
			temp = temp.next;	
		}
		//经过上面的循环之后 temp就是最后一个节点了---将temp.next指向新的节点就ok了
		
		temp.next = heroNode;
		
	}
	
	
	//第二种方式添加节点，根据排名将英雄插入到指定位置--如果有这个排名则添加失败--给出提示
	public void addByOrder(HeroNode heroNode) {
		//因为头结点不能动，因此我们仍然通过一个辅助指针（变量）来帮助我们找到添加的位置
		//因为是单链表，因为我们找的temp是位于 添加位置的前一个节点，否则插入不了
		HeroNode temp = head;
		
		//flag 标志添加的编号是否存在，默认为false
		boolean flag = false;
		
		//遍历队列
		while(true) {
			
			//说明temp已经到链表的最后
			if(temp.next == null) {
				break;
			}
			
			//位置找到了，就在temp的后面
			if(temp.next.no > heroNode.no) {
				break;
			}else if(temp.next.no == heroNode.no) {
				//说明希望添加的heroNode编号已经存在
				flag = true;
				break;
			}
			
			//后移，遍历链表
			temp=temp.next;
		}
		if(flag) {
			
			System.out.printf("准备插入的英雄编号 %d 已经存在了\n",heroNode.no);
			
		}else {
			//插入到链表中
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}
	
	
	//修改节点的信息,根据no编号来进行修改，即no编号不能改---根据newHeroNode 的no 来修改
	public void update(HeroNode newHeroNode) {
		
		//判断链表是否为空
		if(head.next == null) {
			System.out.println("链表为空！");
			return;
		}
		
		//找到需要修改的节点，根据no编号---定义一个辅助变量
		HeroNode temp = head.next;
		
		//来判断是否存在这个节点
		boolean flag = false;
		
		//遍历链表
		while(true) {
			
			//遍历完毕
			if(temp == null) {
				break;
			}
			
			
			if(temp.no == newHeroNode.no) {
				//如果存在 flag = true;
				flag = true;
				break;
			}
			
			//将temp后移
			temp = temp.next;
		}
		
		
		//如果存在该节点，进行更新
		if(flag) {
			temp.name = newHeroNode.name;
			temp.nickName = newHeroNode.nickName;
		}else {
			//如果不存在
			System.out.printf("没有找到 编号 %d 的节点,不能修改\n",newHeroNode.no);
			//进行测试修改节点的代码
		}
		
		
	}
	
	//显示链表
	public void showList() {
		
		//判断链表是否为空
		if(head.next == null) {
			System.out.println("链表为空！");
			return;
		}
		
		//因为头结点，不能动，因此我们需要一个辅助变量来遍历
		HeroNode temp = head.next;
		
		while(true) {
			//如果temp
			if(temp == null) {
				break;
			}
			
			//输出节点信息
			System.out.println(temp);
			
			//将temp后移---一定小心？？？？？
			temp = temp.next;
			
		}	
		
	}
	
	
	//删除节点的方法
	public void del(int no) {
		/**
		 * 1.head 不能动，因为我们需要一个temp辅助节点---找到待删除节点的前一个节点
		 * 2.说明我们在比较的时候，是temp.next.no 和需要删除的节点的no比较
		 * */
		HeroNode temp = head;
		
		//标志是否找到待删除的节点
		boolean flag = false;
		
		while(true) {
			
			if(temp.next == null) {
				break;
			}
			
			//找到了要删除的节点
			if(temp.next.no == no) {
				flag=true;
				break;
			}
			
			temp = temp.next;
		}
		
		//判断flag
		if(flag) {
			//进行删除的操作
			temp.next = temp.next.next;
			
		}else{
			System.out.printf("要删除的 %d 节点不存在\n",no);
		}	
	}	
}

1.3 测试单向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class SingleLinkedListDemo {

	public static void main(String[] args) {
	

		//测试一下--添加节点和遍历节点		 
		HeroNode hero1 = new HeroNode(1, "松江", "及时雨");
		HeroNode hero2 = new HeroNode(2, "卢俊义","玉麒麟");
		//HeroNode hero3 = new HeroNode(3, "吴用","智多星");
		HeroNode hero4 = new HeroNode(4, "林冲","豹子头");
	
		
		//创建SingleLinkedList对象
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		
		//添加数据--链表是按照添加顺序排序（后面升级）
//		singleLinkedList.add(hero1);
//		singleLinkedList.add(hero2);
//		singleLinkedList.add(hero3);
//		singleLinkedList.add(hero4);
		//singleLinkedList.add(hero1);造成死循环--这个死循环会让遍历一直遍历
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero2);
		singleLinkedList.addByOrder(hero1);
		
		System.out.println("修改前的链表");
		//遍历数据
		singleLinkedList.showList();
		
		HeroNode hero5 = new HeroNode(4, "冲冲", "豹子王");
		singleLinkedList.update(hero5);
		
		System.out.println("修改后的链表");
		//遍历数据
		singleLinkedList.showList();
		
		singleLinkedList.del(1);
		System.out.println("删除后的数据！");
		//遍历数据
		singleLinkedList.showList();
	}
}

1.4 求单链表中有效节点的个数（新浪面试题 ）

求单链表中有效节点的个数（如果该链表带头结点，不统计头结点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int getLength(HeroNode head) {
	
	//说明该链表为空链表
	if(head.next == null) {
		return 0;
	}
	
	int count = 0;
	
	//注意没有统计头结点
	while(head.next != null) {
		
		count++;
		
		//后移一个位置
		head = head.next;
	}
	
	
	return count;
}

1.5 查找链表中的倒数第k个节点（新浪面试题 ）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static HeroNode findLastIndexNode(HeroNode head,int index) {
	
	//如果链表为空返回为null
	if(head.next == null) {
		System.out.println("链表为空");
		return null;
	}
	
	//第一次遍历得到的链表的长度
	int length = getLength(head);
	
	//第二次遍历 length-index 位置
	if(index <=0 || index > length ) {
		//这个是对index的校验
		System.out.println("index不规范");
		return null;
	}
	/**
	 * 找到倒数第index个节点
	 * 分析一波：
	 * 	链表数据
	 * 			  头  1 2 3 4  length=4
	 *  倒数第index个
	 *  		 index = 2
	 * */
	//需要借助中间节点
	HeroNode temp = head.next;
	
	
	for (int i = 0; i < length-index; i++) {
		//初始temp是第一个节点，
		temp = temp.next;
	}
	
	return temp;
}

1.6 单链表的反转(腾讯面试题)

  1. 首先先判断该链表是否有数据

  2. 判断长度是否大于1

  3. 设置reverseHead

  4. 遍历链表 取数据 然后 加数据

  5. 把head.next = reverseHead.next;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public static void reverseList(HeroNode head) {
	
	//第一步
	if(head.next == null || head.next.next == null) {
		return;
	}
	
	//定义一个辅助变量，帮助我们遍历原来的链表
	HeroNode cur = head.next;
	
	//指向当前节点的下一个节点
	HeroNode next = null;
	
	//第三步
	HeroNode reverseHead = new HeroNode(-1,"","");
	
	/**
	 * 分析一波：解释一下next的作用
	 * 遍历原来的链表，每遍历一个节点，将其取出，并放在新的链表reverseHead的最前端
	 * 原链表：  			Head ---1---2---3
	 * 经过一次之后：    reverseHead ---1
	 * 经过两次之后：		reverseHead ---2---1
	 * 					...
	 * */
	while(cur!=null) {
		//先暂时保存当前节点的下一个节点，因为后面需要使用
		next = cur.next;
		
		//将cur的下一个节点指向新的链表的最前端
		cur.next = reverseHead.next;
		
		//将cur连接到新的链表上
		reverseHead.next = cur;
		
		//让cur后移
		cur = next;
	}
	
	//实现反转
	head.next = reverseHead.next;	
}

1.7 单向链表的逆序打印（百度面试题）

  • 方法一：就是先把单向链表进行反转然后遍历打印，这样存在一个问题：会改变原始的链表结构；
  • 方法二：利用栈这个数据结构，将各个节点压入栈，然后利用栈的先进后出的特点来实现；
  • 这里我们使用方法二；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void reversePrint(HeroNode head) {
	
	if(head.next == null) {
		//空链表，不能打印
		return;
	}
	//创建一个栈
	Stack<HeroNode> stack = new Stack();
	
	HeroNode cur = head.next;
	
	while(cur!=null) {
		//入栈
		stack.add(cur);
		//后移，进行遍历
		cur = cur.next;
	}
	
	//将栈中的节点进行打印
	while(stack.size()>0) {
		//stack特点是：后进先出
		System.out.println(stack.pop());
	}
	
}

TestStack.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class TestStack {
	public static void main(String[] args) {
		
		Stack<String> stack = new Stack();
		
		//入栈
		stack.add("喵喵");
		stack.add("喵喵~");
		stack.add("喵喵miao~");
		
		//出栈
		while(stack.size()>0) {
			//pop()就是将栈顶的数据取出
			System.out.println(stack.pop());
		}
	}
}

2. 双向链表

双向链表的遍历，添加，修改，删除的操作思路

  • 遍历方法和单链表一样，只是可以向前，也可以向后查找
  • 添加 (默认添加到双向链表的最后)
    (1) 先找到双向链表的最后这个节点
    (2) temp.next = newHeroNode
    (3) newHeroNode.pre = temp;
  • 修改思路和原来的单向链表一样.
  • 删除
    (1) 因为是双向链表，因此，我们可以实现自我删除某个节点
    (2) 直接找到要删除的这个节点，比如 temp
    (3) temp.pre.next = temp.next
    (4) temp.next.pre = temp.pre;

2.1 定义一个HeroNode2对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//定义HeroNode2对象,每个HeroNode2对象就是一个节点
class HeroNode2{
	
	//英雄编号
	public int no;
	
	//英雄名字
	public String name;
	
	//英雄别名
	public String nickName;
	
	//指向下一个节点，默认为null
	public HeroNode2 next;
	
	//指向上一个节点，默认为null
	public HeroNode2 pre;
	
	//构造器
	public HeroNode2(int no,String name,String nickName) {
		this.no = no;
		this.name = name;
		this.nickName = nickName;
	}

	
	//显示方便--重写toString
	@Override
	public String toString() {
		return "HeroNode2 [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
	}
}

2.2 定义一个双向链表

  • public void add(HeroNode heroNode);添加节点的方法
  • public void update(HeroNode newHeroNode);修改节点的信息
  • public void showList();显示链表
  • public void del(int no); 删除节点的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
class DoubleLinkedList{

	//初始化头结点--头结点不动，不存放具体的数据
	HeroNode2 head = new HeroNode2(0,"","");
	
	/**
	 * 返回头结点
	 */
	public HeroNode2 getHead() {
		return head;
	}
	
	/**
	 * 显示链表
	 * */
 	public void showList() {
		
		//判断链表是否为空
		if(head.next == null) {
			System.out.println("链表为空！");
			return;
		}
		
		//因为头结点，不能动，因此我们需要一个辅助变量来遍历
		HeroNode2 temp = head.next;
		
		while(true) {
			//如果temp
			if(temp == null) {
				break;
			}
			
			//输出节点信息
			System.out.println(temp);
			
			//将temp后移---一定小心
			temp = temp.next;
			
		}
	}
	
	
	
	/**
	 * 添加节点到链表的最后，最后需要修改一下
	 * */
	public void add(HeroNode2 heroNode) {
		
		//因为head节点不能动，因为我们需要一个辅助遍历temp
		HeroNode2 temp = head;
		
		//遍历链表，找到最后
		while(true) {
			
			//找到链表的最后
			if(temp.next == null) {
				break;
			}
			
			//如果没找到将temp后移
			temp = temp.next;	
		}
		//经过上面的循环之后 temp就是最后一个节点了---将temp.next指向新的节点就ok了
		//形成一个双向链表
		temp.next = heroNode;
		heroNode.pre = temp;
		
	}

	/**
	 * 修改节点的信息,根据no编号来进行修改，即no编号不能改---根据newHeroNode 的no 来修改
	 * 双向链表的修改和单向的逻辑一样
	 * */
	public void update(HeroNode2 newHeroNode) {
		
		//判断链表是否为空
		if(head.next == null) {
			System.out.println("链表为空！");
			return;
		}
		
		//找到需要修改的节点，根据no编号---定义一个辅助变量
		HeroNode2 temp = head.next;
		
		//来判断是否存在这个节点
		boolean flag = false;
		
		//遍历链表
		while(true) {
			
			//遍历完毕
			if(temp == null) {
				break;
			}
			
			
			if(temp.no == newHeroNode.no) {
				//如果存在 flag = true;
				flag = true;
				break;
			}
			
			//将temp后移
			temp = temp.next;
		}
		
		
		//如果存在该节点，进行更新
		if(flag) {
			temp.name = newHeroNode.name;
			temp.nickName = newHeroNode.nickName;
		}else {
			//如果不存在
			System.out.printf("没有找到 编号 %d 的节点,不能修改\n",newHeroNode.no);
			//进行测试修改节点的代码
		}
		
		
	}
	
	
	/**
	 * 删除节点
	 * 1.对于双向链表，我们可以直接找到要删除的这个节点
	 * 2.找到后，自我删除即可
	 */
	public void del(int no) {
		
		//判断当前链表是否为空
		if(head.next == null){
			System.out.println("链表为空，无法删除");
			return;
		}
		
		/**
		 * 1.head 不能动，因为我们需要一个 temp 辅助节点---找到待删除节点的这一个节点
		 * 2.说明我们在比较的时候，是temp.next.no 和需要删除的节点的no比较
		 * */
		HeroNode2 temp = head.next;
		
		//标志是否找到待删除的节点
		boolean flag = false;
		
		while(true) {
			
			if(temp == null) {
				break;
			}
			
			//找到了要删除的节点
			if(temp.no == no) {
				flag=true;
				break;
			}
			
			temp = temp.next;
		}
		
		//判断flag
		if(flag) {
			
			//进行删除的操作
			temp.pre.next = temp.next;
			//可能会有空指针异常,所以需要添加一个判断
			
			if(temp.next!=null) {
				temp.next.pre = temp.pre;
			}
			
			
		}else{
			System.out.printf("要删除的 %d 节点不存在\n",no);
		}
	}	

	
}

2.3 测试双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * @author DuanChaojie
 * @date 2020年2月23日 下午12:37:54
 * @version 1.0
 */
public class DoubleLinkedListDemo {

	/*
	 * 双向链表的测试
	 * */
	public static void main(String[] args) {
		System.out.println("双向链表的测试");
		//测试一下--添加节点和遍历节点		 
		HeroNode2 hero1 = new HeroNode2(1, "松江", "及时雨");
		HeroNode2 hero2 = new HeroNode2(2, "卢俊义","玉麒麟");
		HeroNode2 hero3 = new HeroNode2(3, "吴用","智多星");
		HeroNode2 hero4 = new HeroNode2(4, "林冲","豹子头");
		
		//创建一个双向链表
		DoubleLinkedList doubleLinkedList = new  DoubleLinkedList();
		doubleLinkedList.add(hero1);
		doubleLinkedList.add(hero2);
		doubleLinkedList.add(hero3);
		doubleLinkedList.add(hero4);
		
		
		//显示双向链表
		doubleLinkedList.showList();

		//修改
		HeroNode2 newHeroNode2 = new HeroNode2(4, "公孙胜","入云龙");
		doubleLinkedList.update(newHeroNode2);
		System.out.println("修改后的链表情况");
		doubleLinkedList.showList();
		
		//删除
		doubleLinkedList.del(2);
		System.out.println("删除后的链表");
		doubleLinkedList.showList();
		
	}
}

3. 单向循环链表

3.1 单向环形链表应用场景

​ Josephu(约瑟夫、约瑟夫环) 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

​ 用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。

3.2 创建一个Boy类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 创建一个Boy类，表示一个节点
 */
class Boy {

	// 编号
	private int no;

	// 指向下一个节点，默认null
	private Boy next;

	public Boy(int no) {
		this.no = no;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public Boy getNext() {
		return next;
	}

	public void setNext(Boy next) {
		this.next = next;
	}

}

3.3 创建环形链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * 创建一个环形的单向链表
 */
class CircleSingleLinkedList {

	// 创建一个first节点，当前没有编号
	private Boy first = null;

	// 添加小孩节点，构成一个环形链表
	public void addBoy(int nums) {
		// 进行nums校验
		if (nums < 1) {
			System.out.println("nums的值不正确");
			return;
		}
		// 辅助指针，帮助构建环形链表
		Boy curBoy = null;

		// 使用for循环来创建环形链表
		for (int i = 1; i <= nums; i++) {
			// 根据编号创建小孩节点
			Boy boy = new Boy(i);
			// 如果是第一个小孩
			if (i == 1) {
				first = boy;
				// 构成环
				first.setNext(first);
				curBoy = first;
			} else {
				curBoy.setNext(boy);
				boy.setNext(first);
				curBoy = boy;
			}
		}

	}

	/**
	 * 遍历当前循环链表
	 */
	public void showBoy() {

		// 判断链表是否为空
		if (first == null) {
			System.out.println("链表为空");
			return;
		}

		// 因为first不能动，因为我们仍然使用一个辅助指针完成遍历
		Boy curBoy = first;
		while (true) {
			System.out.printf("小孩的编号 %d \n", curBoy.getNo());

			// 说明已经遍历完毕
			if (curBoy.getNext() == first) {
				break;
			}
			// curBoy后移
			curBoy = curBoy.getNext();
		}

	}


}

3.4 添加出圈方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * 根据用户的输入，计算出小孩出圈的顺序
 * 
 * @param startNo  表示从第几个小孩开始数数
 * @param countNum 表示数几下
 * @param nums     表示最初有多少小孩在圈中
 */
public void countBoy(int startNo, int countNum, int nums) {
	// 先对数据进行校验
	if (first == null || startNo < 1 || startNo > nums) {
		System.out.println("参数输入有误");
		return;
	}

	// 创建辅助指针，帮助小孩出圈
	// 需要创建一个辅助指针变量helper,事先应该指向环形链表的最后这个节点
	Boy helper = first;
	while (true) {
		// 说明helper指向最后小孩节点
		if (helper.getNext() == first) {
			break;
		}
		helper = helper.getNext();
	}

	// 小孩报数前，先让first和helper移动 k-1 次
	for (int j = 0; j < startNo - 1; j++) {
		first = first.getNext();
		helper = helper.getNext();
	}

	// 当小孩报数时，让 first 和 helper 指针同时 的移动 countNum - 1 次, 然后出圈
	// 这里是一个循环操作，知道圈中只有一个节点
	while (true) {
		if (helper == first) {
			// 说明圈中只有一个人
			break;
		}
		// 让first和helper指针同时移动countNum - 1
		for (int j = 0; j < countNum - 1; j++) {
			first = first.getNext();
			helper = helper.getNext();
		}

		System.out.printf("小孩%d出圈\n", first.getNo());

		// 将first指向的节点出圈
		first = first.getNext();
		helper.setNext(first);

	}
	System.out.printf("最后留在圈中的小孩的编号%d\n", first.getNo());

}

3.5 测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Josephu {

	public static void main(String[] args) {
		/**
		 * 看看构建的环形链表以及遍历
		 */
		CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
		circleSingleLinkedList.addBoy(5);
		circleSingleLinkedList.showBoy();
		
		circleSingleLinkedList.countBoy(1, 2, 5);

	}

}