您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“如何實(shí)現(xiàn)Java單鏈表反轉(zhuǎn)”,感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷,實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“如何實(shí)現(xiàn)Java單鏈表反轉(zhuǎn)”吧!
單鏈表的存儲(chǔ)結(jié)構(gòu)如圖:
數(shù)據(jù)域存放數(shù)據(jù)元素,指針域存放后繼結(jié)點(diǎn)地址
我們以一條 N1 -> N2 -> N3 -> N4 指向的單鏈表為例:
反轉(zhuǎn)后的鏈表指向如圖:
我們?cè)诖a中定義如下結(jié)點(diǎn)類(lèi)以方便運(yùn)行測(cè)試:
/**
* 結(jié)點(diǎn)類(lèi)
* (因?yàn)楹罄m(xù)在main方法中運(yùn)行,為了方便定義為static內(nèi)部類(lèi))
*/
static class Node {
int val; // 數(shù)據(jù)域
Node next; // 指針域,指向下一個(gè)結(jié)點(diǎn)
Node(int x, Node nextNode) {
val = x;
next = nextNode;
}
}
實(shí)現(xiàn)思路:從鏈表頭結(jié)點(diǎn)出發(fā),依次循環(huán)遍歷每一個(gè)結(jié)點(diǎn),并更改結(jié)點(diǎn)對(duì)應(yīng)的指針域,使其指向前一個(gè)結(jié)點(diǎn)
代碼如下:
/**
* 循環(huán)遍歷方式實(shí)現(xiàn)鏈表反轉(zhuǎn)
*
* @param head 鏈表的頭結(jié)點(diǎn)
* @return
*/
public static Node cycleNode(Node head) {
Node prev = null; // 保存前一個(gè)結(jié)點(diǎn)的信息
// 循環(huán)遍歷鏈表中的結(jié)點(diǎn)
while (head.next != null) {
// 1. 先保存當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的信息到tempNext
Node tempNext = head.next;
// 2. 修改當(dāng)前結(jié)點(diǎn)指針域,使其指向上一個(gè)結(jié)點(diǎn)(如果是第一次進(jìn)入循環(huán)的頭結(jié)點(diǎn),則其上一個(gè)結(jié)點(diǎn)為null)
head.next = prev;
// 3. 將當(dāng)前結(jié)點(diǎn)信息保存到prev中(以作為下一次循環(huán)中第二步使用到的"上一個(gè)結(jié)點(diǎn)")
prev = head;
// 4. 當(dāng)前結(jié)點(diǎn)在之前的123步中指針域已經(jīng)修改完畢,此時(shí)讓head重新指向待處理的下一個(gè)結(jié)點(diǎn)
head = tempNext;
}
// 上面的循環(huán)完成后,實(shí)際只修改了原先鏈表中的頭結(jié)點(diǎn)到倒數(shù)第二個(gè)結(jié)點(diǎn)間的結(jié)點(diǎn)指向,倒數(shù)第一個(gè)結(jié)點(diǎn)(尾結(jié)點(diǎn))并未處理
// 此時(shí)prev指向原先鏈表中的倒數(shù)第二個(gè)結(jié)點(diǎn),head指向尾結(jié)點(diǎn)
// 處理尾結(jié)點(diǎn)的指針域,使其指向前一個(gè)結(jié)點(diǎn)
head.next = prev;
// 返回尾結(jié)點(diǎn),此時(shí)的尾結(jié)點(diǎn)既是原先鏈表中的尾結(jié)點(diǎn),又是反轉(zhuǎn)后的新鏈表中的頭結(jié)點(diǎn)
return head;
}
測(cè)試效果:
public static void main(String[] args) {
// 構(gòu)造測(cè)試用例,鏈表指向?yàn)?nbsp;N1 -> N2 -> N3 -> N4
Node n4 = new Node(4, null);
Node n3 = new Node(3, n4);
Node n2 = new Node(2, n3);
Node n1 = new Node(1, n2);
Node head = n1;
// 輸出測(cè)試用例
System.out.println("原始鏈表指向?yàn)椋?quot;);
printNode(head);
// 普通方式反轉(zhuǎn)鏈表
System.out.println("循環(huán)方式反轉(zhuǎn)鏈表指向?yàn)椋?quot;);
head = cycleNode(head);
printNode(head);
}
/**
* 循環(huán)打印鏈表數(shù)據(jù)域
* @param head
*/
public static void printNode(Node head) {
while (head != null) {
System.out.println(head.val);
head = head.next;
}
}
可以看到,原先指向?yàn)?N1 -> N2 -> N3 -> N4 的鏈表,運(yùn)行反轉(zhuǎn)方法后,其指向已變?yōu)?N4 -> N3 -> N2 -> N1
實(shí)現(xiàn)思路:從鏈表頭結(jié)點(diǎn)出發(fā),依次遞歸遍歷每一個(gè)結(jié)點(diǎn),并更改結(jié)點(diǎn)對(duì)應(yīng)的指針域,使其指向前一個(gè)結(jié)點(diǎn)(沒(méi)錯(cuò),實(shí)際每一次遞歸里的處理過(guò)程跟上面的循環(huán)里是一樣的)
代碼實(shí)現(xiàn):
/**
* 遞歸實(shí)現(xiàn)鏈表反轉(zhuǎn)
* 遞歸方法執(zhí)行完成后,head指向就從原鏈表順序:頭結(jié)點(diǎn)->尾結(jié)點(diǎn) 中的第一個(gè)結(jié)點(diǎn)(頭結(jié)點(diǎn)) 變成了反轉(zhuǎn)后的鏈表順序:尾結(jié)點(diǎn)->頭結(jié)點(diǎn) 中的第一個(gè)結(jié)點(diǎn)(尾結(jié)點(diǎn))
*
* @param head 頭結(jié)點(diǎn)
* @param prev 存儲(chǔ)上一個(gè)結(jié)點(diǎn)
*/
public static void recursionNode(Node head, Node prev) {
if (null == head.next) {
// 設(shè)定遞歸終止條件
// 當(dāng)head.next為空時(shí),表明已經(jīng)遞歸到了原鏈表中的尾結(jié)點(diǎn),此時(shí)單獨(dú)處理尾結(jié)點(diǎn)指針域,然后結(jié)束遞歸
head.next = prev;
return;
}
// 1. 先保存當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的信息到tempNext
Node tempNext = head.next;
// 2. 修改當(dāng)前結(jié)點(diǎn)指針域,使其指向上一個(gè)結(jié)點(diǎn)(如果是第一次進(jìn)入遞歸的頭結(jié)點(diǎn),則其上一個(gè)結(jié)點(diǎn)為null)
head.next = prev;
// 3. 將當(dāng)前結(jié)點(diǎn)信息保存到prev中(以作為下一次遞歸中第二步使用到的"上一個(gè)結(jié)點(diǎn)")
prev = head;
// 4. 當(dāng)前結(jié)點(diǎn)在之前的123步中指針域修改已經(jīng)修改完畢,此時(shí)讓head重新指向待處理的下一個(gè)結(jié)點(diǎn)
head = tempNext;
// 遞歸處理下一個(gè)結(jié)點(diǎn)
recursionNode(head, prev);
}
測(cè)試效果:
public static void main(String[] args) {
// 構(gòu)造測(cè)試用例,鏈表指向?yàn)?nbsp;N1 -> N2 -> N3 -> N4
Node n4 = new Node(4, null);
Node n3 = new Node(3, n4);
Node n2 = new Node(2, n3);
Node n1 = new Node(1, n2);
Node head = n1;
// 輸出測(cè)試用例
System.out.println("原始鏈表指向?yàn)椋?quot;);
printNode(head);
// 遞歸方式反轉(zhuǎn)鏈表
System.out.println("遞歸方式反轉(zhuǎn)鏈表指向?yàn)椋?quot;);
recursionNode(head, null);
printNode(head);
}
/**
* 循環(huán)打印鏈表數(shù)據(jù)域
* @param head
*/
public static void printNode(Node head) {
while (head != null) {
System.out.println(head.val);
head = head.next;
}
}
注意:在上面的測(cè)試代碼中,在調(diào)用遞歸函數(shù)時(shí)傳遞了Node類(lèi)的實(shí)例head作為參數(shù)
根據(jù)Java中 方法調(diào)用傳參中,基本類(lèi)型是值傳遞,對(duì)象類(lèi)型是引用傳遞 可得 =>
因?yàn)樵谡{(diào)用遞歸函數(shù)時(shí)傳遞了head對(duì)象的引用,且在遞歸函數(shù)運(yùn)行過(guò)程中,我們已經(jīng)數(shù)次改變了head引用指向的對(duì)象,
那么當(dāng)遞歸函數(shù)執(zhí)行完畢時(shí),head引用指向的對(duì)象此時(shí)理論上已經(jīng)是原鏈表中的尾結(jié)點(diǎn)N4了,且鏈表順序也已經(jīng)變成了 N4 -> N3 -> N2 -> N1
最終的程序運(yùn)行結(jié)果與我的設(shè)想大相徑庭!
那么,問(wèn)題出在哪里呢?
既然程序運(yùn)行效果與預(yù)期效果不符,那我們就在head對(duì)象引用可能發(fā)生變化的地方加入注釋打印一下對(duì)象地址,看看能不能發(fā)現(xiàn)問(wèn)題在哪:
加入注釋后的代碼如下:
public static void main(String[] args) {
// 構(gòu)造測(cè)試用例,鏈表指向?yàn)?nbsp;N1 -> N2 -> N3 -> N4
Node n4 = new Node(4, null);
Node n3 = new Node(3, n4);
Node n2 = new Node(2, n3);
Node n1 = new Node(1, n2);
Node head = n1;
// 輸出測(cè)試用例
System.out.println("原始鏈表指向?yàn)椋?quot;);
printNode(head);
// 遞歸方式反轉(zhuǎn)鏈表
System.out.println("遞歸方式反轉(zhuǎn)鏈表指向?yàn)椋?quot;);
System.out.println("遞歸調(diào)用前 head 引用指向?qū)ο? " + head.toString());
recursionNode(head, null);
System.out.println("遞歸調(diào)用后 head 引用指向?qū)ο? " + head.toString());
printNode(head);
}
/**
* 循環(huán)打印鏈表數(shù)據(jù)域
* @param head
*/
public static void printNode(Node head) {
while (head != null) {
System.out.println(head.val);
head = head.next;
}
}
/**
* 遞歸實(shí)現(xiàn)鏈表反轉(zhuǎn)
* 遞歸方法執(zhí)行完成后,head指向就從原鏈表順序:頭結(jié)點(diǎn)->尾結(jié)點(diǎn) 中的第一個(gè)結(jié)點(diǎn)(頭結(jié)點(diǎn)) 變成了反轉(zhuǎn)后的鏈表順序:尾結(jié)點(diǎn)->頭結(jié)點(diǎn) 中的第一個(gè)結(jié)點(diǎn)(尾結(jié)點(diǎn))
*
* @param head 頭結(jié)點(diǎn)
* @param prev 存儲(chǔ)上一個(gè)結(jié)點(diǎn)
*/
public static void recursionNode(Node head, Node prev) {
System.out.println("遞歸調(diào)用中 head引用指向?qū)ο? " + head.toString());
if (null == head.next) {
// 設(shè)定遞歸終止條件
// 當(dāng)head.next為空時(shí),表名已經(jīng)遞歸到了原鏈表中的尾結(jié)點(diǎn),此時(shí)單獨(dú)處理尾結(jié)點(diǎn)指針域,然后結(jié)束遞歸
head.next = prev;
System.out.println("遞歸調(diào)用返回前 head引用指向?qū)ο? " + head.toString());
return;
}
// 1. 先保存當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的信息到tempNext
Node tempNext = head.next;
// 2. 修改當(dāng)前結(jié)點(diǎn)指針域,使其指向上一個(gè)結(jié)點(diǎn)(如果是第一次進(jìn)入循環(huán)的頭結(jié)點(diǎn),則其上一個(gè)結(jié)點(diǎn)為null)
head.next = prev;
// 3. 將當(dāng)前結(jié)點(diǎn)信息保存到prev中(以作為下一次遞歸中第二步使用到的"上一個(gè)結(jié)點(diǎn)")
prev = head;
// 4. 當(dāng)前結(jié)點(diǎn)在之前的123步中指針域修改已經(jīng)修改完畢,此時(shí)讓head重新指向待處理的下一個(gè)結(jié)點(diǎn)
head = tempNext;
// 遞歸處理下一個(gè)結(jié)點(diǎn)
recursionNode(head, prev);
}
運(yùn)行結(jié)果:
從上面的運(yùn)行結(jié)果看,在遞歸函數(shù)執(zhí)行期間,head引用指向的對(duì)象確實(shí)發(fā)生了變化
注意 調(diào)用前 / 調(diào)用返回前 / 調(diào)用后 這三個(gè)地方head引用指向?qū)ο蟮淖兓?/p>
可以發(fā)現(xiàn),雖然遞歸函數(shù)執(zhí)行期間確實(shí)改變了head引用指向的對(duì)象,但實(shí)際上是變了個(gè)寂寞!
函數(shù)調(diào)用返回后,head引用指向的對(duì)象還是調(diào)用前的那個(gè)!
在debug模式下,我們?cè)倮^續(xù)深入看看遞歸函數(shù)調(diào)用前跟調(diào)用后的head對(duì)象是不是完全一樣的:
從上面兩張圖可以發(fā)現(xiàn),雖然遞歸調(diào)用前跟調(diào)用后head引用指向的對(duì)象都是同一個(gè),但這個(gè)對(duì)象本身的屬性(指針域)已經(jīng)發(fā)生了變化!
由此說(shuō)明遞歸函數(shù)的執(zhí)行并不是在做無(wú)用功,而是切切實(shí)實(shí)改變了原鏈表的各結(jié)點(diǎn)指向順序!
只是因?yàn)檫f歸函數(shù)執(zhí)行完成后,并沒(méi)有成功讓傳入的head對(duì)象引用指向反轉(zhuǎn)后的新鏈表的頭結(jié)點(diǎn)N4,
此時(shí)head對(duì)象引用仍然跟調(diào)用前一樣指向了N1,而N1在反轉(zhuǎn)后的新鏈表中變成了尾結(jié)點(diǎn),至此,我們已經(jīng)完美的丟失了反轉(zhuǎn)后的新鏈表 ,光靠指向尾結(jié)點(diǎn)的head根本無(wú)法遍歷到新鏈表的其他結(jié)點(diǎn)。。。
由上面的問(wèn)題定位可知,問(wèn)題出在我對(duì)Java方法調(diào)用中的參數(shù)傳遞理解有偏差,那么接下來(lái)就來(lái)詳細(xì)探究一下Java方法調(diào)用中的參數(shù)傳遞過(guò)程吧!
測(cè)試示例代碼:
public static void recursionNode(Node headNode, Node prevNode) {
// do something...
}
public static void main(String[] args) {
// init head...
recursionNode(head, null); // 調(diào)用方法
}
在上面的示例代碼中,我們定義了recursionNode()方法,并在main()方法中調(diào)用它
方法定義中的 headNode prevNode 是 形式參數(shù),調(diào)用時(shí)傳入的 head null 是 實(shí)際參數(shù)
方法定義中的形式參數(shù)類(lèi)型如果是基本數(shù)據(jù)類(lèi)型(byte、short、int、long、float、double、boolean、char),則調(diào)用方法時(shí),實(shí)參到形參的傳遞實(shí)際是值傳遞,傳遞的是實(shí)際參數(shù)值的副本(拷貝)
因此,在方法體中任意修改形參的值,并不會(huì)影響到方法體外的實(shí)參的值
方法定義中的形式參數(shù)類(lèi)型如果是對(duì)象類(lèi)型(含基本數(shù)據(jù)類(lèi)型的數(shù)組),則調(diào)用方法時(shí),實(shí)參到形參的傳遞實(shí)際也是值傳遞,傳遞的是實(shí)參對(duì)象的引用地址
如何理解這個(gè) 實(shí)參對(duì)象的引用地址 的概念呢?讓我們來(lái)看看示例代碼運(yùn)行時(shí)的內(nèi)存模型圖(簡(jiǎn)單抽象了stack和heap的部分,如有不對(duì)歡迎指正 )
如圖,main方法和recursionNode方法執(zhí)行時(shí)實(shí)際是作為不同的棧幀入棧到當(dāng)前線(xiàn)程的虛擬機(jī)棧中
main方法中的 head 引用實(shí)際保存的是一個(gè)地址,通過(guò)這個(gè)地址可以找到堆(heap)中的一個(gè)Node對(duì)象
recursionNode方法中的 headNode 引用實(shí)際保存的也是一個(gè)地址,通過(guò)這個(gè)地址可以找到堆中的一個(gè)Node對(duì)象
那么在main方法中調(diào)用recursionNode方法,實(shí)參 head 到形參 headNode 的傳遞過(guò)程中,到底傳遞的是什么呢?
很明顯,傳遞的就是那個(gè)能尋址到堆中某個(gè)Node對(duì)象的 地址(劃重點(diǎn),要考!)
由此,實(shí)參 head 對(duì)象引用和形參 headNode 對(duì)象引用具有了相同的地址值,指向堆中的同一個(gè)Node對(duì)象
通過(guò)這兩個(gè)引用中的任何一個(gè),都可以改變堆中對(duì)應(yīng)的那個(gè)對(duì)象的屬性和狀態(tài)
理解了對(duì)象引用傳遞的實(shí)質(zhì)后,再回過(guò)頭來(lái)看上面遞歸方法調(diào)用后實(shí)際結(jié)果與預(yù)期結(jié)果不一致的問(wèn)題,一切就迎刃而解了
如圖,遞歸調(diào)用結(jié)束后,雖然遞歸方法recursionNode()方法體內(nèi)的 headNode 引用確實(shí)已經(jīng)變成了指向新的Node對(duì)象N4,但是main方法中,head 引用指向的仍然是遞歸方法調(diào)用前的Node對(duì)象N1(隨著遞歸方法的執(zhí)行,N1對(duì)象內(nèi)部的指針域已經(jīng)產(chǎn)生了變化)
/**
* 遞歸實(shí)現(xiàn)鏈表反轉(zhuǎn),遞歸方法執(zhí)行完成后,head就從 頭結(jié)點(diǎn)->尾結(jié)點(diǎn) 中的起始點(diǎn)(頭結(jié)點(diǎn))變成了 尾結(jié)點(diǎn)->頭結(jié)點(diǎn) 中的起始點(diǎn)(尾結(jié)點(diǎn))
*
* @param head 頭結(jié)點(diǎn)
* @param prev 存儲(chǔ)上一個(gè)結(jié)點(diǎn)
*/
public static Node recursionNode2(Node head, Node prev) {
if (null == head.next) {
// 設(shè)定遞歸終止條件
head.next = prev;
return head;
}
Node tempNext = head.next;
head.next = prev;
prev = head;
head = tempNext;
Node result = recursionNode2(head, prev);
return result;
}
測(cè)試結(jié)果:
public static void main(String[] args) {
// 構(gòu)造測(cè)試用例,鏈表指向?yàn)?nbsp;N1 -> N2 -> N3 -> N4
Node n4 = new Node(4, null);
Node n3 = new Node(3, n4);
Node n2 = new Node(2, n3);
Node n1 = new Node(1, n2);
Node head = n1;
// 輸出測(cè)試用例
System.out.println("原始鏈表指向?yàn)椋?quot;);
printNode(head);
// 新遞歸方式反轉(zhuǎn)鏈表
System.out.println("新遞歸方式反轉(zhuǎn)鏈表指向?yàn)椋?quot;);
head = recursionNode2(head, null);
printNode(head);
}
/**
* 循環(huán)打印鏈表數(shù)據(jù)域
* @param head
*/
public static void printNode(Node head) {
while (head != null) {
System.out.println(head.val);
head = head.next;
}
}
到此,相信大家對(duì)“如何實(shí)現(xiàn)Java單鏈表反轉(zhuǎn)”有了更深的了解,不妨來(lái)實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢(xún),關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。