Java單鏈表反轉圖文教程

Posted on by

前言

最近在回顧鏈表反轉問題中，突然有一些新的發現和收獲，特此整理一下，與大傢分享 😁

背景回顧

單鏈表的存儲結構如圖：

數據域存放數據元素，指針域存放後繼結點地址

我們以一條 N1 -> N2 -> N3 -> N4 指向的單鏈表為例：

反轉後的鏈表指向如圖：

我們在代碼中定義如下結點類以方便運行測試：

 /**
 * 結點類
 * （因為後續在main方法中運行，為瞭方便定義為static內部類）
 */
 static class Node {
 int val; // 數據域
 Node next; // 指針域，指向下一個結點

 Node(int x, Node nextNode) {
  val = x;
  next = nextNode;
 }
 }

通過循環遍歷方式實現鏈表反轉

實現思路：從鏈表頭結點出發，依次循環遍歷每一個結點，並更改結點對應的指針域，使其指向前一個結點

代碼如下：

 /**
  * 循環遍歷方式實現鏈表反轉
  *
  * @param head 鏈表的頭結點
  * @return
  */
 public static Node cycleNode(Node head) {

  Node prev = null; // 保存前一個結點的信息

  // 循環遍歷鏈表中的結點
  while (head.next != null) {
   // 1. 先保存當前結點的下一個結點的信息到tempNext
   Node tempNext = head.next;
   // 2. 修改當前結點指針域，使其指向上一個結點（如果是第一次進入循環的頭結點，則其上一個結點為null）
   head.next = prev;
   // 3. 將當前結點信息保存到prev中（以作為下一次循環中第二步使用到的"上一個結點"）
   prev = head;
   // 4. 當前結點在之前的123步中指針域已經修改完畢，此時讓head重新指向待處理的下一個結點
   head = tempNext;
  }

  // 上面的循環完成後，實際隻修改瞭原先鏈表中的頭結點到倒數第二個結點間的結點指向，倒數第一個結點（尾結點）並未處理
  // 此時prev指向原先鏈表中的倒數第二個結點，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("循環方式反轉鏈表指向為：");
  head = cycleNode(head);
  printNode(head);
 }

 /**
  * 循環打印鏈表數據域
  * @param head
  */
 public static void printNode(Node head) {
  while (head != null) {
   System.out.println(head.val);
   head = head.next;
  }
 }

運行結果如圖：

可以看到，原先指向為 N1 -> N2 -> N3 -> N4 的鏈表，運行反轉方法後，其指向已變為 N4 -> N3 -> N2 -> N1

通過遞歸方式實現鏈表反轉

實現思路：從鏈表頭結點出發，依次遞歸遍歷每一個結點，並更改結點對應的指針域，使其指向前一個結點（沒錯，實際每一次遞歸裡的處理過程跟上面的循環裡是一樣的）

代碼實現：

 /**
  * 遞歸實現鏈表反轉
  * 遞歸方法執行完成後，head指向就從原鏈表順序：頭結點->尾結點 中的第一個結點（頭結點） 變成瞭反轉後的鏈表順序：尾結點->頭結點 中的第一個結點（尾結點）
  *
  * @param head 頭結點
  * @param prev 存儲上一個結點
  */
 public static void recursionNode(Node head, Node prev) {
 
  if (null == head.next) {
   // 設定遞歸終止條件
   // 當head.next為空時，表明已經遞歸到瞭原鏈表中的尾結點，此時單獨處理尾結點指針域，然後結束遞歸
   head.next = prev;
   return;
  }

  // 1. 先保存當前結點的下一個結點的信息到tempNext
  Node tempNext = head.next;
  // 2. 修改當前結點指針域，使其指向上一個結點（如果是第一次進入遞歸的頭結點，則其上一個結點為null）
  head.next = prev;
  // 3. 將當前結點信息保存到prev中（以作為下一次遞歸中第二步使用到的"上一個結點"）
  prev = head;
  // 4. 當前結點在之前的123步中指針域修改已經修改完畢，此時讓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);
 }

 /**
  * 循環打印鏈表數據域
  * @param head
  */
 public static void printNode(Node head) {
  while (head != null) {
   System.out.println(head.val);
   head = head.next;
  }
 }

註意：在上面👆的測試代碼中，在調用遞歸函數時傳遞瞭Node類的實例head作為參數

根據Java中 方法調用傳參中，基本類型是值傳遞，對象類型是引用傳遞 可得 =>

因為在調用遞歸函數時傳遞瞭head對象的引用，且在遞歸函數運行過程中，我們已經數次改變瞭head引用指向的對象，

那麼當遞歸函數執行完畢時，head引用指向的對象此時理論上已經是原鏈表中的尾結點N4瞭，且鏈表順序也已經變成瞭 N4 -> N3 -> N2 -> N1

運行效果截圖：

最終的程序運行結果與我的設想大相徑庭！

那麼，問題出在哪裡呢？

遞歸方式反轉鏈表問題排查與延伸問題定位

既然程序運行效果與預期效果不符，那我們就在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("遞歸方式反轉鏈表指向為：");
  System.out.println("遞歸調用前 head 引用指向對象: " + head.toString());
  recursionNode(head, null);
  System.out.println("遞歸調用後 head 引用指向對象: " + head.toString());
  printNode(head);
 }

 /**
  * 循環打印鏈表數據域
  * @param head
  */
 public static void printNode(Node head) {
  while (head != null) {
   System.out.println(head.val);
   head = head.next;
  }
 }

 /**
  * 遞歸實現鏈表反轉
  * 遞歸方法執行完成後，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為空時，表名已經遞歸到瞭原鏈表中的尾結點，此時單獨處理尾結點指針域，然後結束遞歸
   head.next = prev;
   System.out.println("遞歸調用返回前 head引用指向對象: " + head.toString());
   return;
  }

  // 1. 先保存當前結點的下一個結點的信息到tempNext
  Node tempNext = head.next;
  // 2. 修改當前結點指針域，使其指向上一個結點（如果是第一次進入循環的頭結點，則其上一個結點為null）
  head.next = prev;
  // 3. 將當前結點信息保存到prev中（以作為下一次遞歸中第二步使用到的"上一個結點"）
  prev = head;
  // 4. 當前結點在之前的123步中指針域修改已經修改完畢，此時讓head重新指向待處理的下一個結點
  head = tempNext;

  // 遞歸處理下一個結點
  recursionNode(head, prev);
 }

運行結果：

從上面👆的運行結果看，在遞歸函數執行期間，head引用指向的對象確實發生瞭變化

註意 調用前 / 調用返回前 / 調用後 這三個地方head引用指向對象的變化：

可以發現，雖然遞歸函數執行期間確實改變瞭head引用指向的對象，但實際上是變瞭個寂寞！😶

函數調用返回後，head引用指向的對象還是調用前的那個！

在debug模式下，我們再繼續深入看看遞歸函數調用前跟調用後的head對象是不是完全一樣的：

從上面兩張圖可以發現，雖然遞歸調用前跟調用後head引用指向的對象都是同一個，但這個對象本身的屬性（指針域）已經發生瞭變化！

由此說明遞歸函數的執行並不是在做無用功，而是切切實實改變瞭原鏈表的各結點指向順序！

隻是因為遞歸函數執行完成後，並沒有成功讓傳入的head對象引用指向反轉後的新鏈表的頭結點N4，

此時head對象引用仍然跟調用前一樣指向瞭N1，而N1在反轉後的新鏈表中變成瞭尾結點，至此，我們已經完美的丟失瞭反轉後的新鏈表 😭，光靠指向尾結點的head根本無法遍歷到新鏈表的其他結點。。。

問題延伸：探究Java方法調用中的參數傳遞實質

由上面的問題定位可知，問題出在我對Java方法調用中的參數傳遞理解有偏差，那麼接下來就來詳細探究一下Java方法調用中的參數傳遞過程吧！

形參與實參

測試示例代碼：

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 是 形式參數，調用時傳入的 head null 是 實際參數

值傳遞

方法定義中的形式參數類型如果是基本數據類型（byte、short、int、long、float、double、boolean、char），則調用方法時，實參到形參的傳遞實際是值傳遞，傳遞的是實際參數值的副本（拷貝）

因此，在方法體中任意修改形參的值，並不會影響到方法體外的實參的值

引用傳遞

方法定義中的形式參數類型如果是對象類型（含基本數據類型的數組），則調用方法時，實參到形參的傳遞實際也是值傳遞，傳遞的是實參對象的引用地址

如何理解這個 實參對象的引用地址 的概念呢？讓我們來看看示例代碼運行時的內存模型圖（簡單抽象瞭stack和heap的部分，如有不對歡迎指正 😆）

如圖，main方法和recursionNode方法執行時實際是作為不同的棧幀入棧到當前線程的虛擬機棧中

main方法中的 head 引用實際保存的是一個地址，通過這個地址可以找到堆（heap）中的一個Node對象

recursionNode方法中的 headNode 引用實際保存的也是一個地址，通過這個地址可以找到堆中的一個Node對象

那麼在main方法中調用recursionNode方法，實參 head 到形參 headNode 的傳遞過程中，到底傳遞的是什麼呢？

很明顯，傳遞的就是那個能尋址到堆中某個Node對象的 地址（劃重點，要考！）

由此，實參 head 對象引用和形參 headNode 對象引用具有瞭相同的地址值，指向堆中的同一個Node對象

通過這兩個引用中的任何一個，都可以改變堆中對應的那個對象的屬性和狀態

遞歸方法調用後發生瞭什麼

理解瞭對象引用傳遞的實質後，再回過頭來看上面遞歸方法調用後實際結果與預期結果不一致的問題，一切就迎刃而解瞭

如圖，遞歸調用結束後，雖然遞歸方法recursionNode()方法體內的 headNode 引用確實已經變成瞭指向新的Node對象N4，但是main方法中，head 引用指向的仍然是遞歸方法調用前的Node對象N1（隨著遞歸方法的執行，N1對象內部的指針域已經產生瞭變化）

正確的遞歸方式實現鏈表反轉

 /**
  * 遞歸實現鏈表反轉，遞歸方法執行完成後，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);
 }

 /**
  * 循環打印鏈表數據域
  * @param head
  */
 public static void printNode(Node head) {
  while (head != null) {
   System.out.println(head.val);
   head = head.next;
  }
 }

運行結果截圖：

可以看到，經過改善的新遞歸方法實現瞭預期的效果！😁

總結

到此這篇關於Java單鏈表反轉的文章就介紹到這瞭,更多相關Java單鏈表反轉內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：

    None Found