單鏈表進階學習 二段

單鏈表的反轉
思路：

定義一個新節(jié)點，reserveHead=new HeroNode();

利用輔助變量cur遍歷原來的鏈表，每遍歷一個節(jié)點就將其取出，放在新建鏈表的最前端；（這里可能理解上有些難度，舉一個簡單的例子： 首先遍歷到原來鏈表第一個節(jié)點，取出，接到新節(jié)點reserveHead的后面；接著遍歷到原來鏈表的第二個節(jié)點，取出，這個時候把reserveHead的next域指向到新取出的節(jié)點（這里就是原來鏈表的第二個節(jié)點），新取出節(jié)點的next域指向前一個取出的節(jié)點（這里就是原來鏈表的第二個節(jié)點）；這樣就構成了擁有兩個有效節(jié)點的單鏈表的反轉。如果一個單鏈表里有更多的節(jié)點，就按照上述的思路遞歸重復）

把原來鏈表的頭節(jié)點指向新鏈表的第一個節(jié)點head.next=reserveHead.next;

（注：
反轉意味著要將原鏈表破壞，在原鏈表的基礎上打印逆序的鏈表；而不是新建一個鏈表，把原來的節(jié)點直接取出來接在新鏈表頭的后面直接打印出來。這就是上面第三步思路存在的必要性！！！）

public class SingleLinkedListDemo {public static void main(String[] args) {// TODO Auto-generated method stub 第一階段測試代碼// 創(chuàng)建節(jié)點HeroNode hero1 = new HeroNode(1, "呼保義", "宋江");HeroNode hero2 = new HeroNode(2, "玉麒麟", "盧俊義");HeroNode hero3 = new HeroNode(3, "智多星", "吳用");HeroNode hero4 = new HeroNode(4, "入云龍", "公孫勝");HeroNode hero5 = new HeroNode(5, "大刀", "關勝");// 創(chuàng)建單鏈表SingleLinkedList singleLinkedList = new SingleLinkedList();singleLinkedList.add(hero1);singleLinkedList.add(hero2);singleLinkedList.add(hero3);singleLinkedList.add(hero4);singleLinkedList.add(hero5);//測試單鏈表反轉功能// 顯示System.out.println("原鏈表：");singleLinkedList.list();System.out.println();System.out.println("反轉后的鏈表：");reverseList(singleLinkedList.GetHead());singleLinkedList.list();/*// 加入操作// singleLinkedList.add(hero1); // // singleLinkedList.add(hero2); // // singleLinkedList.add(hero3); // // singleLinkedList.add(hero4); // // singleLinkedList.add(hero5);singleLinkedList.addByOrder(hero1);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero3);singleLinkedList.addByOrder(hero5);// 修改操作HeroNode newHeroNode = new HeroNode(5, "寫輪眼", "卡卡西");singleLinkedList.update(newHeroNode);// 顯示System.out.println("刪除前：");singleLinkedList.list();// 修改操作singleLinkedList.del(1);System.out.println("刪除后：");singleLinkedList.list();// 獲取單鏈表節(jié)點的個數(shù)System.out.println(GetNumber(singleLinkedList.GetHead()));HeroNode res = findLastIndexNode(singleLinkedList.GetHead(), 1);// 倒數(shù)第1個System.out.println();System.out.println("單鏈表中倒數(shù)第index個節(jié)點 " + res); */}//反轉鏈表public static void reverseList(HeroNode head) {//老樣子，先判斷鏈表是否為空if(head.next==null||head.next.next==null) {return;}//定義一個輔助變量，幫助遍歷整個鏈表HeroNode cur=head.next;HeroNode next=null;//指向當前節(jié)點【cur】的下一個節(jié)點HeroNode reverseHead= new HeroNode(0, "", "");//遍歷原來的鏈表//遍歷一個節(jié)點就將其取出，放在新建鏈表的最前端while(cur!=null) {next=cur.next;//暫時保存當前節(jié)點的下一個節(jié)點cur.next=reverseHead.next;//cur節(jié)點的下一個節(jié)點指向新鏈表的最前端reverseHead.next=cur;//將cur連接到新的鏈表上cur=next;//cur后移}//將原鏈表的頭節(jié)點的next指向rereverseHead的下一個節(jié)點，實現(xiàn)鏈表的反轉head.next=reverseHead.next;}// 1.查找單鏈表中倒數(shù)第index個節(jié)點// 2.編寫一個方法接收head節(jié)點，同時接受一個index（index數(shù)值代表單鏈表的倒數(shù)第index個節(jié)點）// 3.將鏈表遍歷一遍，得到有效節(jié)點總數(shù)（GetNumber）// 4.單鏈表有效節(jié)點總數(shù)為size，直接遍歷size-index個節(jié)點// 5.如果找到了這個節(jié)點就返回該節(jié)點，否則就返回NULLpublic static HeroNode findLastIndexNode(HeroNode head, int index) {// 如果鏈表為空返回NULLif (head.next == null) {return null;}// 第一次遍歷得到單鏈表的節(jié)點個數(shù)int size = GetNumber(head);// 第二次遍歷單鏈表，這次直接遍歷size-index個節(jié)點，這就是要求的值// 在這里要做一個index的校驗if (index <= 0 || index > size) {return null;}// 定義一個輔助變量，指向第一個有效節(jié)點（頭節(jié)點后的第一個節(jié)點）HeroNode cur = head.next;// for循環(huán)定位到倒數(shù)index個節(jié)點for (int i = 0; i < size - index; i++) {cur = cur.next;}return cur;}//獲取單鏈表節(jié)點的個數(shù)（如果帶頭結點，計數(shù)時要取消頭結點的計數(shù)，因為頭節(jié)點不存儲數(shù)據(jù)）public static int GetNumber(HeroNode head) {if (head.next == null) {return 0;}int number = 0;// 定義一個輔助變量HeroNode cur = head.next;// 這里就是沒有統(tǒng)計頭結點的微操作while (cur != null) {number++;cur = cur.next;}return number;} }//定義一個SingleLinkedList(單鏈表)，管理英雄 class SingleLinkedList {// 一開始要初始化一個頭節(jié)點，保持不動否則會找不到剩下的節(jié)點，***不存放具體數(shù)據(jù)private HeroNode head = new HeroNode(0, "", "");// no初始化為0，姓名和稱號也不寫// 返回頭節(jié)點public HeroNode GetHead() {return head;}// 添加節(jié)點到單向鏈表// 當不考慮編號順序時：// 把節(jié)點添加進去的操作是首先找到當前鏈表的最后一個節(jié)點，next域原本是NULL，要把next域指向新添的節(jié)點public void add(HeroNode heroNode) {// 由于頭節(jié)點不能動，所以需要輔助變量HeroNode temp = head;// temp是輔助變量一開始指向頭節(jié)點，因為單向鏈表不是順序存儲，所以每一次找最后一個節(jié)點都需要遍歷整個鏈表// 開始遍歷while (true) {// 死循環(huán)if (temp.next == null) {// 找到鏈表的尾節(jié)點了break;}// 如果當前節(jié)點不是末節(jié)點// temp后移一位temp = temp.next;// 要清楚temp是一個移動輔助變量，每遍歷到一個不是尾節(jié)點的點temp就會指向當前節(jié)點的下一個節(jié)點}// 當退出這個死循環(huán)的時候，temp就指向了單鏈表的尾節(jié)點// 這個時候就可以把尾節(jié)點的next域指向傳入的新節(jié)點，這個新傳入的節(jié)點就連上了temp.next = heroNode;}// 增添節(jié)點，按照順序顯示出來// 如果已經(jīng)有這個編號，則添加失敗并給出提示public void addByOrder(HeroNode heroNode) {// heroNode為傳入的新節(jié)點// 由于頭節(jié)點不能動，所以需要輔助變量// 單鏈表要添加節(jié)點，temp一定是指向要插入位置的前一個節(jié)點，然后temp.next就指向新節(jié)點，這樣第一步就完成了HeroNode temp = head;boolean flag = false;// 判斷要添加的節(jié)點是否已存在while (true) {if (temp.next == null) {break;}if (temp.next.no > heroNode.no) {break;} else if (temp.next.no == heroNode.no) {flag = true;// 說明已經(jīng)有了break;} else {temp = temp.next;// 如果上述情況都不符合的話，那么繼續(xù)遍歷找下一個節(jié)點}}// 退出循環(huán)的時候要看flag的值if (flag) {System.out.printf("已有編號%d，添加失敗~~~\n", heroNode.no);} else {// 可以插入到鏈表中，temp后移heroNode.next = temp.next;// 新節(jié)點的next域指向下一個節(jié)點temp.next = heroNode;// 前一個節(jié)點的next域指向新節(jié)點}}//修改節(jié)點的信息// 根據(jù)編號no來修改稱號和姓名，編號no不動（如果編號改變就相當于添加操作了）public void update(HeroNode newHeroNode) {// 判斷鏈表是否為空if (head.next == null) {System.out.println("鏈表為空~~~");return;}// 找到需要修改的節(jié)點// 根據(jù)編號no來修改節(jié)點信息// 定義一個輔助變量HeroNode temp = head.next;boolean flag = false;// 標識是否找到這個節(jié)點while (true) {if (temp == null) {// 這里和之前不一樣，表示已經(jīng)遍歷完這個鏈表了（無殘留，去干凈）break;} else if (temp.no == newHeroNode.no) {// 表示已經(jīng)找到要刪除的節(jié)點flag = true;break;}temp = temp.next;}// 退出循環(huán)以后，根據(jù)flag的值來判斷if (flag) {// flag=true；表示找到了要修改的點temp.name = newHeroNode.name;temp.nickname = newHeroNode.nickname;}// 還有一種情況就是沒有找到要修改的點else {System.out.println();System.out.printf("沒有找到編號為%d 的好漢，不能刪除😔\n");}}//刪除節(jié)點/** 1.由于頭節(jié)點不能動，所以需要輔助變量，需要用輔助變量temp找到待刪除節(jié)點的前一個節(jié)點 比較時使用temp.next.no和待刪除節(jié)點的編號no比較**/public void del(int no) {HeroNode temp = head;// 因為需要找到目標節(jié)點的前一個節(jié)點，所以這里不能把輔助節(jié)點定義為頭節(jié)點之后第一個節(jié)點boolean flag = false;while (true) {if (temp.next == null) {// 到鏈表最后，最后一個節(jié)點的后面break;} else if (temp.next.no == no) {// 找到前一個節(jié)點flag = true;break;}temp = temp.next;// 每遍歷一個節(jié)點就后移一位}if (flag) {// 找到了前一個節(jié)點// 刪除操作temp.next = temp.next.next;} else {System.out.println();System.out.printf("刪除的數(shù)據(jù)%d不存在呀不存在~~~\n", no);}}// 顯示單向鏈表public void list() {// 首先判斷鏈表是否為空if (head.next == null) {System.out.println("鏈表為空~~~");return;}// 如果能進行到下面這一步就說明鏈表不為空，至少有一個節(jié)點// 由于頭節(jié)點不能動，所以需要輔助變量HeroNode temp = head.next;// 至少有一個節(jié)點，所以就把輔助變量指向頭節(jié)點后的第一個節(jié)點while (true) {// 死循環(huán)if (temp == null) {// 找到鏈表的尾節(jié)點了break;}// 如果當前節(jié)點不是末節(jié)點System.out.println();System.out.printf("%-6s",temp);// 因為之前已經(jīng)重寫過toString方法了，所以這里直接打印輸出就行了// ************// 下面這點很重要，每打印輸出一個節(jié)點，就需要將輔助變量temp后移，否則的話后果就是一直輸出一個值而且是個死循環(huán)temp = temp.next;}}}//定義HeroNode，每個HeroNode都是一個節(jié)點 class HeroNode {public int no;// 定義編號public String name;// 定義姓名public String nickname;// 定義稱號public HeroNode next;// 定義next域，指向下一個節(jié)點// 建一個構造器public HeroNode(int no, String nickname, String name) {this.no = no;this.nickname = nickname;this.name = name;}// 為了便于顯示，重寫toString方法/** @Override是偽代碼,表示重寫。(當然不寫@Override也可以)，不過寫上有如下好處: 1、可以當注釋用,方便閱讀；* 2、編譯器可以給你驗證@Override下面的方法名是否是你父類中所有的，如果沒有則報錯。* 例如，你如果沒寫@Override，而你下面的方法名又寫錯了，這時你的編譯器是可以編譯通 過的，因為編譯器以為這個方法是你的子類中自己增加的方法。*/@Overridepublic String toString() {return "no= " + no + "，nickname= " + nickname + "，name = " + name;}}

總結

以上是生活随笔為你收集整理的单链表进阶学习 二段的全部內容，希望文章能夠幫你解決所遇到的問題。

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