直接上實現代碼

//單鏈表的反轉public static void reverseList(HeroNode head){//如果當前鏈表為空，或只有一個節點，無需反轉if (head.next == null || head.next.next == null){return ;}//定義一個輔助變量，幫助我們遍歷HeroNode cur = head.next;HeroNode next = null;//指向當前節點[cur]的下一個節點HeroNode reverseHead = new HeroNode(0,"","");//遍歷原來的鏈表，每遍歷一個節點，就將其取出，并放到reverseHeadwhile(cur != null){next = cur.next;//先保存當前節點的下一個節點cur.next = reverseHead.next;reverseHead.next = cur;//cur的下一個節點指向新的鏈表的最前端cur = next; //把記錄的cur.next賦給cur}//將head.next 指向 reverseHead.next，實現單鏈表反轉head.next = reverseHead.next;}

最主要的是while循環里的邏輯

while(cur != null){next = cur.next;//先保存當前節點的下一個節點cur.next = reverseHead.next;reverseHead.next = cur;//cur的下一個節點指向新的鏈表的最前端cur = next; //把記錄的cur.next賦給cur}

這里一定要畫圖來慢慢理解，首先一個圖是原鏈表，另一個是新鏈表的頭部，邊畫圖變理解著寫邏輯

第一步先保留一下原鏈表的第二個位置head.next.next也就是代碼里的cur.next，如果不保留的話取出來后原鏈表就斷掉了

第二步，讓取出來的cur的右邊先next指向reverseHead.next

左邊是reverseHead.next = cur

然后把next賦給cur

在循環完鏈表后把鏈表的頭部更換

head.next = reverseHead.next;

下面是完整代碼（如果只看反轉可以找到reverseList()方法）

package DataStructures.LinkedList;public class SingleLinedListDemo {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 linkedList = new SingleLinkedList();//加入(按照加入的順序) // linkedList.add(hero1); // linkedList.add(hero2); // linkedList.add(hero3); // linkedList.add(hero4);//加入（按照no序號排序）linkedList.addByOrder(hero1);linkedList.addByOrder(hero4);linkedList.addByOrder(hero2);linkedList.addByOrder(hero3);linkedList.addByOrder(hero3);// //顯示(修改前) // System.out.println("顯示(修改前)"); // linkedList.list(); // //測試修改節點的代碼 // HeroNode hero5 = new HeroNode(2, "chun", "chunchun"); // linkedList.updata(hero5); // //顯示(修改后) // System.out.println("顯示(修改后)"); // linkedList.list();// //刪除節點 // linkedList.delete(2); // System.out.println("顯示刪除后"); // linkedList.list(); // // linkedList.delete(2); // System.out.println("顯示刪除后"); // linkedList.list();// //測試一下 求單鏈表中有效節點的個數 // System.out.println("有效的節點個數 = "+getLength(linkedList.getHead())); // // //測試一下看看是否得到倒數第k個節點 // HeroNode heroNode = fidLastIndexNode(linkedList.getHead(), 2); // // System.out.println(heroNode);linkedList.list();reverseList(linkedList.getHead());linkedList.list();}// 1.獲取到單鏈表的節點的個數（如果有頭結點，不統計頭結點）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.先把鏈表從頭到尾遍歷，得到鏈表的總長度// 4.得到size后從鏈表的第一個開始遍歷，遍歷size-index個就可以得到// 如果找到了，則返回該節點，否則返回nullpublic static HeroNode fidLastIndexNode(HeroNode head, int index){//判斷如果為空，則返回nullif (head.next == null){return null;}//第一個遍歷得到鏈表的長度（節點個數）//先做一個index的校驗int size = getLength(head);if (index<=0 || index> size){return null;}//定義輔助變量HeroNode temp = head.next;//遍歷，for循環定位到倒數的index個for (int i=0; i<size - index; i++){temp = temp.next;}return temp;}//單鏈表的反轉public static void reverseList(HeroNode head){//如果當前鏈表為空，或只有一個節點，無需反轉if (head.next == null || head.next.next == null){return ;}//定義一個輔助變量，幫助我們遍歷HeroNode cur = head.next;HeroNode next = null;//指向當前節點[cur]的下一個節點HeroNode reverseHead = new HeroNode(0,"","");//遍歷原來的鏈表，每遍歷一個節點，就將其取出，并放到reverseHeadwhile(cur != null){next = cur.next;//先保存當前節點的下一個節點cur.next = reverseHead.next;reverseHead.next = cur;//cur的下一個節點指向新的鏈表的最前端cur = next; //把記錄的cur.next賦給cur}//將head.next 指向 reverseHead.next，實現單鏈表反轉head.next = reverseHead.next;} }//定義一個SingleLinkedList 管理人物 class SingleLinkedList{//初始化一個頭結點，頭結點不要動，不存放具體數據private HeroNode head = new HeroNode(0,"","");public HeroNode getHead() {return head;}//添加節點到單鏈表//思路：當不考慮編號的順序時//1.找到當前鏈表的最后節點//2.將最后這個節點的next 指向 新的節點public void add(HeroNode heroNode){//因為head節點不能動，因此我們需要一個輔助變量 tempHeroNode 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是位于添加位置的前一個節點，否則插入不了,因為前一個節點next才可以找到新插入的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; //后移}//判斷flag 的值if(flag){//不能添加，已經存在System.out.printf("人物編號%d 已經存在，不能添加\n",heroNode.no);} else {//插入到鏈表中，temp后heroNode.next = temp.next; //連接新的節點的next和下一個的datatemp.next = heroNode; //連接上一個節點的next和新節點的數據}}//修改節點信息，根據no來修改，no不能改變public void updata(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;}//判斷flag ，是否找到需要修改的if (flag){temp.name = newHeroNode.name;temp.nickName = newHeroNode.nickName;}else {//沒找到System.out.printf("沒有找到編號：%d 的節點，不能修改",newHeroNode.no);}}//刪除節點//思路：// 1.先找到需要刪除的這個節點的前一個節點，// 2.temp.next = temp.next.next// 被刪除的節點沒有引用指向，會被GC回收public void delete(int no){if (head.next == null){System.out.println("鏈表為空，不能刪除");return;}//找到需要修改的節點，根據no編號//定義一個輔助變量HeroNode temp = head;boolean flag = false;//標記是否找到待刪除的節點while (true){if (temp.next == null){ //節點遍歷完畢break;}if (temp.next.no == no){//找到節點noflag = true;break;}temp = temp.next; //temp后移}if (flag){//找到notemp.next = temp.next.next;}else {System.out.printf("鏈表里沒有no為：%d 的節點\n",no);}}//展示鏈表public void list(){//先判斷鏈表是否為空if (head.next == null){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@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +", nickName='" + nickName + '\'' +'}';} }

總結

以上是生活随笔為你收集整理的java数据结构 - 单链表（腾讯面试题实现单链表反转）的全部內容，希望文章能夠幫你解決所遇到的問題。

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