單鏈表進階學(xué)習(xí) 三段

從尾到頭打印單鏈表：

思路：

實際意義就是逆序打印單鏈表；

利用棧的操作，先進后出，實現(xiàn)逆序打印效果。

（注：不建議直接對單鏈表進行反轉(zhuǎn)操作。這樣會破壞鏈表本身的結(jié)構(gòu)，在做題和練習(xí)的時候可以嘗試，但在工作中考慮到鏈表的重復(fù)使用，最好習(xí)慣使用棧數(shù)據(jù)結(jié)構(gòu)的思想來操作）

---

演示棧：

要單個取出棧元素的操作

import java.util.Stack;public class TextStackDemo {// 演示棧的操作public static void main(String[] args) {// TODO Auto-generated method stub// 輸入“new stack()”,快捷鍵“ctrl+1”Stack<String> stack = new Stack<>();// 新建一個stack棧,標注鍵入String類型的數(shù)據(jù)// 入棧stack.add("1");//可以用push();stack.add("2");stack.add("3");// 鍵入棧stack三個string類型的數(shù)據(jù)// 入棧完成// 出棧// pop()直接代表出棧操作System.out.println(stack.pop());// 一次操作出棧一個數(shù)據(jù)} }

2.將棧元素一次性取出的操作

import java.util.Stack;public class TextStackDemo {// 演示棧的操作public static void main(String[] args) {// TODO Auto-generated method stub// 輸入“new stack()”,快捷鍵“ctrl+1”Stack<String> stack = new Stack<>();// 新建一個stack棧,標注鍵入String類型的數(shù)據(jù)// 入棧stack.add("1");stack.add("2");stack.add("3");// 鍵入棧stack三個string類型的數(shù)據(jù)// 入棧完成// 出棧// pop()直接代表出棧操作while (stack.size() > 0) {System.out.println(stack.pop());// 一次操作出棧一個數(shù)據(jù)}} }

---

接下來進入正題：

用棧的思想解決單鏈表的逆序打印：

import java.util.Stack;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, "大刀", "關(guān)勝");// 創(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("逆序輸出的鏈表：");reversePrint(singleLinkedList.GetHead());/** //測試單鏈表反轉(zhuǎn)功能 // 顯示 System.out.println("原鏈表："); singleLinkedList.list();* * System.out.println(); System.out.println("反轉(zhuǎn)后的鏈表：");* 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 reversePrint(HeroNode head) {if (head.next == null) {return;// 空鏈表，無法打印}// 創(chuàng)建一個棧，將各節(jié)點壓入棧中Stack<HeroNode> stack = new Stack<HeroNode>();HeroNode cur = head.next;// 遍歷需要的輔助變量while (cur != null) {stack.push(cur);cur = cur.next;// 后移，好壓入下一個節(jié)點}// 出棧while (stack.size() > 0) {System.out.println(stack.pop());}}// 反轉(zhuǎn)鏈表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)鏈表的反轉(zhuǎ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ù)（如果帶頭結(jié)點，計數(shù)時要取消頭結(jié)點的計數(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)計頭結(jié)點的微操作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(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é)點// 建一個構(gòu)造器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;}}

合并兩個單鏈表，依照順序打印輸出：

思路：

創(chuàng)建一個新的單鏈表；

依次遍歷兩個原來的單鏈表，每遍歷一次取出一個最小的節(jié)點接到新鏈表之后。

public class LinkedListConbine {public static void main(String[] args) {SingleLinkedList4 singleLinkedList1 = new SingleLinkedList4();SingleLinkedList4 singleLinkedList2 = new SingleLinkedList4();Node node1 = new Node(1);Node node2 = new Node(2);Node node3 = new Node(3);Node node4 = new Node(4);Node node5 = new Node(5);Node node6 = new Node(6);Node node7 = new Node(7);Node node8 = new Node(8);singleLinkedList1.add(node3);singleLinkedList1.add(node1);singleLinkedList1.add(node7);singleLinkedList1.add(node5);singleLinkedList2.add(node2);singleLinkedList2.add(node6);singleLinkedList2.add(node8);singleLinkedList2.add(node4);System.out.println("鏈表一：");singleLinkedList1.show(singleLinkedList1.head);System.out.println("鏈表二：");singleLinkedList2.show(singleLinkedList2.head);System.out.println("合并兩個鏈表==========");Node conbine = singleLinkedList1.conbine(singleLinkedList1.head, singleLinkedList2.head);singleLinkedList1.show(conbine);} }class SingleLinkedList4 {public Node head;public SingleLinkedList4() {head = new Node(-1);}/*** 數(shù)據(jù)按從小到大的順序添加到鏈表中* @param newNode 新節(jié)點*/public void add(Node newNode) {//輔助變量必須從head開始，不能從head.next開始，否則鏈表就斷了Node cur = head;Node pre = head;int value = newNode.num;while (cur.next != null) {pre = cur;cur = cur.next;if(value <= cur.num) { //小于節(jié)點cur，插在cur前面newNode.next = cur;pre.next = newNode;return; //當前鏈表中存在大于等于value的值}}cur.next = newNode; //當前鏈表中不存在大于等于value的值，則添加到末尾}public void show(Node head) {Node cur = head.next;if (cur == null) {System.out.println("鏈表為空~");}while (cur != null) {System.out.println(cur);cur = cur.next;}}public Node conbine(Node head1, Node head2) {Node conbine = new Node(-1);Node conbineTemp = conbine;Node cur1 = head1.next;Node cur2 = head2.next;while (cur1 != null && cur2 != null) {if (cur1.num <= cur2.num) {conbineTemp.next = new Node(cur1.num);conbineTemp = conbineTemp.next;cur1 = cur1.next;} else {conbineTemp.next = new Node(cur2.num);conbineTemp = conbineTemp.next;cur2 = cur2.next;}}if (cur1 == null) {while (cur2 != null) {conbineTemp.next = new Node(cur2.num);conbineTemp = conbineTemp.next;cur2 = cur2.next;}} else {while (cur1 != null) {conbineTemp.next = new Node(cur1.num);conbineTemp = conbineTemp.next;cur1 = cur1.next;}}return conbine;} }

總結(jié)

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

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