Java單鏈表反轉圖文教程
前言
最近在回顧鏈表反轉問題中，突然有一些新的發(fā)現(xiàn)和收獲，特此整理一下，與大家分享 😁
背景回顧
單鏈表的存儲結構如圖：
數(shù)據(jù)域存放數(shù)據(jù)元素，指針域存放后繼結點地址
我們以一條 N1 -> N2 -> N3 -> N4 指向的單鏈表為例：
反轉后的鏈表指向如圖：
我們在代碼中定義如下結點類以方便運行測試：
/**
* 結點類
* （因為后續(xù)在main方法中運行，為了方便定義為static內部類）
*/
static class Node {
int val; // 數(shù)據(jù)域
Node next; // 指針域，指向下一個結點
Node(int x, Node nextNode) {
val = x;
next = nextNode;
}
}
通過循環(huán)遍歷方式實現(xiàn)鏈表反轉
實現(xiàn)思路：從鏈表頭結點出發(fā)，依次循環(huán)遍歷每一個結點，并更改結點對應的指針域，使其指向前一個結點
代碼如下：
/**
* 循環(huán)遍歷方式實現(xiàn)鏈表反轉
*
* @param head 鏈表的頭結點
* @return
*/
public static Node cycleNode(Node head) {
Node prev = null; // 保存前一個結點的信息
// 循環(huán)遍歷鏈表中的結點
while (head.next != null) {
// 1. 先保存當前結點的下一個結點的信息到tempNext
Node tempNext = head.next;
// 2. 修改當前結點指針域，使其指向上一個結點（如果是第一次進入循環(huán)的頭結點，則其上一個結點為null）
head.next = prev;
// 3. 將當前結點信息保存到prev中（以作為下一次循環(huán)中第二步使用到的"上一個結點"）
prev = head;
// 4. 當前結點在之前的123步中指針域已經(jīng)修改完畢，此時讓head重新指向待處理的下一個結點
head = tempNext;
}
// 上面的循環(huán)完成后，實際只修改了原先鏈表中的頭結點到倒數(shù)第二個結點間的結點指向，倒數(shù)第一個結點（尾結點）并未處理
// 此時prev指向原先鏈表中的倒數(shù)第二個結點，head指向尾結點
// 處理尾結點的指針域，使其指向前一個結點
head.next = prev;
// 返回尾結點，此時的尾結點既是原先鏈表中的尾結點，又是反轉后的新鏈表中的頭結點
return head;
}
測試效果：
public static void main(String[] args) {
// 構造測試用例，鏈表指向為 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;
// 輸出測試用例
System.out.println("原始鏈表指向為：");
printNode(head);
// 普通方式反轉鏈表
System.out.println("循環(huán)方式反轉鏈表指向為：");
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;
}
}
運行結果如圖：
可以看到，原先指向為 N1 -> N2 -> N3 -> N4 的鏈表，運行反轉方法后，其指向已變?yōu)?N4 -> N3 -> N2 -> N1
通過遞歸方式實現(xiàn)鏈表反轉
實現(xiàn)思路：從鏈表頭結點出發(fā)，依次遞歸遍歷每一個結點，并更改結點對應的指針域，使其指向前一個結點（沒錯，實際每一次遞歸里的處理過程跟上面的循環(huán)里是一樣的）
代碼實現(xiàn)：
/**
* 遞歸實現(xiàn)鏈表反轉
* 遞歸方法執(zhí)行完成后，head指向就從原鏈表順序：頭結點->尾結點 中的第一個結點（頭結點） 變成了反轉后的鏈表順序：尾結點->頭結點 中的第一個結點（尾結點）
*
* @param head 頭結點
* @param prev 存儲上一個結點
*/
public static void recursionNode(Node head, Node prev) {
if (null == head.next) {
// 設定遞歸終止條件
// 當head.next為空時，表明已經(jīng)遞歸到了原鏈表中的尾結點，此時單獨處理尾結點指針域，然后結束遞歸
head.next = prev;
return;
}
// 1. 先保存當前結點的下一個結點的信息到tempNext
Node tempNext = head.next;
// 2. 修改當前結點指針域，使其指向上一個結點（如果是第一次進入遞歸的頭結點，則其上一個結點為null）
head.next = prev;
// 3. 將當前結點信息保存到prev中（以作為下一次遞歸中第二步使用到的"上一個結點"）
prev = head;
// 4. 當前結點在之前的123步中指針域修改已經(jīng)修改完畢，此時讓head重新指向待處理的下一個結點
head = tempNext;
// 遞歸處理下一個結點
recursionNode(head, prev);
}
測試效果：
public static void main(String[] args) {
// 構造測試用例，鏈表指向為 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;
// 輸出測試用例
System.out.println("原始鏈表指向為：");
printNode(head);
// 遞歸方式反轉鏈表
System.out.println("遞歸方式反轉鏈表指向為：");
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;
}
}
注意：在上面👆的測試代碼中，在調用遞歸函數(shù)時傳遞了Node類的實例head作為參數(shù)
根據(jù)Java中 方法調用傳參中，基本類型是值傳遞，對象類型是引用傳遞 可得 =>
因為在調用遞歸函數(shù)時傳遞了head對象的引用，且在遞歸函數(shù)運行過程中，我們已經(jīng)數(shù)次改變了head引用指向的對象，
那么當遞歸函數(shù)執(zhí)行完畢時，head引用指向的對象此時理論上已經(jīng)是原鏈表中的尾結點N4了，且鏈表順序也已經(jīng)變成了 N4 -> N3 -> N2 -> N1
運行效果截圖：
最終的程序運行結果與我的設想大相徑庭！
那么，問題出在哪里呢？
遞歸方式反轉鏈表問題排查與延伸問題定位
既然程序運行效果與預期效果不符，那我們就在head對象引用可能發(fā)生變化的地方加入注釋打印一下對象地址，看看能不能發(fā)現(xiàn)問題在哪：
加入注釋后的代碼如下：
public static void main(String[] args) {
// 構造測試用例，鏈表指向為 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;
// 輸出測試用例
System.out.println("原始鏈表指向為：");
printNode(head);
// 遞歸方式反轉鏈表
System.out.println("遞歸方式反轉鏈表指向為：");
System.out.println("遞歸調用前 head 引用指向對象: " + head.toString());
recursionNode(head, null);
System.out.println("遞歸調用后 head 引用指向對象: " + 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;
}
}
/**
* 遞歸實現(xiàn)鏈表反轉
* 遞歸方法執(zhí)行完成后，head指向就從原鏈表順序：頭結點->尾結點 中的第一個結點（頭結點） 變成了反轉后的鏈表順序：尾結點->頭結點 中的第一個結點（尾結點）
*
* @param head 頭結點
* @param prev 存儲上一個結點
*/
public static void recursionNode(Node head, Node prev) {
System.out.println("遞歸調用中 head引用指向對象: " + head.toString());
if (null == head.next) {
// 設定遞歸終止條件
// 當head.next為空時，表名已經(jīng)遞歸到了原鏈表中的尾結點，此時單獨處理尾結點指針域，然后結束遞歸
head.next = prev;
System.out.println("遞歸調用返回前 head引用指向對象: " + head.toString());
return;
}
// 1. 先保存當前結點的下一個結點的信息到tempNext
Node tempNext = head.next;
// 2. 修改當前結點指針域，使其指向上一個結點（如果是第一次進入循環(huán)的頭結點，則其上一個結點為null）
head.next = prev;
// 3. 將當前結點信息保存到prev中（以作為下一次遞歸中第二步使用到的"上一個結點"）
prev = head;
// 4. 當前結點在之前的123步中指針域修改已經(jīng)修改完畢，此時讓head重新指向待處理的下一個結點
head = tempNext;
// 遞歸處理下一個結點
recursionNode(head, prev);
}
運行結果：
從上面👆的運行結果看，在遞歸函數(shù)執(zhí)行期間，head引用指向的對象確實發(fā)生了變化
注意 調用前 / 調用返回前 / 調用后 這三個地方head引用指向對象的變化：
可以發(fā)現(xiàn)，雖然遞歸函數(shù)執(zhí)行期間確實改變了head引用指向的對象，但實際上是變了個寂寞！😶
函數(shù)調用返回后，head引用指向的對象還是調用前的那個！
在debug模式下，我們再繼續(xù)深入看看遞歸函數(shù)調用前跟調用后的head對象是不是完全一樣的：
從上面兩張圖可以發(fā)現(xiàn)，雖然遞歸調用前跟調用后head引用指向的對象都是同一個，但這個對象本身的屬性（指針域）已經(jīng)發(fā)生了變化！
由此說明遞歸函數(shù)的執(zhí)行并不是在做無用功，而是切切實實改變了原鏈表的各結點指向順序！
只是因為遞歸函數(shù)執(zhí)行完成后，并沒有成功讓傳入的head對象引用指向反轉后的新鏈表的頭結點N4，
此時head對象引用仍然跟調用前一樣指向了N1，而N1在反轉后的新鏈表中變成了尾結點，至此，我們已經(jīng)完美的丟失了反轉后的新鏈表 😭，光靠指向尾結點的head根本無法遍歷到新鏈表的其他結點。。。
問題延伸：探究Java方法調用中的參數(shù)傳遞實質
由上面的問題定位可知，問題出在我對Java方法調用中的參數(shù)傳遞理解有偏差，那么接下來就來詳細探究一下Java方法調用中的參數(shù)傳遞過程吧！
形參與實參
測試示例代碼：
public static void recursionNode(Node headNode, Node prevNode) {
// do something...
}
public static void main(String[] args) {
// init head...
recursionNode(head, null); // 調用方法
}
在上面的示例代碼中，我們定義了recursionNode()方法，并在main()方法中調用它
方法定義中的 headNode prevNode 是 形式參數(shù)，調用時傳入的 head null 是 實際參數(shù)
值傳遞
方法定義中的形式參數(shù)類型如果是基本數(shù)據(jù)類型（byte、short、int、long、float、double、boolean、char），則調用方法時，實參到形參的傳遞實際是值傳遞，傳遞的是實際參數(shù)值的副本（拷貝）
因此，在方法體中任意修改形參的值，并不會影響到方法體外的實參的值
引用傳遞
方法定義中的形式參數(shù)類型如果是對象類型（含基本數(shù)據(jù)類型的數(shù)組），則調用方法時，實參到形參的傳遞實際也是值傳遞，傳遞的是實參對象的引用地址
如何理解這個 實參對象的引用地址 的概念呢？讓我們來看看示例代碼運行時的內存模型圖（簡單抽象了stack和heap的部分，如有不對歡迎指正 😆）
如圖，main方法和recursionNode方法執(zhí)行時實際是作為不同的棧幀入棧到當前線程的虛擬機棧中
main方法中的 head 引用實際保存的是一個地址，通過這個地址可以找到堆（heap）中的一個Node對象
recursionNode方法中的 headNode 引用實際保存的也是一個地址，通過這個地址可以找到堆中的一個Node對象
那么在main方法中調用recursionNode方法，實參 head 到形參 headNode 的傳遞過程中，到底傳遞的是什么呢？
很明顯，傳遞的就是那個能尋址到堆中某個Node對象的 地址（劃重點，要考?。?/p>
由此，實參 head 對象引用和形參 headNode 對象引用具有了相同的地址值，指向堆中的同一個Node對象
通過這兩個引用中的任何一個，都可以改變堆中對應的那個對象的屬性和狀態(tài)
遞歸方法調用后發(fā)生了什么
理解了對象引用傳遞的實質后，再回過頭來看上面遞歸方法調用后實際結果與預期結果不一致的問題，一切就迎刃而解了
如圖，遞歸調用結束后，雖然遞歸方法recursionNode()方法體內的 headNode 引用確實已經(jīng)變成了指向新的Node對象N4，但是main方法中，head 引用指向的仍然是遞歸方法調用前的Node對象N1（隨著遞歸方法的執(zhí)行，N1對象內部的指針域已經(jīng)產(chǎn)生了變化）
正確的遞歸方式實現(xiàn)鏈表反轉
/**
* 遞歸實現(xiàn)鏈表反轉，遞歸方法執(zhí)行完成后，head就從 頭結點->尾結點 中的起始點（頭結點）變成了 尾結點->頭結點 中的起始點（尾結點）
*
* @param head 頭結點
* @param prev 存儲上一個結點
*/
public static Node recursionNode2(Node head, Node prev) {
if (null == head.next) {
// 設定遞歸終止條件
head.next = prev;
return head;
}
Node tempNext = head.next;
head.next = prev;
prev = head;
head = tempNext;
Node result = recursionNode2(head, prev);
return result;
}
測試結果：
public static void main(String[] args) {
// 構造測試用例，鏈表指向為 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;
// 輸出測試用例
System.out.println("原始鏈表指向為：");
printNode(head);
// 新遞歸方式反轉鏈表
System.out.println("新遞歸方式反轉鏈表指向為：");
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;
}
}
運行結果截圖：
可以看到，經(jīng)過改善的新遞歸方法實現(xiàn)了預期的效果！😁
總結
到此這篇關于Java單鏈表反轉的文章就介紹到這了,更多相關Java單鏈表反轉內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
SpringBoot根據(jù)目錄結構自動生成路由前綴的實現(xiàn)代碼
本文介紹如何根據(jù)目錄結構給RequestMapping添加路由前綴，具體實現(xiàn)方法，本文通過示例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友參考下吧2021-08-08
這篇文章主要介紹了Java中RocketMq的消費方式詳解,RocketMQ的消費方式都是基于拉模式拉取消息的,而在這其中有一種長輪詢機制(對普通輪詢的一種優(yōu)化),來平衡上面Push/Pull模型的各自缺點,需要的朋友可以參考下2023-10-10
這篇文章主要介紹了Mybatis獲取參數(shù)值和查詢功能,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-03-03
java String 類的一些理解 關于==、equals、null
在對字符串的相等判斷，==判斷的是地址是否相同，equal()判斷的是字符值是否相同。大多數(shù)時候==跟equal()的結果都是相同的。2009-06-06
這篇文章主要介紹了淺談Spring IoC容器的依賴注入原理，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-03-03
通過springboot+mybatis+druid配置動態(tài)數(shù)據(jù)源
這篇文章主要介紹了通過springboot+mybatis+druid配置動態(tài)數(shù)據(jù)源，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，,需要的朋友可以參考下2019-06-06
MybatisPlus處理四種表與實體的映射及id自增策略分析
在最近的工作中，碰到一個比較復雜的返回結果，發(fā)現(xiàn)簡單映射已經(jīng)解決不了這個問題了，只好去求助百度，學習mybatis表與實體的映射應該怎么寫，將學習筆記結合工作碰到的問題寫下本文，供自身查漏補缺，同時已被不時之需2022-10-10
本文介紹了什么是哈希表?什么是哈希函數(shù)?什么是哈希沖突?三個問題的解決方案,文中有非常詳細的代碼示例,對正在學習java的小伙伴們很有幫助,需要的朋友可以參考下2021-05-05
springboot-2.3.x最新版源碼閱讀環(huán)境搭建(基于gradle構建)
這篇文章主要介紹了springboot-2.3.x最新版源碼閱讀環(huán)境搭建(基于gradle構建),需要的朋友可以參考下2020-08-08
Spring Cloud出現(xiàn)Options Forbidden 403問題解決方法
本篇文章主要介紹了Spring Cloud出現(xiàn)Options Forbidden 403問題解決方法，具有一定的參考價值，有興趣的可以了解一下2017-11-11