文章目錄
- 第二章-連結清單
- 1.連結清單(Linked List)介紹
- 1.1 記憶體結構
- 1.2 邏輯結構
- 2.連結清單的應用場景
- 2.1 直接插傳入連結表
- 2.2 按順序插傳入連結表
- 2.3 修改單連結清單的節點資訊
- 2.4 删除單連結清單的節點
- 3.單連結清單的常見面試題
- 3.1 求單連結清單中的有效節點個數
- 3.2 查找單連結清單中的倒數第k個節點[新浪面試題]
- 3.3 單連結清單的反轉[騰訊面試題,有點難度]
- 3.4 從尾到頭列印單連結清單[百度面試題]
- 3.5 合并兩個有序的單連結清單，合并之後的連結清單仍然有序
- 4.雙向連結清單
- 4.1 連結清單節點的定義
- 4.2 雙向連結清單周遊
- 4.3 尾部插入節點
- 4.4 按順序插入節點
- 4.5 修改節點資訊
- 4.6 删除節點
- 4.7 雙向連結清單測試結果
- 4.8 雙向連結清單所有代碼
- 5.單向環形連結清單
- 5.1 單向環形連結清單圖解
- 5.2 約瑟夫問題
- 5.3 環形連結清單的建構與周遊
- 5.3.1 Boy 節點的定義
- 5.3.2 單向循環連結清單的定義
- 5.4 約瑟夫問題代碼實作
- 5.5 約瑟夫問題所有代碼
第二章-連結清單
1.連結清單(Linked List)介紹
1.1 記憶體結構
- 連結清單是以節點的方式來存儲的,是鍊式存儲
- 每個節點包含 data 域：存放資料， next 域：指向下一個節點
- 連結清單的各個節點不一定是連續存儲，比如a1的位址是150，而next指向的a2位址是110
- 連結清單分帶頭節點的連結清單和沒有頭節點的連結清單
1.2 邏輯結構
連結清單的邏輯結構雖然看起來像是連續的，但實際上的結構如1.1的記憶體結構所示，連結清單的存儲空間是不連續的
2.連結清單的應用場景
使用帶head頭的單向連結清單實作 –水浒英雄排行榜管理
完成對英雄人物的增删改查操作
第一種方法在添加英雄時，直接添加到連結清單的尾部
第二種方式在添加英雄時，根據排名将英雄插入到指定位置(如果有這個排名，則添加失敗，并給出提示) 2.1 直接插傳入連結表
//第一種方法在添加英雄時，直接添加到連結清單的尾部
public class SingleLinkedListDemo {
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();
// 将Hero對象加傳入連結表
singleLinkedList.add(hero1);
singleLinkedList.add(hero2);
singleLinkedList.add(hero3);
singleLinkedList.add(hero4);
//周遊連結清單并顯示
singleLinkedList.list();
}
}
//定義SingleLinkedList管理我們的英雄
class SingleLinkedList {
//先初始化一個頭節點, 頭節點不要動, 不存放具體的資料
private HeroNode head = new HeroNode(0,"","");
//添加節點到單向連結清單
/**
* 思路，當不考慮編号順序時
* 1.找到目前連結清單的最後節點
* 2.将最後這個節點的next指向新的節點
*/
public void add(HeroNode heroNode){
//因為head節點不能動，是以我們需要一個輔助變量 temp
HeroNode temp = head; //相當于此時的指針指向head節點
//周遊連結清單，找到最後的節點
while (true) {
//找到連結清單的最後一個節點
if(temp.next == null) {
break;
}
//如果沒有找到最後的節點，就将temp後移
temp = temp.next;
}
//當退出while循環時，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;
}
}
}
//定義一個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;
}
// 為了顯示友善，重寫toString方法，注意不要列印next，能夠清晰一點
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
}
} 程式運作結果
HeroNode [no=1, name=宋江, nickName=及時雨]
HeroNode [no=2, name=盧俊義, nickName=玉麒麟]
HeroNode [no=3, name=吳用, nickName=智多星]
HeroNode [no=4, name=林沖, nickName=豹子頭] 2.2 按順序插傳入連結表
第二種方式在添加英雄時，根據排名将英雄插入到指定位置(如果有這個排名，則添加失敗，并給出提示)
public class SingleLinkedListDemo {
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(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
//周遊連結清單并顯示
singleLinkedList.list();
}
}
//定義SingleLinkedList管理我們的英雄
class SingleLinkedList {
//先初始化一個頭節點, 頭節點不要動, 不存放具體的資料
private HeroNode head = new HeroNode(0,"","");
// 第二種方式在添加英雄時，根據排名将英雄插入到指定位置
// (如果有這個排名，則添加失敗，并給出提示)
public void addByOrder(HeroNode heroNode) {
// 因為頭節點不能動，是以我們仍然通過一個輔助指針(變量)來幫助找到添加的位置
// 因為是單連結清單，是以我們找的temp 是位于 添加位置的前一個節點，否則插入不了
HeroNode temp = head;
boolean flag = false; // 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) {// 說明希望添加的heroNode的編号已然存在
flag = true; // 說明編号存在
break;
}
temp = temp.next; // 後移，周遊目前連結清單
}
// 判斷flag 的值
if (flag) { // 如果flag為true，不能添加，說明編号存在
System.out.printf("準備插入的英雄的編号 %d 已經存在了, 不能加入\n", heroNode.no);
} else {
// 插入到連結清單中, temp的後面
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;
}
}
}
//定義一個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;
}
// 為了顯示友善，重寫toString方法，注意不要列印next，能夠清晰一點
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
}
} 程式運作結果
HeroNode [no=1, name=宋江, nickName=及時雨]
HeroNode [no=2, name=盧俊義, nickName=玉麒麟]
HeroNode [no=3, name=吳用, nickName=智多星]
HeroNode [no=4, name=林沖, nickName=豹子頭] 2.3 修改單連結清單的節點資訊
思路
(1) 先找到該節點，通過周遊
(2) temp.name = newHeroNode.name ;
temp.nickname= newHeroNode.nickname public class SingleLinkedListDemo {
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();
// 将Hero對象加傳入連結表
// singleLinkedList.add(hero1);
// singleLinkedList.add(hero2);
// singleLinkedList.add(hero3);
// singleLinkedList.add(hero4);
//加入按照編号的順序
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
System.out.println("修改前的連結清單情況:");
singleLinkedList.list();
// 測試修改節點的代碼
HeroNode newHeroNode = new HeroNode(2, "小盧", "小玉");
singleLinkedList.update(newHeroNode);
System.out.println("修改後的連結清單情況:");
singleLinkedList.list();
}
}
//定義SingleLinkedList管理我們的英雄
class SingleLinkedList {
//先初始化一個頭節點, 頭節點不要動, 不存放具體的資料
private HeroNode head = new HeroNode(0,"","");
//添加節點到單向連結清單
/**
* 思路，當不考慮編号順序時
* 1.找到目前連結清單的最後節點
* 2.将最後這個節點的next指向新的節點
*/
public void add(HeroNode heroNode){
//因為head節點不能動，是以我們需要一個輔助變量 temp
HeroNode temp = head; //相當于此時的指針指向head節點
//周遊連結清單，找到最後的節點
while (true) {
//找到連結清單的最後一個節點
if(temp.next == null) {
break;
}
//如果沒有找到最後的節點，就将temp後移
temp = temp.next;
}
//當退出while循環時，temp就指向了連結清單的最後
//将最後這個節點的next指向新的節點
temp.next = heroNode;
}
// 第二種方式在添加英雄時，根據排名将英雄插入到指定位置
// (如果有這個排名，則添加失敗，并給出提示)
public void addByOrder(HeroNode heroNode) {
// 因為頭節點不能動，是以我們仍然通過一個輔助指針(變量)來幫助找到添加的位置
// 因為是單連結清單，是以我們找的temp 是位于 添加位置的前一個節點，否則插入不了
HeroNode temp = head;
boolean flag = false; // 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) {// 說明希望添加的heroNode的編号已然存在
flag = true; // 說明編号存在
break;
}
temp = temp.next; // 後移，周遊目前連結清單
}
// 判斷flag 的值
if (flag) { // 如果flag為true，不能添加，說明編号存在
System.out.printf("準備插入的英雄的編号 %d 已經存在了, 不能加入\n", heroNode.no);
} else {
// 插入到連結清單中, temp的後面
heroNode.next = temp.next;
temp.next = heroNode;
}
}
// 修改節點的資訊, 根據no編号來修改，即no編号不能改.
// 說明
// 1. 根據 newHeroNode 的 no編号 來修改即可
public void update(HeroNode newHeroNode) {
// 判斷是否空
if (head.next == null) {
System.out.println("連結清單為空~");
return;
}
// 找到需要修改的節點, 根據no編号查找
// 定義一個輔助變量
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.printf("沒有找到 編号為 %d 的節點，不能修改\n", newHeroNode.no);
}
}
// 顯示連結清單[周遊連結清單]
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;
}
// 為了顯示友善，重寫toString方法，注意不要列印next，能夠清晰一點
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]"; 程式運作結果
修改前的連結清單情況:
HeroNode [no=1, name=宋江, nickName=及時雨]
HeroNode [no=2, name=盧俊義, nickName=玉麒麟]
HeroNode [no=3, name=吳用, nickName=智多星]
HeroNode [no=4, name=林沖, nickName=豹子頭]
修改後的連結清單情況:
HeroNode [no=1, name=宋江, nickName=及時雨]
HeroNode [no=2, name=小盧, nickName=小玉]
HeroNode [no=3, name=吳用, nickName=智多星]
HeroNode [no=4, name=林沖, nickName=豹子頭] 2.4 删除單連結清單的節點
public class SingleLinkedListDemo {
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();
// 将Hero對象加傳入連結表
// singleLinkedList.add(hero1);
// singleLinkedList.add(hero2);
// singleLinkedList.add(hero3);
// singleLinkedList.add(hero4);
//加入按照編号的順序
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
System.out.println("修改前的連結清單情況:");
singleLinkedList.list();
// 測試修改節點的代碼
HeroNode newHeroNode = new HeroNode(2, "小盧", "小玉");
singleLinkedList.update(newHeroNode);
System.out.println("修改後的連結清單情況:");
singleLinkedList.list();
//删除節點
singleLinkedList.del(1);
singleLinkedList.del(4);
System.out.println("删除後的連結清單情況:");
singleLinkedList.list();
}
}
//定義SingleLinkedList管理我們的英雄
class SingleLinkedList {
//先初始化一個頭節點, 頭節點不要動, 不存放具體的資料
private HeroNode head = new HeroNode(0,"","");
//添加節點到單向連結清單
/**
* 思路，當不考慮編号順序時
* 1.找到目前連結清單的最後節點
* 2.将最後這個節點的next指向新的節點
*/
public void add(HeroNode heroNode){
//因為head節點不能動，是以我們需要一個輔助變量 temp
HeroNode temp = head; //相當于此時的指針指向head節點
//周遊連結清單，找到最後的節點
while (true) {
//找到連結清單的最後一個節點
if(temp.next == null) {
break;
}
//如果沒有找到最後的節點，就将temp後移
temp = temp.next;
}
//當退出while循環時，temp就指向了連結清單的最後
//将最後這個節點的next指向新的節點
temp.next = heroNode;
}
// 第二種方式在添加英雄時，根據排名将英雄插入到指定位置
// (如果有這個排名，則添加失敗，并給出提示)
public void addByOrder(HeroNode heroNode) {
// 因為頭節點不能動，是以我們仍然通過一個輔助指針(變量)來幫助找到添加的位置
// 因為是單連結清單，是以我們找的temp 是位于 添加位置的前一個節點，否則插入不了
HeroNode temp = head;
boolean flag = false; // 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) {// 說明希望添加的heroNode的編号已然存在
flag = true; // 說明編号存在
break;
}
temp = temp.next; // 後移，周遊目前連結清單
}
// 判斷flag 的值
if (flag) { // 如果flag為true，不能添加，說明編号存在
System.out.printf("準備插入的英雄的編号 %d 已經存在了, 不能加入\n", heroNode.no);
} else {
// 插入到連結清單中, temp的後面
heroNode.next = temp.next;
temp.next = heroNode;
}
}
// 修改節點的資訊, 根據no編号來修改，即no編号不能改.
// 說明
// 1. 根據 newHeroNode 的 no編号 來修改即可
public void update(HeroNode newHeroNode) {
// 判斷是否空
if (head.next == null) {
System.out.println("連結清單為空~");
return;
}
// 找到需要修改的節點, 根據no編号查找
// 定義一個輔助變量
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.printf("沒有找到 編号為 %d 的節點，不能修改\n", newHeroNode.no);
}
}
// 删除節點
// 思路
// 1. head節點 不能動，是以我們需要一個temp輔助節點(指針)找到待删除節點的前一個節點
// 2. 我們在比較時，是temp.next.no 和 需要删除的節點的no比較
public void del(int no) {
HeroNode temp = head;
boolean flag = false; // 辨別是否找到待删除節點的前一個節點
while (true) {
if (temp.next == null) { // 已經周遊到連結清單的最後
break;
}
if (temp.next.no == no) {
// 找到 待删除節點的前一個節點temp
flag = true;
break;
}
temp = temp.next; // temp後移，周遊
}
// 判斷flag
if (flag) { // 找到
// 可以删除
temp.next = temp.next.next;
} else {
System.out.printf("要删除的 %d 節點不存在\n", no);
}
}
// 顯示連結清單[周遊連結清單]
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;
}
// 為了顯示友善，重寫toString方法，注意不要列印next，能夠清晰一點
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
}
} 程式運作結果
修改前的連結清單情況:
HeroNode [no=1, name=宋江, nickName=及時雨]
HeroNode [no=2, name=盧俊義, nickName=玉麒麟]
HeroNode [no=3, name=吳用, nickName=智多星]
HeroNode [no=4, name=林沖, nickName=豹子頭]
修改後的連結清單情況:
HeroNode [no=1, name=宋江, nickName=及時雨]
HeroNode [no=2, name=小盧, nickName=小玉]
HeroNode [no=3, name=吳用, nickName=智多星]
HeroNode [no=4, name=林沖, nickName=豹子頭]
删除後的連結清單情況:
HeroNode [no=2, name=小盧, nickName=小玉]
HeroNode [no=3, name=吳用, nickName=智多星] 3.單連結清單的常見面試題
3.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(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
//删除節點
singleLinkedList.del(1);
singleLinkedList.del(4);
// 測試一下 求單連結清單中有效節點的個數
System.out.println("有效的節點個數=" + getLength(singleLinkedList.getHead()));// 2
} 程式運作結果
有效的節點個數=2 3.2 查找單連結清單中的倒數第k個節點[新浪面試題]
public class SingleLinkedListDemo {
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();
// 将Hero對象加傳入連結表
// singleLinkedList.add(hero1);
// singleLinkedList.add(hero2);
// singleLinkedList.add(hero3);
// singleLinkedList.add(hero4);
//加入按照編号的順序
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
System.out.println("修改前的連結清單情況:");
singleLinkedList.list();
// 測試修改節點的代碼
HeroNode newHeroNode = new HeroNode(2, "小盧", "小玉");
singleLinkedList.update(newHeroNode);
System.out.println("修改後的連結清單情況:");
singleLinkedList.list();
//删除節點
singleLinkedList.del(1);
singleLinkedList.del(4);
System.out.println("删除後的連結清單情況:");
singleLinkedList.list();
// 測試一下 求單連結清單中有效節點的個數
System.out.println("有效的節點個數=" + getLength(singleLinkedList.getHead()));// 2
// 測試一下看看是否得到了倒數第K個節點
HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 2);
System.out.println("res=" + res);
}
//方法：擷取單連結清單有效節點的個數(如果是帶頭結點的連結清單，需求不統計頭節點)
/**
* @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;
}
// 查找單連結清單中的倒數第k個結點
// 思路
// 1. 編寫一個方法，接收head節點，同時接收一個index
// 2. index 表示 倒數第index個節點
// 3. 先把連結清單從頭到尾周遊，得到連結清單的總長度 getLength
// 4. 得到size 後，我們從連結清單的第一個開始周遊 (size-index)個，就可以得到
// 5. 如果找到了，則傳回該節點，否則傳回nulll
public static HeroNode findLastIndexNode(HeroNode head, int index) {
// 判斷如果連結清單為空，傳回null
if (head.next == null) { //連結清單為空
return null;// 沒有找到
}
// 第一次周遊得到連結清單的長度(節點個數)
int size = getLength(head);
// 第二次周遊到 (size-index) 的位置，就是我們倒數的第K個節點
// 先做一個index的校驗
if (index <= 0 || index > size) {
return null;
}
// 定義輔助變量 cur， for循環定位到倒數的index
HeroNode cur = head.next;
for (int i = 0; i < size - index; i++) {
cur = cur.next;
}
return cur;
}
}
//定義SingleLinkedList管理我們的英雄
class SingleLinkedList {
//先初始化一個頭節點, 頭節點不要動, 不存放具體的資料
private HeroNode head = new HeroNode(0,"","");
//傳回頭結點head
public HeroNode getHead() {
return head;
}
//添加節點到單向連結清單
/**
* 思路，當不考慮編号順序時
* 1.找到目前連結清單的最後節點
* 2.将最後這個節點的next指向新的節點
*/
public void add(HeroNode heroNode){
//因為head節點不能動，是以我們需要一個輔助變量 temp
HeroNode temp = head; //相當于此時的指針指向head節點
//周遊連結清單，找到最後的節點
while (true) {
//找到連結清單的最後一個節點
if(temp.next == null) {
break;
}
//如果沒有找到最後的節點，就将temp後移
temp = temp.next;
}
//當退出while循環時，temp就指向了連結清單的最後
//将最後這個節點的next指向新的節點
temp.next = heroNode;
}
// 第二種方式在添加英雄時，根據排名将英雄插入到指定位置
// (如果有這個排名，則添加失敗，并給出提示)
public void addByOrder(HeroNode heroNode) {
// 因為頭節點不能動，是以我們仍然通過一個輔助指針(變量)來幫助找到添加的位置
// 因為是單連結清單，是以我們找的temp 是位于 添加位置的前一個節點，否則插入不了
HeroNode temp = head;
boolean flag = false; // 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) {// 說明希望添加的heroNode的編号已然存在
flag = true; // 說明編号存在
break;
}
temp = temp.next; // 後移，周遊目前連結清單
}
// 判斷flag 的值
if (flag) { // 如果flag為true，不能添加，說明編号存在
System.out.printf("準備插入的英雄的編号 %d 已經存在了, 不能加入\n", heroNode.no);
} else {
// 插入到連結清單中, temp的後面
heroNode.next = temp.next;
temp.next = heroNode;
}
}
// 修改節點的資訊, 根據no編号來修改，即no編号不能改.
// 說明
// 1. 根據 newHeroNode 的 no編号 來修改即可
public void update(HeroNode newHeroNode) {
// 判斷是否空
if (head.next == null) {
System.out.println("連結清單為空~");
return;
}
// 找到需要修改的節點, 根據no編号查找
// 定義一個輔助變量
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.printf("沒有找到 編号為 %d 的節點，不能修改\n", newHeroNode.no);
}
}
// 删除節點
// 思路
// 1. head節點 不能動，是以我們需要一個temp輔助節點(指針)找到待删除節點的前一個節點
// 2. 我們在比較時，是temp.next.no 和 需要删除的節點的no比較
public void del(int no) {
HeroNode temp = head;
boolean flag = false; // 辨別是否找到待删除節點的前一個節點
while (true) {
if (temp.next == null) { // 已經周遊到連結清單的最後
break;
}
if (temp.next.no == no) {
// 找到 待删除節點的前一個節點temp
flag = true;
break;
}
temp = temp.next; // temp後移，周遊
}
// 判斷flag
if (flag) { // 找到
// 可以删除
temp.next = temp.next.next;
} else {
System.out.printf("要删除的 %d 節點不存在\n", no);
}
}
// 顯示連結清單[周遊連結清單]
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;
}
// 為了顯示友善，重寫toString方法，注意不要列印next，能夠清晰一點
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
}
} 測試運作結果
修改前的連結清單情況:
HeroNode [no=1, name=宋江, nickName=及時雨]
HeroNode [no=2, name=盧俊義, nickName=玉麒麟]
HeroNode [no=3, name=吳用, nickName=智多星]
HeroNode [no=4, name=林沖, nickName=豹子頭]
修改後的連結清單情況:
HeroNode [no=1, name=宋江, nickName=及時雨]
HeroNode [no=2, name=小盧, nickName=小玉]
HeroNode [no=3, name=吳用, nickName=智多星]
HeroNode [no=4, name=林沖, nickName=豹子頭]
删除後的連結清單情況:
HeroNode [no=2, name=小盧, nickName=小玉]
HeroNode [no=3, name=吳用, nickName=智多星]
有效的節點個數=2
res=HeroNode [no=2, name=小盧, nickName=小玉] 3.3 單連結清單的反轉[騰訊面試題,有點難度]
public class SingleLinkedListDemo {
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();
// 将Hero對象加傳入連結表
singleLinkedList.add(hero1);
singleLinkedList.add(hero4);
singleLinkedList.add(hero2);
singleLinkedList.add(hero3);
// 測試一下單連結清單的反轉功能
System.out.println("原來連結清單的情況:");
singleLinkedList.list();
System.out.println("反轉單連結清單:");
reversetList(singleLinkedList.getHead());
singleLinkedList.list();
}
//将單連結清單進行反轉
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;
}
}
//定義SingleLinkedList管理我們的英雄
class SingleLinkedList {
//先初始化一個頭節點, 頭節點不要動, 不存放具體的資料
private HeroNode head = new HeroNode(0,"","");
//傳回頭結點head
public HeroNode getHead() {
return head;
}
//添加節點到單向連結清單
/**
* 思路，當不考慮編号順序時
* 1.找到目前連結清單的最後節點
* 2.将最後這個節點的next指向新的節點
*/
public void add(HeroNode heroNode){
//因為head節點不能動，是以我們需要一個輔助變量 temp
HeroNode temp = head; //相當于此時的指針指向head節點
//周遊連結清單，找到最後的節點
while (true) {
//找到連結清單的最後一個節點
if(temp.next == null) {
break;
}
//如果沒有找到最後的節點，就将temp後移
temp = temp.next;
}
//當退出while循環時，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;
}
}
}
//定義一個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;
}
// 為了顯示友善，重寫toString方法，注意不要列印next，能夠清晰一點
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
}
} 程式運作結果
原來連結清單的情況:
HeroNode [no=1, name=宋江, nickName=及時雨]
HeroNode [no=4, name=林沖, nickName=豹子頭]
HeroNode [no=2, name=盧俊義, nickName=玉麒麟]
HeroNode [no=3, name=吳用, nickName=智多星]
反轉單連結清單:
HeroNode [no=3, name=吳用, nickName=智多星]
HeroNode [no=2, name=盧俊義, nickName=玉麒麟]
HeroNode [no=4, name=林沖, nickName=豹子頭]
HeroNode [no=1, name=宋江, nickName=及時雨] 3.4 從尾到頭列印單連結清單[百度面試題]
//示範棧Stack的基本使用
public class TestStack {
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
//入棧操作
stack.add("jack");
stack.add("tom");
stack.add("smith");
//出棧
while (stack.size() > 0) {
System.out.println(stack.pop());//pop就是将棧頂的資料取出
}
}
} 程式運作結果
smith
tom
jack public class SingleLinkedListDemo {
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();
// 将Hero對象加傳入連結表
singleLinkedList.add(hero1);
singleLinkedList.add(hero4);
singleLinkedList.add(hero2);
singleLinkedList.add(hero3);
System.out.println("原來連結清單的情況:");
singleLinkedList.list();
System.out.println("測試逆序列印單連結清單, 沒有改變連結清單的結構");
reversePrint(singleLinkedList.getHead());
}
// 使用方式2：
// 可以利用棧這個資料結構，将各個節點壓入到棧中，然後利用棧的先進後出的特點，就實作了逆序列印的效果
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 = cur.next; // cur後移，這樣就可以壓入下一個節點
}
// 将棧中的節點進行列印,pop 出棧
while (stack.size() > 0) {
System.out.println(stack.pop()); // stack的特點是先進後出
}
}
//定義SingleLinkedList管理我們的英雄
class SingleLinkedList {
//先初始化一個頭節點, 頭節點不要動, 不存放具體的資料
private HeroNode head = new HeroNode(0,"","");
//傳回頭結點head
public HeroNode getHead() {
return head;
}
//添加節點到單向連結清單
/**
* 思路，當不考慮編号順序時
* 1.找到目前連結清單的最後節點
* 2.将最後這個節點的next指向新的節點
*/
public void add(HeroNode heroNode){
//因為head節點不能動，是以我們需要一個輔助變量 temp
HeroNode temp = head; //相當于此時的指針指向head節點
//周遊連結清單，找到最後的節點
while (true) {
//找到連結清單的最後一個節點
if(temp.next == null) {
break;
}
//如果沒有找到最後的節點，就将temp後移
temp = temp.next;
}
//當退出while循環時，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;
}
}
}
//定義一個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;
}
// 為了顯示友善，重寫toString方法，注意不要列印next，能夠清晰一點
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
}
} 程式運作結果
原來連結清單的情況:
HeroNode [no=1, name=宋江, nickName=及時雨]
HeroNode [no=4, name=林沖, nickName=豹子頭]
HeroNode [no=2, name=盧俊義, nickName=玉麒麟]
HeroNode [no=3, name=吳用, nickName=智多星]
測試逆序列印單連結清單, 沒有改變連結清單的結構
HeroNode [no=3, name=吳用, nickName=智多星]
HeroNode [no=2, name=盧俊義, nickName=玉麒麟]
HeroNode [no=4, name=林沖, nickName=豹子頭]
HeroNode [no=1, name=宋江, nickName=及時雨] 3.5 合并兩個有序的單連結清單，合并之後的連結清單仍然有序
public class MergeList {
public static void main(String[] args) {
SingleLinkedList list1 = new SingleLinkedList();
list1.add(new Node(1));
list1.add(new Node(3));
list1.add(new Node(5));
list1.add(new Node(7));
list1.add(new Node(9));
SingleLinkedList list2 = new SingleLinkedList();
list2.add(new Node(2));
list2.add(new Node(4));
list2.add(new Node(6));
list2.add(new Node(6));
list2.add(new Node(8));
list2.add(new Node(10));
list2.add(new Node(11));
list2.add(new Node(12));
// 合并連結清單
SingleLinkedList mergeList = merge(list1.head, list2.head);
System.out.println("合并後的連結清單如下:");
mergeList.show();
}
public static SingleLinkedList merge(Node head1,Node head2) {
//建立新連結清單的頭結點
Node head = new Node(0);
SingleLinkedList mergeList = new SingleLinkedList();
mergeList.head = head;
Node temp = head;
Node temp1 = head1.next;
Node temp2 = head2.next;
while (temp1 != null && temp2 != null) {
if(temp1.data <= temp2.data) {
temp.next = temp1;
temp1 = temp1.next;
}else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
while (temp1 != null) {
temp.next = temp1;
temp1 = temp1.next;
}
while (temp2 != null) {
temp.next = temp2;
temp2 = temp2.next;
}
return mergeList;
}
}
//定義連結清單管理節點
class SingleLinkedList {
//首先定義一個頭結點，頭節點不要動, 不存放具體的資料
Node head = new Node(0);
//添加節點到單連結清單，要求排好序，如果資料相等，則直接插入
public void add(Node node) {
//定義一個指針
Node temp = head;
while (true) {
if(temp.next == null) { //說明temp已經在連結清單的最後
//直接在temp的後面插入節點
temp.next = node;
break;
}
if (temp.next.data > node.data) {
// 插入到連結清單中, temp的後面
node.next = temp.next;
temp.next = node;
break;
}else if (temp.next.data == node.data) {
//如果要添加的資料與temp的下一個節點的資料相等
//就直接在temp的下一個節點的後面插入即可
temp.next.next = node;
break;
}
temp = temp.next; // 後移，周遊目前連結清單
}
}
//周遊連結清單
public void show() {
// 判斷連結清單是否為空
if (head.next == null) {
System.out.println("連結清單為空");
return;
}
//因為頭節點不能動，是以我們需要一個輔助變量來周遊
Node temp = head.next; //輔助變量指向第一個節點
while (true) {
// 判斷是否到連結清單最後
if (temp == null) {
break;
}
// 輸出節點的資訊
System.out.println(temp);
// 将temp後移，一定要記得後移
temp = temp.next;
}
}
}
//建立節點類
class Node {
public Integer data; //資料
public Node next; //指向下一個節點
public Node(Integer data) {
this.data = data;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
} 程式運作結果
合并後的連結清單如下:
Node{data=1}
Node{data=2}
Node{data=3}
Node{data=4}
Node{data=5}
Node{data=6}
Node{data=6}
Node{data=7}
Node{data=8}
Node{data=9}
Node{data=12} 4.雙向連結清單
單向連結清單和雙向連結清單的差別
1.單向連結清單， 查找的方向隻能是一個方向， 而雙向連結清單可以向前或者向後查找
2.單向連結清單不能自我删除， 需要靠輔助節點 ， 而雙向連結清單， 則可以自我删除， 是以前面我們單連結清單删除時節點， 總是找到 temp ，temp 是待删除節點的前一個節點(認真體會) 4.1 連結清單節點的定義
//定義一個HeroNode，每個HeroNode對象就是一個節點
class HeroNode2 {
public int no; //編号
public String name; //名字
public String nickName; //昵稱
public HeroNode2 next; // 指向下一個節點，預設為null
public HeroNode2 pre; // 指向前一個節點，預設為null
//構造器
public HeroNode2(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickName = nickname;
}
// 為了顯示友善，重寫toString方法，注意不要列印next，能夠清晰一點
@Override
public String toString() {
return "HeroNode2 [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
}
} 4.2 雙向連結清單周遊
//周遊雙向連結清單的方法
// 顯示連結清單[周遊連結清單]
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;
}
} 4.3 尾部插入節點
//添加一個節點到雙向連結清單的最後
public void add(HeroNode2 heroNode){
//因為head節點不能動，是以我們需要一個輔助變量 temp
HeroNode2 temp = head; //相當于此時的指針指向head節點
//周遊連結清單，找到最後的節點
while (true) {
//找到連結清單的最後一個節點
if(temp.next == null) {
break;
}
//如果沒有找到最後的節點，就将temp後移
temp = temp.next;
}
//當退出while循環時，temp就指向了連結清單的最後
//形成一個雙向連結清單
temp.next = heroNode;
heroNode.pre = temp;
} 4.4 按順序插入節點
// 第二種方式在添加英雄時，根據排名将英雄插入到指定位置
// (如果有這個排名，則添加失敗，并給出提示)
public void addByOrder(HeroNode2 heroNode) {
// 因為頭節點不能動，是以我們仍然通過一個輔助指針(變量)來幫助找到添加的位置
HeroNode2 temp = head;
boolean flag = false; // 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) {// 說明希望添加的heroNode的編号已然存在
flag = true; // 說明編号存在
break;
}
temp = temp.next; // 後移，周遊目前連結清單
}
// 判斷flag 的值
if (flag) { // 如果flag為true，不能添加，說明編号存在
System.out.printf("準備插入的英雄的編号 %d 已經存在了, 不能加入\n", heroNode.no);
} else {
// 插入到連結清單中, temp的後面
// heroNode 指向 temp 節點的下一個節點
heroNode.next = temp.next;
if(temp.next != null) {
temp.next.pre = heroNode;
}
// temp 節點指向 heroNode 節點
temp.next = heroNode;
heroNode.pre = temp;
}
} 4.5 修改節點資訊
// 修改一個節點的内容, 可以看到雙向連結清單的節點内容修改和單向連結清單一樣
// 隻是 節點類型改成 HeroNode2
public 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; //temp後移
}
// 根據flag 判斷是否找到要修改的節點
if (flag) {
temp.name = newHeroNode.name;
temp.nickName = newHeroNode.nickName;
} else { // 沒有找到
System.out.printf("沒有找到 編号為 %d 的節點，不能修改\n", newHeroNode.no);
}
} 4.6 删除節點
// 從雙向連結清單中删除一個節點,
// 說明
// 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) {
// 找到的待删除節點的前一個節點temp
flag = true;
break;
}
temp = temp.next; // temp後移，周遊
}
// 判斷flag
if (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);
}
} 4.7 雙向連結清單測試結果
雙向連結清單的測試:
HeroNode2 [no=1, name=宋江, nickName=及時雨]
HeroNode2 [no=2, name=盧俊義, nickName=玉麒麟]
HeroNode2 [no=3, name=吳用, nickName=智多星]
HeroNode2 [no=5, name=林沖, nickName=豹子頭]
按順序插入後的情況
HeroNode2 [no=1, name=宋江, nickName=及時雨]
HeroNode2 [no=2, name=盧俊義, nickName=玉麒麟]
HeroNode2 [no=3, name=吳用, nickName=智多星]
HeroNode2 [no=4, name=Heygo, nickName=Heygogo]
HeroNode2 [no=5, name=林沖, nickName=豹子頭]
HeroNode2 [no=6, name=Oneby, nickName=Onebyone]
修改後的連結清單情況:
HeroNode2 [no=1, name=宋江, nickName=及時雨]
HeroNode2 [no=2, name=盧俊義, nickName=玉麒麟]
HeroNode2 [no=3, name=吳用, nickName=智多星]
HeroNode2 [no=4, name=Heygo, nickName=Heygogo]
HeroNode2 [no=5, name=公孫勝, nickName=入雲龍]
HeroNode2 [no=6, name=Oneby, nickName=Onebyone]
删除後的連結清單情況:
HeroNode2 [no=1, name=宋江, nickName=及時雨]
HeroNode2 [no=2, name=盧俊義, nickName=玉麒麟]
HeroNode2 [no=4, name=Heygo, nickName=Heygogo]
HeroNode2 [no=5, name=公孫勝, nickName=入雲龍]
HeroNode2 [no=6, name=Oneby, nickName=Onebyone] 4.8 雙向連結清單所有代碼
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(5, "林沖", "豹子頭");
// 建立一個雙向連結清單
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.add(hero1);
doubleLinkedList.add(hero2);
doubleLinkedList.add(hero3);
doubleLinkedList.add(hero4);
doubleLinkedList.list();
// 測試按需插入
doubleLinkedList.addByOrder(new HeroNode2(4, "Heygo", "Heygogo"));
doubleLinkedList.addByOrder(new HeroNode2(6, "Oneby", "Onebyone"));
System.out.println("按順序插入後的情況");
doubleLinkedList.list();
// 修改
HeroNode2 newHeroNode = new HeroNode2(5, "公孫勝", "入雲龍");
doubleLinkedList.update(newHeroNode);
System.out.println("修改後的連結清單情況:");
doubleLinkedList.list();
// 删除
doubleLinkedList.del(3);
System.out.println("删除後的連結清單情況:");
doubleLinkedList.list();
}
}
//建立一個雙向連結清單的類
class DoubleLinkedList {
//先初始化一個頭節點, 頭節點不要動, 不存放具體的資料
private HeroNode2 head = new HeroNode2(0,"","");
//傳回頭結點head
public HeroNode2 getHead() {
return head;
}
//添加一個節點到雙向連結清單的最後
public void add(HeroNode2 heroNode){
//因為head節點不能動，是以我們需要一個輔助變量 temp
HeroNode2 temp = head; //相當于此時的指針指向head節點
//周遊連結清單，找到最後的節點
while (true) {
//找到連結清單的最後一個節點
if(temp.next == null) {
break;
}
//如果沒有找到最後的節點，就将temp後移
temp = temp.next;
}
//當退出while循環時，temp就指向了連結清單的最後
//形成一個雙向連結清單
temp.next = heroNode;
heroNode.pre = temp;
}
// 第二種方式在添加英雄時，根據排名将英雄插入到指定位置
// (如果有這個排名，則添加失敗，并給出提示)
public void addByOrder(HeroNode2 heroNode) {
// 因為頭節點不能動，是以我們仍然通過一個輔助指針(變量)來幫助找到添加的位置
HeroNode2 temp = head;
boolean flag = false; // 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) {// 說明希望添加的heroNode的編号已然存在
flag = true; // 說明編号存在
break;
}
temp = temp.next; // 後移，周遊目前連結清單
}
// 判斷flag 的值
if (flag) { // 如果flag為true，不能添加，說明編号存在
System.out.printf("準備插入的英雄的編号 %d 已經存在了, 不能加入\n", heroNode.no);
} else {
// 插入到連結清單中, temp的後面
// heroNode 指向 temp 節點的下一個節點
heroNode.next = temp.next;
if(temp.next != null) {
temp.next.pre = heroNode;
}
// temp 節點指向 heroNode 節點
temp.next = heroNode;
heroNode.pre = temp;
}
}
// 修改一個節點的内容, 可以看到雙向連結清單的節點内容修改和單向連結清單一樣
// 隻是 節點類型改成 HeroNode2
public 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; //temp後移
}
// 根據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) {
// 找到的待删除節點的前一個節點temp
flag = true;
break;
}
temp = temp.next; // temp後移，周遊
}
// 判斷flag
if (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);
}
}
//周遊雙向連結清單的方法
// 顯示連結清單[周遊連結清單]
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;
}
}
}
//定義一個HeroNode，每個HeroNode對象就是一個節點
class HeroNode2 {
public int no; //編号
public String name; //名字
public String nickName; //昵稱
public HeroNode2 next; // 指向下一個節點，預設為null
public HeroNode2 pre; // 指向前一個節點，預設為null
//構造器
public HeroNode2(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickName = nickname;
}
// 為了顯示友善，重寫toString方法，注意不要列印next，能夠清晰一點
@Override
public String toString() {
return "HeroNode2 [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
}
} 5.單向環形連結清單
5.1 單向環形連結清單圖解
5.2 約瑟夫問題
Josephu 問題為： 設編号為 1， 2， … n 的 n 個人圍坐一圈， 約定編号為 k（1<=k<=n） 的人從 1 開始報數， 數到 m 的那個人出列， 它的下一位又從 1 開始報數， 數到 m 的那個人又出列， 依次類推， 直到所有人出列為止， 由此産生一個出隊編号的序列。
思路
用一個不帶頭結點的循環連結清單來處理 Josephu 問題： 先構成一個有 n 個結點的單循環連結清單， 然後由 k 結點起從 1 開始計數， 計到 m 時， 對應結點從連結清單中删除， 然後再從被删除結點的下一個結點又從 1 開始計數， 直到最後一個結點從連結清單中删除算法結束。
5.3 環形連結清單的建構與周遊
5.3.1 Boy 節點的定義
//建立一個Boy類，表示一個節點
class Boy {
private int no; //編号
private Boy next; //指向下一個節點，預設為null
public 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;
}
} 5.3.2 單向循環連結清單的定義
//建立一個環形的單向連結清單
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 節點加到連結清單尾部
boy.setNext(first); // 構成環狀
curBoy = boy; // curBoy 指針後移
}
}
}
// 周遊目前的環形連結清單
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指針後移
}
}
} public static void main(String[] args) {
// 測試一把看看建構環形連結清單，和周遊是否ok
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5);// 加入5個小孩節點
circleSingleLinkedList.showBoy();
} 程式運作結果
小孩的編号 1
小孩的編号 2
小孩的編号 3
小孩的編号 4
小孩的編号 5 5.4 約瑟夫問題代碼實作
//根據使用者的輸入，計算出小孩出圈的順序
/**
* @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 指針同時 移動 countNum - 1, 然後出圈
//這裡是一個循環操作，直到圈中隻有一個節點
while (true) {
if (helper == first) { //說明圈中隻有一個節點
break;
}
//讓 first 和 helper 指針同時 的移動 countNum - 1
for (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());
} public static void main(String[] args) {
// 測試一把看看建構環形連結清單，和周遊是否ok
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5);// 加入5個小孩節點
circleSingleLinkedList.showBoy();
// 測試一把小孩出圈是否正确
circleSingleLinkedList.countBoy(1, 2, 5); // 2->4->1->5->3
} 小孩的編号 1
小孩的編号 2
小孩的編号 3
小孩的編号 4
小孩的編号 5
小孩2出圈
小孩4出圈
小孩1出圈
小孩5出圈
最後留在圈中的小孩編号3 5.5 約瑟夫問題所有代碼
public class Josephu {
public static void main(String[] args) {
// 測試一把看看建構環形連結清單，和周遊是否ok
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5);// 加入5個小孩節點
circleSingleLinkedList.showBoy();
// 測試一把小孩出圈是否正确
circleSingleLinkedList.countBoy(1, 2, 5); // 2->4->1->5->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 節點加到連結清單尾部
boy.setNext(first); // 構成環狀
curBoy = boy; // curBoy 指針後移
}
}
}
// 周遊目前的環形連結清單
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 指針同時 移動 countNum - 1, 然後出圈
//這裡是一個循環操作，直到圈中隻有一個節點
while (true) {
if (helper == first) { //說明圈中隻有一個節點
break;
}
//讓 first 和 helper 指針同時 的移動 countNum - 1
for (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; //指向下一個節點，預設為null
public 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;
}
}