教你怎么實(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)類以方便運(yùn)行測(cè)試：

 /**
 * 結(jié)點(diǎn)類
 * （因?yàn)楹罄m(xù)在main方法中運(yùn)行，為了方便定義為static內(nèi)部類）
 */
 static class Node {
 int val; // 數(shù)據(jù)域
 Node next; // 指針域，指向下一個(gè)結(jié)點(diǎn)

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

通過循環(huán)遍歷方式實(shí)現(xiàn)鏈表反轉(zhuǎn)

實(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)?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)椋?);
  printNode(head);

  // 普通方式反轉(zhuǎn)鏈表
  System.out.println("循環(huán)方式反轉(zhuǎn)鏈表指向?yà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;
  }
 }

運(yùn)行結(jié)果如圖：

可以看到，原先指向?yàn)?N1 -> N2 -> N3 -> N4 的鏈表，運(yùn)行反轉(zhuǎn)方法后，其指向已變?yōu)?N4 -> N3 -> N2 -> N1

通過遞歸方式實(shí)現(xiàn)鏈表反轉(zhuǎn)

實(shí)現(xiàn)思路：從鏈表頭結(jié)點(diǎn)出發(fā)，依次遞歸遍歷每一個(gè)結(jié)點(diǎn)，并更改結(jié)點(diǎn)對(duì)應(yīng)的指針域，使其指向前一個(gè)結(jié)點(diǎn)（沒錯(cuò)，實(shí)際每一次遞歸里的處理過程跟上面的循環(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)?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)椋?);
  printNode(head);

  // 遞歸方式反轉(zhuǎn)鏈表
  System.out.println("遞歸方式反轉(zhuǎn)鏈表指向?yàn)椋?);
  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類的實(shí)例head作為參數(shù)

根據(jù)Java中 方法調(diào)用傳參中，基本類型是值傳遞，對(duì)象類型是引用傳遞 可得 =>

因?yàn)樵谡{(diào)用遞歸函數(shù)時(shí)傳遞了head對(duì)象的引用，且在遞歸函數(shù)運(yùn)行過程中，我們已經(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)行效果截圖：

最終的程序運(yùn)行結(jié)果與我的設(shè)想大相徑庭！

那么，問題出在哪里呢？

遞歸方式反轉(zhuǎn)鏈表問題排查與延伸問題定位

既然程序運(yùn)行效果與預(yù)期效果不符，那我們就在head對(duì)象引用可能發(fā)生變化的地方加入注釋打印一下對(duì)象地址，看看能不能發(fā)現(xiàn)問題在哪：

加入注釋后的代碼如下：

public static void main(String[] args) {
 // 構(gòu)造測(cè)試用例，鏈表指向?yàn)?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)椋?);
 printNode(head);
 
 
 // 遞歸方式反轉(zhuǎn)鏈表
 System.out.println("遞歸方式反轉(zhuǎn)鏈表指向?yàn)椋?);
 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ā)生了變化！

由此說明遞歸函數(shù)的執(zhí)行并不是在做無用功，而是切切實(shí)實(shí)改變了原鏈表的各結(jié)點(diǎn)指向順序！

只是因?yàn)檫f歸函數(shù)執(zhí)行完成后，并沒有成功讓傳入的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根本無法遍歷到新鏈表的其他結(jié)點(diǎn)。。。

問題延伸：探究Java方法調(diào)用中的參數(shù)傳遞實(shí)質(zhì)

由上面的問題定位可知，問題出在我對(duì)Java方法調(diào)用中的參數(shù)傳遞理解有偏差，那么接下來就來詳細(xì)探究一下Java方法調(diào)用中的參數(shù)傳遞過程吧！

形參與實(shí)參

測(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ù)類型如果是基本數(shù)據(jù)類型（byte、short、int、long、float、double、boolean、char），則調(diào)用方法時(shí)，實(shí)參到形參的傳遞實(shí)際是值傳遞，傳遞的是實(shí)際參數(shù)值的副本（拷貝）

因此，在方法體中任意修改形參的值，并不會(huì)影響到方法體外的實(shí)參的值

引用傳遞

方法定義中的形式參數(shù)類型如果是對(duì)象類型（含基本數(shù)據(jù)類型的數(shù)組），則調(diào)用方法時(shí)，實(shí)參到形參的傳遞實(shí)際也是值傳遞，傳遞的是實(shí)參對(duì)象的引用地址

如何理解這個(gè) 實(shí)參對(duì)象的引用地址 的概念呢？讓我們來看看示例代碼運(yùn)行時(shí)的內(nèi)存模型圖（簡(jiǎn)單抽象了stack和heap的部分，如有不對(duì)歡迎指正 ）

如圖，main方法和recursionNode方法執(zhí)行時(shí)實(shí)際是作為不同的棧幀入棧到當(dāng)前線程的虛擬機(jī)棧中

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

recursionNode方法中的 headNode 引用實(shí)際保存的也是一個(gè)地址，通過這個(gè)地址可以找到堆中的一個(gè)Node對(duì)象

那么在main方法中調(diào)用recursionNode方法，實(shí)參 head 到形參 headNode 的傳遞過程中，到底傳遞的是什么呢？

很明顯，傳遞的就是那個(gè)能尋址到堆中某個(gè)Node對(duì)象的 地址（劃重點(diǎn)，要考！）

由此，實(shí)參 head 對(duì)象引用和形參 headNode 對(duì)象引用具有了相同的地址值，指向堆中的同一個(gè)Node對(duì)象

通過這兩個(gè)引用中的任何一個(gè)，都可以改變堆中對(duì)應(yīng)的那個(gè)對(duì)象的屬性和狀態(tài)

遞歸方法調(diào)用后發(fā)生了什么

理解了對(duì)象引用傳遞的實(shí)質(zhì)后，再回過頭來看上面遞歸方法調(diào)用后實(shí)際結(jié)果與預(yù)期結(jié)果不一致的問題，一切就迎刃而解了

如圖，遞歸調(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)

    /**
     * 遞歸實(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)?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)椋?);
        printNode(head);

        // 新遞歸方式反轉(zhuǎn)鏈表
        System.out.println("新遞歸方式反轉(zhuǎn)鏈表指向?yàn)椋?);
        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;
        }
    }

運(yùn)行結(jié)果截圖：

可以看到，經(jīng)過改善的新遞歸方法實(shí)現(xiàn)了預(yù)期的效果！

以上就是關(guān)于使用Java語言實(shí)現(xiàn)單鏈表反轉(zhuǎn)的全部?jī)?nèi)容，如果想要了解更多和Java數(shù)據(jù)結(jié)構(gòu)的相關(guān)內(nèi)容，請(qǐng)關(guān)注W3Cschool以前的文章或者繼續(xù)瀏覽接下來的內(nèi)容，如果對(duì)您的學(xué)習(xí)有所幫助，請(qǐng)多多支持和關(guān)注。