文章目錄

• 1.數據結構-鏈表詳解
• • 1.1單鏈表
  • • 1.1.1單鏈表節點的尾部添加
    • 1.1.2單鏈表節點的自動排序添加
    • 1.1.3單鏈表節點的修改
    • 1.1.4單鏈表節點的刪除
  • 1.2單鏈表面試題
  • • 1.2.1單鏈表的有效節點個數
    • 1.2.2單鏈表倒數第k個結點
    • 1.2.3單鏈表反轉
    • 1.2.4單鏈表逆序打印
  • 1.3雙向鏈表
  • • 1.3.1雙向鏈表介紹
    • 1.3.2雙向鏈表增刪改查
  • 1.4單向環形鏈表
  • • 1.4.1約瑟夫（Josephu）環問題

1.數據結構-鏈表詳解

鏈表可分為三類：

單鏈表

雙向鏈表

循環列表

下面具體分析三個鏈表的應用。

1.1單鏈表

單鏈表是有序的列表，它在內存中存儲方式如下：

雖然單鏈表是有序列表，但是其元素并不是連續存儲的。我們從圖中可以看出，a1的next域為110，而地址為110的元素為a2；a2的next域為180，而地址為180的元素為a3，以此類推。
綜上所述：

• 單鏈表是以節點的方式來存儲的
• 每個節點包含data域(存儲數據)，next域(指向下一個節點)
• 單鏈表的各個節點不一定是連續存儲的

1.1.1單鏈表節點的尾部添加

對單鏈表的概念和特點有所了解之后，我們通過一個案例來感受一下單鏈表的魅力所在。
需求：使用帶head頭節點的單向鏈表實現——水滸英雄排行榜管理，完成對英雄人物的增刪改查操作。

根據該示意圖，我們可以得出創建單鏈表的具體過程：

先創建一個head頭節點，不存儲數據，作用就是表示單鏈表的頭

后面每添加一個節點，就直接加入到鏈表的末尾

源碼實現：

//定義SingleLinkedList 管理英雄 class SingleLinkedList {// 初始化一個頭節點 不存放具體數據private HeroNode head = new HeroNode(0, "", "");// 添加節點到單向鏈表public void add(HeroNode heroNode) {// 當不考慮編號的順序時:// 1、找到當前鏈表的最后節點// 2、將最后這個節點的next域指向新的節點即可// 因為head頭節點不能動，因此我們需要一個輔助節點tempHeroNode temp = head;// 遍歷鏈表，找到尾節點while (true) {// 找到鏈表的尾節點if (temp.next == null) {break;}// 如果不是尾節點，將temp后移temp = temp.next;}// 循環結束后，temp指向的是尾節點temp.next = heroNode;// 將next域指向新節點}// 顯示鏈表public void list() {// 判斷鏈表是否為空if (head.next == null) {System.out.println("鏈表為空");return;}// 創建一個輔助節點HeroNode temp = head.next;while (true) {// 判斷是否到了鏈表末尾if (temp == null) {break;}// 輸出節點信息System.out.println(temp);// 將temp后移temp = temp.next;}} }//定義HeroNode，每個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;}@Overridepublic String toString() {return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";} }

這樣鏈表就編寫完畢了，接下來編寫測試代碼：

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 = new SingleLinkedList();// 加入鏈表singleLinkedList.add(hero1);singleLinkedList.add(hero2);singleLinkedList.add(hero3);singleLinkedList.add(hero4);// 顯示鏈表singleLinkedList.list();}

運行結果：

HeroNode [no=1, name=宋江, nickname= 及時雨] HeroNode [no=2, name=盧俊義, nickname=玉麒麟] HeroNode [no=3, name=吳用, nickname=智多星] HeroNode [no=4, name=林沖, nickname=豹子頭]

現在這個程序雖然可以創建鏈表，但是它并不能保證元素按照編號進行排序，它只是按照添加的順序進行創建的。
那么如何使英雄在添加進鏈表的時候始終按照排名添加呢？
我們來分析一下：

首先要找到新添加的節點位置，通過一個輔助節點

讓新節點的next等于輔助節點的next，因為輔助節點已經找到了要添加的位置，所以將輔助節點的next賦給新節點的next即可

將新節點的賦值給輔助節點的next

1.1.2單鏈表節點的自動排序添加

源碼實現：

//定義SingleLinkedList 管理英雄 class SingleLinkedList {// 初始化一個頭節點 不存放具體數據private HeroNode head = new HeroNode(0, "", "");// 第二種添加方式，根據排名進行添加public void addByOrder(HeroNode heroNode) {// 創建輔助節點幫助找到添加的位置// 因為是單鏈表，因此輔助節點的位置應該是添加位置的前一個節點HeroNode temp = head;boolean flag = false;// 標識英雄的編號是否存在while (true) {if (temp.next == null) {// 此時temp已經在鏈表末尾break;}if (temp.next.no > heroNode.no) {// 位置找到，就在temp的后面break;} else if (temp.next.no == heroNode.no) {// 編號已存在flag = true;break;}temp = temp.next;// 將temp后移}// 循環結束后，判斷flagif (flag) {// 編號存在，不能添加System.out.println("準備插入的英雄編號" + heroNode.no + "重復，不能加入");} else {// 插入到鏈表中heroNode.next = temp.next;temp.next = heroNode;}}// 顯示鏈表public void list() {// 判斷鏈表是否為空if (head.next == null) {System.out.println("鏈表為空");return;}// 創建一個輔助節點HeroNode temp = head.next;while (true) {// 判斷是否到了鏈表末尾if (temp == null) {break;}// 輸出節點信息System.out.println(temp);// 將temp后移temp = temp.next;}} }

編寫測試代碼：

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 = new SingleLinkedList();// 加入鏈表singleLinkedList.addByOrder(hero1);singleLinkedList.addByOrder(hero3);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);// 顯示鏈表singleLinkedList.list();}

運行效果：

HeroNode [no=1, name=宋江, nickname= 及時雨] HeroNode [no=2, name=盧俊義, nickname=玉麒麟] HeroNode [no=3, name=吳用, nickname=智多星] HeroNode [no=4, name=林沖, nickname=豹子頭]

此時即使添加順序不正確，在插入后鏈表依然將英雄排名進行了排序，這是在插入的時候就已經完成了排序。

1.1.3單鏈表節點的修改

通過上面的分析和實踐，我們已經知道如何去創建一個單鏈表，那么如何對單鏈表的節點修改呢？

// 修改節點的信息，根據no編號來修改public void update(HeroNode newHeroNode) {// 根據newHeroNode的編號進行修改// 判斷鏈表是否為空if (head == null) {System.out.println("鏈表為空");return;}// 找到需要修改的節點// 定義輔助節點HeroNode temp = head.next;boolean flag = false;// 表示是否找到該節點while (true) {if (temp == null) {break;// 鏈表遍歷結束}if (temp.no == newHeroNode.no) {// 找到需要修改的節點flag = true;break;}temp = temp.next;// 將temp后移}// 根據flag判斷是否已經找到要修改的節點if (flag) {temp.name = newHeroNode.name;temp.nickname = newHeroNode.nickname;} else {// 沒有找到節點System.out.println("沒有找到");}}

修改的實現相對來說就非常簡單了。

下面測試一下：

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 = new SingleLinkedList();singleLinkedList.addByOrder(hero1);singleLinkedList.addByOrder(hero3);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);//修改節點HeroNode newHeroNode = new HeroNode(2, "小盧","~玉麒麟~");singleLinkedList.update(newHeroNode);// 顯示鏈表singleLinkedList.list();}

運行結果：

HeroNode [no=1, name=宋江, nickname= 及時雨] HeroNode [no=2, name=小盧, nickname=~玉麒麟~] HeroNode [no=3, name=吳用, nickname=智多星] HeroNode [no=4, name=林沖, nickname=豹子頭]

編號為2的英雄信息就被修改過來了。

1.1.4單鏈表節點的刪除

接下來是最后一個操作，刪除。
首先分析一下：

先找到需要刪除節點的前一個節點，通過一個輔助節點temp

temp.next = temp.next.next，也就是說需要刪除節點的前一個節點本來指向的是刪除節點，然后我們使其指向刪除節點的下一個節點，直接跳過刪除節點，這樣該節點也就相當于被刪除了

被刪除的節點將不會有其它引用指向，會被垃圾回收器回收

源碼實現：

// 刪除節點public void delete(int 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;// 將temp后移}// 判斷flagif (flag) {// 找到// 可以刪除temp.next = temp.next.next;} else {// 未找到System.out.println("要刪除的節點不存在");}}

測試代碼：

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 = new SingleLinkedList();singleLinkedList.addByOrder(hero1);singleLinkedList.addByOrder(hero3);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);//刪除節點singleLinkedList.delete(1);// 顯示鏈表singleLinkedList.list();}

運行結果：

HeroNode [no=2, name=盧俊義, nickname=玉麒麟] HeroNode [no=3, name=吳用, nickname=智多星] HeroNode [no=4, name=林沖, nickname=豹子頭]

宋江被成功刪除。

到這里，關于單鏈表的增刪改查操作就全部結束。

1.2單鏈表面試題

1.2.1單鏈表的有效節點個數

代碼實現：

//方法：獲取到單鏈表的節點的個數(如果是帶頭結點的鏈表，需求不統計頭節點)/*** * @param head 鏈表的頭節點* @return 返回的就是有效節點的個數*/public static int getLength(HeroNode head) {if(head.next == null) { //空鏈表return 0;}int length = 0;//定義一個輔助的變量, 這里我們沒有統計頭節點HeroNode cur = head.next;while(cur != null) {length++;cur = cur.next; //遍歷}return length;}}

測試代碼：

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 = new SingleLinkedList();singleLinkedList.addByOrder(hero1);singleLinkedList.addByOrder(hero3);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);//測試單鏈表中有效節點的個數System.out.println("有效的節點個數=" +getLength(singleLinkedList.getHead()));//2 }

運行結果：

有效的節點個數=4

1.2.2單鏈表倒數第k個結點

代碼實現：

//查找單鏈表中的倒數第k個結點 【新浪面試題】//思路//1. 編寫一個方法，接收head節點，同時接收一個index //2. index 表示是倒數第index個節點//3. 先把鏈表從頭到尾遍歷，得到鏈表的總的長度 getLength//4. 得到size 后，我們從鏈表的第一個開始遍歷 (size-index)個，就可以得到//5. 如果找到了，則返回該節點，否則返回nulllpublic static HeroNode findLastIndexNode(HeroNode head, int index) {//判斷如果鏈表為空，返回nullif(head.next == null) {return null;//沒有找到}//第一個遍歷得到鏈表的長度(節點個數)int size = getLength(head);//第二次遍歷 size-index 位置，就是我們倒數的第K個節點//先做一個index的校驗if(index <=0 || index > size) {return null; }//定義給輔助變量， for 循環定位到倒數的indexHeroNode cur = head.next; //3 // 3 - 1 = 2for(int i =0; i< size - index; i++) {cur = cur.next;}return cur;}

測試代碼：

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 = new SingleLinkedList();singleLinkedList.addByOrder(hero1);singleLinkedList.addByOrder(hero3);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);//測試一下看看是否得到了倒數第K個節點HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 3);System.out.println("倒數第3個節點=" + res);}

運行結果：

倒數第3個節點=HeroNode [no=2, name=盧俊義, nickname=玉麒麟]

1.2.3單鏈表反轉

代碼實現：

//將單鏈表反轉public static void reversetList(HeroNode head) {//如果當前鏈表為空，或者只有一個節點，無需反轉，直接返回if(head.next == null || head.next.next == null) {return ;}//定義一個輔助的指針(變量)，幫助我們遍歷原來的鏈表HeroNode cur = head.next;HeroNode next = null;// 指向當前節點[cur]的下一個節點HeroNode reverseHead = new HeroNode(0, "", "");//遍歷原來的鏈表，每遍歷一個節點，就將其取出，并放在新的鏈表reverseHead 的最前端//動腦筋while(cur != null) { next = cur.next;//先暫時保存當前節點的下一個節點，因為后面需要使用cur.next = reverseHead.next;//將cur的下一個節點指向新的鏈表的最前端reverseHead.next = cur; //將cur 連接到新的鏈表上cur = next;//讓cur后移}//將head.next 指向 reverseHead.next , 實現單鏈表的反轉head.next = reverseHead.next;}

測試代碼：

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 = new SingleLinkedList();singleLinkedList.addByOrder(hero1);singleLinkedList.addByOrder(hero3);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);//測試反轉單鏈表System.out.println("原來鏈表的情況~~");singleLinkedList.list();System.out.println("反轉單鏈表~~");reversetList(singleLinkedList.getHead());singleLinkedList.list(); }

運行結果：

原來鏈表的情況~~ HeroNode [no=1, name=宋江, nickname=及時雨] HeroNode [no=2, name=盧俊義, nickname=玉麒麟] HeroNode [no=3, name=吳用, nickname=智多星] HeroNode [no=4, name=林沖, nickname=豹子頭] 反轉單鏈表~~ HeroNode [no=4, name=林沖, nickname=豹子頭] HeroNode [no=3, name=吳用, nickname=智多星] HeroNode [no=2, name=盧俊義, nickname=玉麒麟] HeroNode [no=1, name=宋江, nickname=及時雨]

1.2.4單鏈表逆序打印

代碼實現：

//可以利用棧這個數據結構，將各個節點壓入到棧中，然后利用棧的先進后出的特點，就實現了逆序打印的效果public static void reversePrint(HeroNode head) {if(head.next == null) {return;//空鏈表，不能打印}//創建要給一個棧，將各個節點壓入棧Stack<HeroNode> stack = new Stack<HeroNode>();HeroNode cur = head.next;//將鏈表的所有節點壓入棧while(cur != null) {stack.push(cur);cur = cur.next; //cur后移，這樣就可以壓入下一個節點}//將棧中的節點進行打印,pop 出棧while (stack.size() > 0) {System.out.println(stack.pop()); //stack的特點是先進后出}}

測試代碼：

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 = new SingleLinkedList();singleLinkedList.addByOrder(hero1);singleLinkedList.addByOrder(hero3);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);//測試逆序打印單鏈表, 沒有改變鏈表的結構System.out.println("原來鏈表的情況~~");singleLinkedList.list();System.out.println("測試逆序打印單鏈表, 沒有改變鏈表的結構~~");reversePrint(singleLinkedList.getHead());}

運行結果：

原來鏈表的情況~~ HeroNode [no=1, name=宋江, nickname=及時雨] HeroNode [no=2, name=盧俊義, nickname=玉麒麟] HeroNode [no=3, name=吳用, nickname=智多星] HeroNode [no=4, name=林沖, nickname=豹子頭] 測試逆序打印單鏈表, 沒有改變鏈表的結構~~ HeroNode [no=4, name=林沖, nickname=豹子頭] HeroNode [no=3, name=吳用, nickname=智多星] HeroNode [no=2, name=盧俊義, nickname=玉麒麟] HeroNode [no=1, name=宋江, nickname=及時雨]

1.3雙向鏈表

1.3.1雙向鏈表介紹

雙向鏈表可以向前或者向后查找。而單向鏈表，只能一個方向查找。

雙向鏈表，可以自我刪除。單向鏈表不能自我刪除，需要靠輔助節點 ，所以前面我們單鏈表刪除節點時，總是找到temp,temp是待刪除節點的前一個節點。

1.3.2雙向鏈表增刪改查

源碼實現：

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.addByOrder(hero4);doubleLinkedList.addByOrder(hero3);doubleLinkedList.addByOrder(hero2);doubleLinkedList.addByOrder(hero1);doubleLinkedList.list();// 修改 // HeroNode2 newHeroNode = new HeroNode2(4, "公孫勝", "入云龍"); // doubleLinkedList.update(newHeroNode); // System.out.println("修改后的鏈表情況"); // doubleLinkedList.list();// 刪除 // doubleLinkedList.del(3); // System.out.println("刪除后的鏈表情況~~"); // doubleLinkedList.list();}}// 創建一個雙向鏈表的類 class DoubleLinkedList {// 先初始化一個頭節點, 頭節點不要動, 不存放具體的數據private HeroNode2 head = new HeroNode2(0, "", "");// 返回頭節點public HeroNode2 getHead() {return head;}// 遍歷雙向鏈表的方法// 顯示鏈表[遍歷]public void list() {// 判斷鏈表是否為空if (head.next == null) {System.out.println("鏈表為空");return;}// 因為頭節點，不能動，因此我們需要一個輔助變量來遍歷HeroNode2 temp = head.next;while (true) {// 判斷是否到鏈表最后if (temp == null) {break;}// 輸出節點的信息System.out.println(temp);// 將temp后移， 一定小心temp = temp.next;}}//第二種方式在添加英雄時，根據排名將英雄插入到指定位置//(如果有這個排名，則添加失敗，并給出提示)public void addByOrder(HeroNode2 heroNode) {//因為頭節點不能動，因此我們仍然通過一個輔助指針(變量)來幫助找到添加的位置//因為單鏈表，因為我們找的temp 是位于 添加位置的前一個節點，否則插入不了HeroNode2 temp = head;boolean flag = false; // flag標志添加的編號是否存在，默認為falsewhile(true) {if(temp.next == null) {//說明temp已經在鏈表的最后break; //} if(temp.next.no > heroNode.no) { //位置找到，就在temp的后面插入break;} else if (temp.next.no == heroNode.no) {//說明希望添加的heroNode的編號已然存在flag = true; //說明編號存在break;}temp = temp.next; //后移，遍歷當前鏈表}//判斷flag 的值if(flag) { //不能添加，說明編號存在System.out.printf("準備插入的英雄的編號 %d 已經存在了, 不能加入\n", heroNode.no);} else {heroNode.next = temp.next;//（若temp是最后一個節點則不需要執行這句話否則出現空指針）if(temp.next!=null)temp.next.pre = heroNode;heroNode.pre = temp;temp.next = heroNode;}}// 添加一個節點到雙向鏈表的最后.public void add(HeroNode2 heroNode) {// 因為head節點不能動，因此我們需要一個輔助遍歷 tempHeroNode2 temp = head;// 遍歷鏈表，找到最后while (true) {// 找到鏈表的最后if (temp.next == null) {//break;}// 如果沒有找到最后, 將將temp后移temp = temp.next;}// 當退出while循環時，temp就指向了鏈表的最后// 形成一個雙向鏈表temp.next = heroNode;heroNode.pre = temp;}// 修改一個節點的內容, 可以看到雙向鏈表的節點內容修改和單向鏈表一樣// 只是 節點類型改成 HeroNode2public 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;break;}temp = temp.next;}// 根據flag 判斷是否找到要修改的節點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;}HeroNode2 temp = head.next; // 輔助變量(指針)boolean flag = false; // 標志是否找到待刪除節點的while (true) {if (temp == null) { // 已經到鏈表的最后break;}if (temp.no == no) {// 找到的待刪除節點的前一個節點tempflag = true;break;}temp = temp.next; // temp后移，遍歷}// 判斷flagif (flag) { // 找到// 可以刪除// temp.next = temp.next.next;[單向鏈表]temp.pre.next = temp.next;// 這里我們的代碼有問題?// 如果是最后一個節點，就不需要執行下面這句話，否則出現空指針if (temp.next != null) {temp.next.pre = temp.pre;}} else {System.out.printf("要刪除的 %d 節點不存在\n", no);}}}// 定義HeroNode2 ， 每個HeroNode 對象就是一個節點 class HeroNode2 {public int no;public String name;public String nickname;public HeroNode2 next; // 指向下一個節點, 默認為nullpublic HeroNode2 pre; // 指向前一個節點, 默認為null// 構造器public HeroNode2(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}// 為了顯示方法，我們重新toString@Overridepublic String toString() {return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";}}

1.4單向環形鏈表

示意圖：

1.4.1約瑟夫（Josephu）環問題

設編號為1，2，… n的n個人圍坐一圈，約定編號為k（1<=k<=n）的人從1開始報數，數到m 的那個人出列，它的下一位又從1開始報數，數到m的那個人又出列，依次類推，直到所有人出列為止，由此產生一個出隊編號的序列。

思路提示：( 使用單向環形鏈表解決Josephu問題)

用一個不帶頭結點的循環鏈表來處理Josephu 問題：先構成一個有n個結點的單循環鏈表，然后由k結點起從1開始計數，計到m時，對應結點從鏈表中刪除，然后再從被刪除結點的下一個結點又從1開始計數，直到最后一個結點從鏈表中刪除算法結束。

源碼實現：

public class Josephu {public static void main(String[] args) {// 測試一把看看構建環形鏈表，和遍歷是否okCircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();circleSingleLinkedList.addBoy(125);// 加入5個小孩節點circleSingleLinkedList.showBoy();//測試一把小孩出圈是否正確circleSingleLinkedList.countBoy(10, 20, 125); // 2->4->1->5->3//String str = "7*2*2-5+1-5+3-3";}}// 創建一個環形的單向鏈表 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; // 讓curBoy指向第一個小孩} 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.getNext(); // curBoy后移}}// 根據用戶的輸入，計算出小孩出圈的順序/*** * @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;}// 創建要給輔助指針,幫助完成小孩出圈Boy helper = first;// 需求創建一個輔助指針(變量) helper , 事先應該指向環形鏈表的最后這個節點while (true) {if (helper.getNext() == first) { // 說明helper指向最后小孩節點break;}helper = helper.getNext();}//小孩報數前，先讓 first 和 helper 移動 k - 1次for(int j = 0; j < startNo - 1; j++) {first = first.getNext();helper = helper.getNext();}//當小孩報數時，讓first 和 helper 指針同時 的移動 m - 1 次, 然后出圈//這里是一個循環操作，知道圈中只有一個節點while(true) {if(helper == first) { //說明圈中只有一個節點break;}//讓 first 和 helper 指針同時 的移動 countNum - 1for(int j = 0; j < countNum - 1; j++) {first = first.getNext();helper = helper.getNext();}//這時first指向的節點，就是要出圈的小孩節點System.out.printf("小孩%d出圈\n", first.getNo());//這時將first指向的小孩節點出圈first = first.getNext();helper.setNext(first); //}System.out.printf("最后留在圈中的小孩編號%d \n", first.getNo());} }// 創建一個Boy類，表示一個節點 class Boy {private int no;// 編號private Boy next; // 指向下一個節點,默認nullpublic 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;}}

總結

以上是生活随笔為你收集整理的java数据结构-链表详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。