單連結清單的常見題型
- 一、求單連結清單中有效節點的個數
- 二、查找單連結清單中的倒數第k個節點
- 三、單連結清單的反轉
- 四、從尾到頭列印單連結清單（非遞歸）
- 五、完整代碼(帶注釋)
- 六、運作結果
一、求單連結清單中有效節點的個數
代碼如下（示例）：
//方法：擷取到單連結清單的節點的個數（如果是帶頭結點的連結清單，需求出不統計頭節）
/*
* @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個節點
代碼如下（示例）：
//查找單連結清單中的倒數第K個節點
//思路
//1.編寫一個方法，接收head節點，同時接收一個index
//2.index 表示的是倒數第index個節點
//3.先把連結清單從頭到尾周遊，得到連結清單的總的長度getLegth
//4.得到size後，我們從表鍊的第一個開始周遊（size—index）個
//5.如果找到了，則傳回該節點，否則傳回null
public static HeroNode findLastIdexNode(HeroNode head,int index) {
//判斷如果連結清單為空，傳回null
if(head.next == null) {
return null; //沒有找到
}
//第一個周遊得到的連結清單長度（節點個數）
int size = getLength(head);
//第二次周遊size-index 位置，即我們倒數的第k個節點
//先做一個index的效驗（檢查index是否合理）
if(index <= 0 ||index >= size) {
return null;
}
//定義一個輔助變量,for循環定位到倒數的index
HeroNode cur = head.next;
for(int i = 0; i < size - index; i++) {
cur = cur.next;
}
return cur;
}
三、單連結清單的反轉
代碼如下（示例）：
//将單連結清單反轉
public static void reversetList(HeroNode head) {
//如果目前連結清單為空，或者隻有一個節點，無需反轉，直接傳回
if(head.next == null || head.next.next == null) {
return ;
}
//先定義一個輔助的指針（變量），幫助我們周遊原先的連結清單
HeroNode cur = head.next;
HeroNode next = null;
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 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());
}
}
五、完整代碼(帶注釋)
代碼如下（示例）：
package linkedlist;
import java.util.Stack;
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,"林沖","豹子頭");
HeroNode hero5 = new HeroNode(4,"yang","豹子頭");
//建立要給連結清單
SingleLinkedList singleLinkedList = new SingleLinkedList();
//加入
// singleLinkedList.add(hero1);
// singleLinkedList.add(hero2);
// singleLinkedList.add(hero3);
// singleLinkedList.add(hero4);
//有序加入
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero5);
System.out.println("節點數目為："+getLength(singleLinkedList.getHead()));
//顯示
singleLinkedList.list();
HeroNode newHeroNode = new HeroNode(4,"林子","小豹子");
singleLinkedList.updata(newHeroNode);
System.out.println("修改後的資料~~");
singleLinkedList.list();
//删除一個節點
singleLinkedList.del(1);
System.out.println("删除後的連結清單情況~~");
singleLinkedList.list();
System.out.println("節點數目為："+getLength(singleLinkedList.getHead()));
//測試 看是否得到了倒數第k個節點
HeroNode res = findLastIdexNode(singleLinkedList.getHead(),3);
System.out.println("res="+res);
/*
//測試單連結清單的反轉
System.out.println("反轉後的單連結清單：");
reversetList(singleLinkedList.getHead());
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.next; //cur後移，可以壓入下一個節點
}
//将棧中的節點進行列印，pop出棧
while(stack.size() > 0) {
System.out.println(stack.pop());
}
}
//将單連結清單反轉
public static void reversetList(HeroNode head) {
//如果目前連結清單為空，或者隻有一個節點，無需反轉，直接傳回
if(head.next == null || head.next.next == null) {
return ;
}
//先定義一個輔助的指針（變量），幫助我們周遊原先的連結清單
HeroNode cur = head.next;
HeroNode next = null;
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;
}
//查找單連結清單中的倒數第K個節點
//思路
//1.編寫一個方法，接收head節點，同時接收一個index
//2.index 表示的是倒數第index個節點
//3.先把連結清單從頭到尾周遊，得到連結清單的總的長度getLegth
//4.得到size後，我們從表鍊的第一個開始周遊（size—index）個
//5.如果找到了，則傳回該節點，否則傳回null
public static HeroNode findLastIdexNode(HeroNode head,int index) {
//判斷如果連結清單為空，傳回null
if(head.next == null) {
return null; //沒有找到
}
//第一個周遊得到的連結清單長度（節點個數）
int size = getLength(head);
//第二次周遊size-index 位置，即我們倒數的第k個節點
//先做一個index的效驗（檢查index是否合理）
if(index <= 0 ||index >= size) {
return null;
}
//定義一個輔助變量,for循環定位到倒數的index
HeroNode cur = head.next;
for(int i = 0; i < size - index; i++) {
cur = cur.next;
}
return cur;
}
//方法：擷取到單連結清單的節點的個數（如果是帶頭結點的連結清單，需求出不統計頭節）
/*
* @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;
}
}
//定義SingleLinkedList 管理我們的英雄
class SingleLinkedList{
//先初始化一個頭結點，頭結點不要動，不存放具體的資料
private HeroNode head = new HeroNode(0,"","");
public HeroNode getHead() {
return head;
}
//添加節點到單向連結清單
//思路，當不考慮編号順序時
//1.找到目前連結清單的最後節點
//2.将最後這個節點的next 指向 新的節點
public void add(HeroNode heroNode) {
//因為head節點不能動，是以我們需要一個輔助變量 temp
HeroNode temp = 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) {//不能添加，說明編号存在
System.out.printf("準備插入的英雄編号%d已經存在了，不能加入\n",heroNode.no);
}else {
//插入到連結清單中，temp的後面
heroNode.next = temp.next;
temp.next = heroNode;
}
}
//修改節點的資訊，根據no編号來修改，即no編号不能修改
//說明：1.根據newHeroNode的no來修改即可
public void updata(HeroNode newHeroNode) {
//判斷是否為空
if(head.next == 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;
}
//根據flag 判斷是否找到該要修改節點
if(flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
}else {
System.out.println("沒有找到編号%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後移，周遊
}
if(flag) {
temp.next = temp.next.next;
}else {
System.out.println("沒有找到編号%d的節點，不能删除"+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 hNo,String hName,String hNickname) {
this.no = hNo;
this.name = hName;
this.nickname = hNickname;
}
//為了顯示方法，重新toString
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname+ "]";
}
}
六、運作結果
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)