雙向環(huán)形鏈表和約瑟夫問(wèn)題Java實(shí)現(xiàn)

經(jīng)過(guò)自己測(cè)試沒(méi)有問(wèn)題乎澄,很多地方的實(shí)現(xiàn)可能有些麻煩
大佬們可以留言提出寶貴意見(jiàn)害晦,感謝感謝B嫦ァ!嚼摩!

代碼如下:

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ù)

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末病游,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子稠通,更是在濱河造成了極大的恐慌衬衬,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,729評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件改橘,死亡現(xiàn)場(chǎng)離奇詭異滋尉,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)飞主,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門狮惜,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人碌识,你說(shuō)我怎么就攤上這事碾篡。” “怎么了筏餐?”我有些...
    開(kāi)封第一講書人閱讀 169,461評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵开泽,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我魁瞪,道長(zhǎng)穆律,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書人閱讀 60,135評(píng)論 1 300
  • 正文 為了忘掉前任导俘,我火速辦了婚禮峦耘,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘旅薄。我一直安慰自己辅髓,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布少梁。 她就那樣靜靜地躺著洛口,像睡著了一般。 火紅的嫁衣襯著肌膚如雪猎莲。 梳的紋絲不亂的頭發(fā)上绍弟,一...
    開(kāi)封第一講書人閱讀 52,736評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音著洼,去河邊找鬼樟遣。 笑死,一個(gè)胖子當(dāng)著我的面吹牛身笤,可吹牛的內(nèi)容都是我干的豹悬。 我是一名探鬼主播,決...
    沈念sama閱讀 41,179評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼液荸,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼瞻佛!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起娇钱,我...
    開(kāi)封第一講書人閱讀 40,124評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤伤柄,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后文搂,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體适刀,經(jīng)...
    沈念sama閱讀 46,657評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評(píng)論 3 342
  • 正文 我和宋清朗相戀三年煤蹭,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了笔喉。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,872評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡硝皂,死狀恐怖常挚,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情稽物,我是刑警寧澤奄毡,帶...
    沈念sama閱讀 36,533評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站贝或,受9級(jí)特大地震影響秧倾,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜傀缩,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評(píng)論 3 336
  • 文/蒙蒙 一那先、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧赡艰,春花似錦售淡、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 32,700評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至料身,卻和暖如春汤纸,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背芹血。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 33,819評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工贮泞, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留楞慈,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,304評(píng)論 3 379
  • 正文 我出身青樓啃擦,卻偏偏與公主長(zhǎng)得像囊蓝,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子令蛉,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容