单向链表逆序问题
注意这里是单向链表，所以只能从头向尾遍历。
单向链表的逆序主要有以下两种方式。
- 使用栈的先进后出特性，将链表中的数据放入栈中然后再从栈中取出
- 头插法，如果仅有一个元素，那么链表的逆序就是自己。如果有多个元素，顺序取出元素，然后讲后一个放到前一个的前面。
这里我们只讲头插法，头插法的效率是，使用栈是
。两个算法的时间复杂度只有常数级的差异。
头插法如下图所示
97e852ab39cd4732b1e2895235ddbbdcpng
思路分析
- 如果是只有一个节点或者没有节点就什么都不用做
- 如果多于一个节点，定义一个
head变量指向头节点，定义一个node变量指向头结点的下一个节点。 - 将链表中的最后节点指针
last指向头节点，并将其next指针设置为null。这一步其实是非常关键的一步，如果少了这一步会形成循环链表。 - 开始while循环
while(node != null)- 首先定义一个
next变量指向node的下一个节点，这个是我们下次遍历需要处理的节点。 - 让
node.next = head，这步相当于把当前遍历的这个节点插入到了头节点之前 -
head = node，将头节点变更为当前遍历的节点 -
node = next，将当前节点指向下一个节点，开始新一轮的遍历
- 首先定义一个
- 链表中的
first指向head;
代码实现
实现代码如下：
/**
* 反转链表
*/
public void reverse() {
// 如果没有元素或只有一个元素则无需反转。
if (this.size <= 1) {
return;
}
this.last = this.first;
Node<E> head = this.first;
// 由于上面的判断，所以这里的next一定是不为空的
Node<E> node = this.first.next;
head.next = null;
while (node != null) {
// 取出当前元素的下一个元素
Node<E> next = node.next;
// 将当前元素的next指向头节点
node.next = head;
// 将头节点改为当前元素
head = node;
// 开始遍历下一个元素
node = next;
}
this.first = head;
}
代码不多，核心在while循环中，这里一定要想明白。看明白之后一定要写一写，注意这里是自己写，而不是把我写的代码复制到IDE中运行下。
很多人都是“一学就会，一写就废”，就是这个原因，感觉自己看明白了，就认为会了。看明白和写出来是两码事，一定要多写，多练习。
单向链表逆序打印问题
再解决了上面的问题后，这个问题就变得简单了。这个问题有两种方法可以实现，一种是先反转，再打印；一种是采用栈。
先反转再打印会改变原来的数据结构，所以这种方式不推荐。因为使用这种方式需要做两次反转，即 反转 --> 遍历 --> 反转。所以我们采用栈来处理。
这里采用栈来处理，由于代码很简单，所以我们不再做思路分析，直接上代码。
public void reversePrint() {
if (isEmpty()) {
return;
}
if (this.size == 0) {
System.out.println(this.first.item);
return;
}
// 遍历元素并将元素依次入栈
Stack<E> stack = new Stack<>();
Node<E> node = this.first;
while (node != null) {
stack.push(node.item);
node = node.next;
}
// 出栈并打印。
while (!stack.empty()) {
System.out.print(stack.pop() + "\t");
}
System.out.println();
}
约瑟夫问题
约瑟夫（Josephus）问题又叫“约瑟夫环”或“丢手绢问题”。
约瑟夫问题是：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。那么这些人被杀掉的顺序是什么。
思路分析
这里我们采用环形链表的方式来处理，假定报数总是从第一个人开始。
652f2c429b5d4748ba819ebb025b4b20png
第一个人开始报数，然后数到后，这个节点的人出列，然后从下一个人继续开始数。
4ff40cbc4d6340bd9d9ced688d9baf50png
直到最后一个结束，当链表中只剩下一个人的时候，无论数多少最终都是这个人，所以我们可以不用数直接让这个人出列。
52cf2de348b94452a22f5c7365531c75png
如上图：有5人，每次数3个数。
- 第一轮：3号出列，2号的下一个变成4号
- 第二轮：1号出列，5号的下一个变成了2号
- 第三轮：5号出列，4号的下一个变成了2号
- 第四轮：2号出列，这是后仅剩下4号
- 第五轮：4号出列。
代码实现
/**
* 约瑟夫问题
*
* @author jaune
* @since 1.0.0
*/
public class Josephus {
private Node first;
private Node last;
private int size;
/**
* 指定有多少人，然后根据人数创建环形链表。
* @param peopleNum 人数
*/
public Josephus(int peopleNum) {
// 初始化环形链表
for (int i = 1; i <= peopleNum; i++) {
if (this.first == null) {
this.first = new Node(i);
this.last = first;
} else {
Node node = new Node(i);
this.last.next = node;
this.last = node;
}
}
// 最后一个的next指向头结点，形成闭环
this.last.next = this.first;
this.size = peopleNum;
}
public boolean isEmpty() {
return this.size == 0;
}
public List<Integer> kill(int num) {
if (num < 1) {
throw new RuntimeException("报数的数字必须大于0");
}
// 保存被杀人的顺序
List<Integer> killSeq = new ArrayList<>(this.size);
// 开始遍历
if (this.size == 1) {
killSeq.add(this.first.item);
return killSeq;
}
int seq = 0;
Node node = this.first;
Node prev = this.last;
while (true) {
seq++;
if (seq == num) {
// 取出节点
if (node.equals(this.first)) {
this.first = node.next;
}
// 移除选中的人，并重新形成闭环
killSeq.add(node.item);
prev.next = node.next;
Node next = node.next;
node.next = null;
node = next;
seq = 0;
this.size--;
this.list();
// 只剩最后一个节点了，当只剩下最后一个节点的时候我们就不用在数了，直接取出即可。
if (prev.equals(node)) {
killSeq.add(node.item);
this.first = null;
this.last = null;
this.size = 0;
break;
}
} else {
prev = node;
node = node.next;
}
}
return killSeq;
}
// 打印每次kill后剩余的人
public void list() {
if (this.first == null) {
return;
}
Node node = this.first;
do {
System.out.print(node.item + "\t");
node = node.next;
} while (node != null && !node.equals(this.first));
System.out.println();
}
private static class Node {
int item;
Node next;
public Node(int item) {
this.item = item;
}
}
}
size其实是可以不用维护的，如果不每次kill完之后都打印剩下的人，那么可以删掉list方法，这时候first也是不用维护的，这样程序会简洁很多。
网友评论