經(jīng)過(guò)自己測(cè)試沒(méi)有問(wèn)題乎澄，很多地方的實(shí)現(xiàn)可能有些麻煩
大佬們可以留言提出寶貴意見(jiàn)害晦，感謝感謝Ｂ嫦ァ！嚼摩！
代碼如下：
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;
}
//添加新節(jié)點(diǎn)
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;
//只有一個(gè)元素
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){
//是不是尾節(jié)點(diǎn)
size--;
if(temp == last){
temp.prev.next = first;
last = temp.prev.next;
break;
}
//不是尾節(jié)點(diǎn)
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;
}
//沒(méi)有節(jié)點(diǎn)直接添加
if(first == null){
first = newNode;
first.prev = first;
first.next = first;
last = first;
size++;
return;
}
Node temp = first;
//如果成為新的首節(jié)點(diǎn)
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){
//判斷是否到了尾節(jié)點(diǎn)
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;
}
}
//中間節(jié)點(diǎn)插入情況
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
//約瑟夫問(wèn)題：出圈钦讳，假設(shè)5個(gè)節(jié)點(diǎn)矿瘦，開(kāi)始節(jié)點(diǎn)為2，報(bào)3的出圈愿卒，順序3-1-5-2-4
public void outCircle (int startNum,int countNum) {
//判斷參數(shù)是否合法
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;
}
//如果只有一個(gè)節(jié)點(diǎn)
if(size == 1){
System.out.println(first);
return;
}
//定義兩個(gè)指針,一個(gè)是開(kāi)始節(jié)點(diǎn)缚去，一個(gè)是結(jié)束節(jié)點(diǎn)
Node firstNode = first;
Node lastNode = last;
for(int i = 0; i < startNum - 1; i++){
firstNode = firstNode.next;
lastNode = lastNode.next;
}
//開(kāi)始出列，結(jié)束條件 first == last
while(true){
if(firstNode == lastNode){
System.out.println(firstNode.no + "號(hào) last gets out of the list.");
break;
}
for(int i = 0; i < countNum - 1; i++){
firstNode = firstNode.next;
lastNode = lastNode.next;
}
//移除當(dāng)前節(jié)點(diǎn)
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+"號(hào)");
list.addByOrder(node);
}
// 12345 4 - 2 - 1 - 3 - 5
list.outCircle(2,3);
}
}
運(yùn)行結(jié)果：
image.png
總結(jié)經(jīng)驗(yàn)：
（1）雙向環(huán)形鏈表的首尾判斷很重要
（2）出隊(duì)列的兩個(gè)指針很重要琼开，主要是未來(lái)后面判斷結(jié)束做服務(wù)
