经过自己测试没有问题，很多地方的实现可能有些麻烦
大佬们可以留言提出宝贵意见，感谢感谢！！！
代码如下：
package util;
import java.util.ArrayList;
public class CircleLinkedList {
Node first;
Node last;
int size = 0;
//添加
public void add (Node newNode){
size++;
if(first == null){
first = newNode;
first.next = first;
first.prev = first;
last = first;
return;
}
//添加新节点
Node temp = first;
while(true){
if(temp == last){
last.next = newNode;
newNode.prev = last;
newNode.next = first;
last = newNode;
break;
}
temp = temp.next;
}
}
//删除
public Node delete (int no) {
if(first == null){
System.out.println("list is empty.");
return null;
}
Node temp = first;
//只有一个元素
if(size == 1){
first = null;
last = null;
size--;
}else{
while(true){
if(temp == last && temp.no != no){
System.out.println("no is not exist.");
break;
}
if(temp.no == no){
//是不是尾节点
size--;
if(temp == last){
temp.prev.next = first;
last = temp.prev.next;
break;
}
//不是尾节点
temp.prev.next = temp.next;
temp.next.prev = temp.prev;
break;
}
temp = temp.next;
}
}
return temp;
}
//遍历
public void list () {
if(first == null){
System.out.println("list is empty.");
return;
}
Node temp = first;
while(true){
System.out.println(temp.toString());
if(temp == last ){
break;
}
temp = temp.next;
}
}
//顺序添加
public void addByOrder (Node newNode){
if(newNode == null){
System.out.println("node is null.");
return;
}
//没有节点直接添加
if(first == null){
first = newNode;
first.prev = first;
first.next = first;
last = first;
size++;
return;
}
Node temp = first;
//如果成为新的首节点
if(newNode.no < temp.no){
size++;
first = newNode;
first.prev = last;
first.next = temp;
temp.prev = first;
last.next = first;
return;
}else if(newNode.no == temp.no){
System.out.println("same number,reject.");
return;
}else{
while(true){
//判断是否到了尾节点
if(temp == last){
if(temp.no < newNode.no){
size++;
temp.next = newNode;
newNode.prev = temp;
newNode.next = first;
last = newNode;
break;
}else if(temp.no == newNode.no){
System.out.println("same number,reject!");
break;
}else{
size++;
temp.prev.next = newNode;
newNode.prev = temp.prev;
newNode.next = temp;
temp.prev = newNode;
break;
}
}
//中间节点插入情况
if(newNode.no < temp.no){
size++;
temp.prev.next = newNode;
newNode.prev = temp.prev;
newNode.next = temp;
temp.prev = newNode;
break;
}else if(newNode.no == temp.no){
System.out.println("same number,reject!");
break;
}
//后移
temp = temp.next;
}
}
}
// 1 2 3 4 5
//约瑟夫问题：出圈，假设5个节点，开始节点为2，报3的出圈，顺序3-1-5-2-4
public void outCircle (int startNum,int countNum) {
//判断参数是否合法
if(startNum > size || countNum > size || countNum < 1 || startNum < 1){
System.out.println("illegal argument.");
return;
}
if(first == null){
System.out.println("list is empty.");
return;
}
//如果只有一个节点
if(size == 1){
System.out.println(first);
return;
}
//定义两个指针,一个是开始节点，一个是结束节点
Node firstNode = first;
Node lastNode = last;
for(int i = 0; i < startNum - 1; i++){
firstNode = firstNode.next;
lastNode = lastNode.next;
}
//开始出列，结束条件 first == last
while(true){
if(firstNode == lastNode){
System.out.println(firstNode.no + "号 last gets out of the list.");
break;
}
for(int i = 0; i < countNum - 1; i++){
firstNode = firstNode.next;
lastNode = lastNode.next;
}
//移除当前节点
firstNode = firstNode.next;
firstNode.prev = lastNode;
lastNode.next = firstNode;
//System.out.println(temp.no + " gets out of the list.");
}
}
}
class Node {
int no;
String name;
Node prev;
Node next;
public Node (int no,String name) {
this.no = no;
this.name = name;
}
public String toString () {
return "number:" + no + "\tname:"+ name;
}
}
class TestList {
public static void main(String[] args) {
CircleLinkedList list = new CircleLinkedList();
for(int i = 1; i < 6 ; i++){
Node node = new Node(i,i+"号");
list.addByOrder(node);
}
// 12345 4 - 2 - 1 - 3 - 5
list.outCircle(2,3);
}
}
运行结果：
image.png
总结经验：
（1）双向环形链表的首尾判断很重要
（2）出队列的两个指针很重要，主要是未来后面判断结束做服务
