轉(zhuǎn)載自???Java單鏈表反轉(zhuǎn) 詳細過程

（一）單鏈表的結(jié)點結(jié)構(gòu):　

? ????data域：存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域；　
? ??next域：存儲直接后繼位置的域稱為指針域，它是存放結(jié)點的直接后繼的地址（位置）的指針域（鏈域）。
? ??data域+ next域：組成數(shù)據(jù)ai的存儲映射，稱為結(jié)點；
? ??注意：①鏈表通過每個結(jié)點的鏈域?qū)⒕€性表的n個結(jié)點按其邏輯順序鏈接在一起的。 　　
? ? ? ? ? ②每個結(jié)點只有一個鏈域的鏈表稱為單鏈表（Single Linked List）。
? ? ?所謂的鏈表就好像火車車廂一樣，從火車頭開始，每一節(jié)車廂之后都連著后一節(jié)車廂。
? ? ?要實現(xiàn)單鏈表存儲，首先是創(chuàng)建一結(jié)點類，其Java代碼如下：

[java]?view plain?copy

class?Node?{??

????private?int?Data;//?數(shù)據(jù)域??

????private?Node?Next;//?指針域??

????public?Node(int?Data)?{??

????????//?super();??

????????this.Data?=?Data;??

????}??

????public?int?getData()?{??

????????return?Data;??

????}??

????public?void?setData(int?Data)?{??

????????this.Data?=?Data;??

????}??

??

????public?Node?getNext()?{??

????????return?Next;??

????}??

????public?void?setNext(Node?Next)?{??

????????this.Next?=?Next;??

????}??

}??

（二）實現(xiàn)反轉(zhuǎn)的方法：
??（1）遞歸反轉(zhuǎn)法：在反轉(zhuǎn)當前節(jié)點之前先反轉(zhuǎn)后續(xù)節(jié)點。這樣從頭結(jié)點開始，層層深入直到尾結(jié)點才開始反轉(zhuǎn)指針域的指向。簡單的說就是從尾結(jié)點開始，逆向反轉(zhuǎn)各個結(jié)點的指針域指向，其過程圖如下所示：
? ?head：是前一結(jié)點的指針域（PS：前一結(jié)點的指針域指向當前結(jié)點）
? ?head.getNext()：是當前結(jié)點的指針域（PS：當前結(jié)點的指針域指向下一結(jié)點）
? ?reHead：是反轉(zhuǎn)后新鏈表的頭結(jié)點（即原來單鏈表的尾結(jié)點）

Java代碼實現(xiàn)：

[java]?view plain?copy

package?javatest1;??

public?class?javatest1?{??

????public?static?void?main(String[]?args)?{??

????????Node?head?=?new?Node(0);??

????????Node?node1?=?new?Node(1);??

????????Node?node2?=?new?Node(2);??

????????Node?node3?=?new?Node(3);??

????????head.setNext(node1);??

????????node1.setNext(node2);??

????????node2.setNext(node3);??

??

????????//?打印反轉(zhuǎn)前的鏈表??

????????Node?h?=?head;??

????????while?(null?!=?h)?{??

????????????System.out.print(h.getData()?+?"?");??

????????????h?=?h.getNext();??

????????}??

????????//?調(diào)用反轉(zhuǎn)方法??

????????head?=?Reverse1(head);??

??

????????System.out.println("\n**************************");??

????????//?打印反轉(zhuǎn)后的結(jié)果??

????????while?(null?!=?head)?{??

????????????System.out.print(head.getData()?+?"?");??

????????????head?=?head.getNext();??

????????}??

????}??

??

????/**?

?????*?遞歸，在反轉(zhuǎn)當前節(jié)點之前先反轉(zhuǎn)后續(xù)節(jié)點?

?????*/??

????public?static?Node?Reverse1(Node?head)?{??

????????//?head看作是前一結(jié)點，head.getNext()是當前結(jié)點，reHead是反轉(zhuǎn)后新鏈表的頭結(jié)點??

????????if?(head?==?null?||?head.getNext()?==?null)?{??

????????????return?head;//?若為空鏈或者當前結(jié)點在尾結(jié)點，則直接還回??

????????}??

????????Node?reHead?=?Reverse1(head.getNext());//?先反轉(zhuǎn)后續(xù)節(jié)點head.getNext()??

????????head.getNext().setNext(head);//?將當前結(jié)點的指針域指向前一結(jié)點??

????????head.setNext(null);//?前一結(jié)點的指針域令為null;??

????????return?reHead;//?反轉(zhuǎn)后新鏈表的頭結(jié)點??

????}??

}??

??

????class?Node?{??

????????private?int?Data;//?數(shù)據(jù)域??

????????private?Node?Next;//?指針域??

??

????????public?Node(int?Data)?{??

????????????//?super();??

????????????this.Data?=?Data;??

????????}??

??

????????public?int?getData()?{??

????????????return?Data;??

????????}??

??

????????public?void?setData(int?Data)?{??

????????????this.Data?=?Data;??

????????}??

??

????????public?Node?getNext()?{??

????????????return?Next;??

????????}??

??

????????public?void?setNext(Node?Next)?{??

????????????this.Next?=?Next;??

????????}??

????}??

?

（2）遍歷反轉(zhuǎn)法：遞歸反轉(zhuǎn)法是從后往前逆序反轉(zhuǎn)指針域的指向，而遍歷反轉(zhuǎn)法是從前往后反轉(zhuǎn)各個結(jié)點的指針域的指向。

? ?基本思路是：將當前節(jié)點cur的下一個節(jié)點 cur.getNext()緩存到temp后，然后更改當前節(jié)點指針指向上一結(jié)點pre。也就是說在反轉(zhuǎn)當前結(jié)點指針指向前，先把當前結(jié)點的指針域用tmp臨時保存，以便下一次使用，其過程可表示如下：
? ?pre：上一結(jié)點
? ?cur:?當前結(jié)點
? ?tmp:?臨時結(jié)點，用于保存當前結(jié)點的指針域（即下一結(jié)點）

?

Java代碼實現(xiàn)：

[java]?view plain?copy

package?javatest1;??

public?class?JavaTest1?{??

????public?static?void?main(String[]?args)?{??

????????Node?head?=?new?Node(0);??

????????Node?node1?=?new?Node(1);??

????????Node?node2?=?new?Node(2);??

????????Node?node3?=?new?Node(3);??

??

????????head.setNext(node1);??

????????node1.setNext(node2);??

????????node2.setNext(node3);??

??

????????//?打印反轉(zhuǎn)前的鏈表??

????????Node?h?=?head;??

????????while?(null?!=?h)?{??

????????????System.out.print(h.getData()?+?"?");??

????????????h?=?h.getNext();??

????????}??

????????//?調(diào)用反轉(zhuǎn)方法??

????????//?head?=?reverse1(head);??

????????head?=?reverse2(head);??

??

????????System.out.println("\n**************************");??

????????//?打印反轉(zhuǎn)后的結(jié)果??

????????while?(null?!=?head)?{??

????????????System.out.print(head.getData()?+?"?");??

????????????head?=?head.getNext();??

????????}??

????}??

??

????/**?

?????*?遍歷，將當前節(jié)點的下一個節(jié)點緩存后更改當前節(jié)點指針?

?????*/??

????public?static?Node?reverse2(Node?head)?{??

????????if?(head?==?null)??

????????????return?head;??

????????Node?pre?=?head;//?上一結(jié)點??

????????Node?cur?=?head.getNext();//?當前結(jié)點??

????????Node?tmp;//?臨時結(jié)點，用于保存當前結(jié)點的指針域（即下一結(jié)點）??

????????while?(cur?!=?null)?{//?當前結(jié)點為null，說明位于尾結(jié)點??

????????????tmp?=?cur.getNext();??

????????????cur.setNext(pre);//?反轉(zhuǎn)指針域的指向??

??

????????????//?指針往下移動??

????????????pre?=?cur;??

????????????cur?=?tmp;??

????????}??

????????//?最后將原鏈表的頭節(jié)點的指針域置為null，還回新鏈表的頭結(jié)點，即原鏈表的尾結(jié)點??

????????head.setNext(null);??

??????????

????????return?pre;??

????}??

}??

??

class?Node?{??

????private?int?Data;//?數(shù)據(jù)域??

????private?Node?Next;//?指針域??

??

????public?Node(int?Data)?{??

????????//?super();??

????????this.Data?=?Data;??

????}??

??

????public?int?getData()?{??

????????return?Data;??

????}??

??

????public?void?setData(int?Data)?{??

????????this.Data?=?Data;??

????}??

??

????public?Node?getNext()?{??

????????return?Next;??

????}??

??

????public?void?setNext(Node?Next)?{??

????????this.Next?=?Next;??

????}??

}??

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

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

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