怎么理解Java遞歸單鏈表反轉

這篇文章主要講解了“怎么理解Java遞歸單鏈表反轉”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“怎么理解Java遞歸單鏈表反轉”吧！

首先，咱們要先明確，什么是遞歸。遞歸就是自己調用自己對吧。比如:有一個函數為 f(n) = f(n-1) * n  ，(注意，我這里是舉例子，這個函數沒有給出遞歸的結束條件)給 n 賦值為 5 ， 則:

--> f(5) --> 5 * f(4) --> 5 * ( 4 * f(3)) --> 5 * ( 4 * (3 * f(2))) --> 5 * ( 4 * ( 3 * ( 2 * f (1)))) --> 5 * ( 4 * ( 3 * ( 2 * 1))) --> 5 * ( 4 * ( 3 * 2)) --> 5 * ( 4 * 6 ) --> 5 * 24 --> 120

在看完例子之后，咱們接下來不 BB ，直接 show code：

/**  * 單鏈表反轉---遞歸實現  */ public class ReverseSingleList {     public static class Node{         private int data;         private Node next;          public Node( int data , Node next){             this.data = data;             this.next = next;         }          public int getData(){return  data;}     }     public static void main(String[] args){         // 初始化單鏈表         Node node5 = new Node(5,null);         Node node4 = new Node(4,node5);         Node node3 = new Node(3,node4);         Node node2 = new Node(2,node3);         Node node1 = new Node(1,node2);          // 調用反轉方法         Node recursiveList = recursiveList(node1);         System.out.println(recursiveList);     }     /**      *遞歸實現單鏈表反轉      * @param list 為傳入的單鏈表      */     public static Node recursiveList(Node list){         // 如果鏈表為空 或者 鏈表中只有一個節點,直接返回         // 也是遞歸結束的條件         if (list == null || list.next == null) return list;         Node recursive = recursiveList(list.next);         // 將 list.next.next 指針指向當前鏈表 list         list.next.next = list ;         // 將 list.next 指針指向 null         list.next = null;         // 返回反轉之后的鏈表 recursive         return recursive;     } }

經過上面的代碼，應該能夠看到核心代碼就是，遞歸實現單鏈表反轉部分的那 5 行代碼，別小看了這 5 行代碼，想要真正弄清楚還真的挺不容易的。

我把這 5 行代碼貼在這里，咱們一行行分析，爭取看完這篇博客就能懂~(注釋我就去掉了，咱們專心看這幾行核心代碼)

if (list == null || list.next == null) return list; Node recursive = recursiveList(list.next); list.next.next = list ; list.next = null; return recursive;

第一行就是一個判斷，條件不滿足，那就往下走，第二行是自己調用自己，程序又回到第一行，不滿足條件程序向下執行，自己調用自己

就這樣循環到符合條件為止，那么什么時候符合條件呢?也就是 list == null 或者 list.next == null 時，看一下自己定義的鏈表是  1->2->3->4->5->null ，所以符合條件時，此時的鏈表為 5->null  ，符合條件之后，程序繼續向下執行，在執行完 Node recursive = recursiveList(list.next);  這行代碼之后，咱們來看一下此時的程序執行結果:

我把上面這個給畫出來(阿粉的畫工不是不好，不要在乎它的美丑~)

接下來程序該執行 list.next.next = list 執行結束之后，鏈表大概就是這個樣子:

那是圖，下面是程序斷點調試程序的結果，發現和上面的圖是一樣的:

程序繼續向下走 list.next = null ，也就是說，將 list 的 next 指針指向 null :

從圖中看到， list 為 4->null ， recursive 為 5->4->null  ，咱們來看看程序的結果，是不是和圖相符:

完全一樣有沒有!

OK ，還記得咱們剛開始的遞歸函數例子嘛?現在執行完畢，開始執行下一次，咱們繼續來看，此時的鏈表是這個樣子的:

接下來程序執行的代碼就是四行了:

Node recursive = recursiveList(list.next); list.next.next = list ; list.next = null; return recursive;

繼續執行程序，咱們來看結果，將 list.next.next = list 運行結束時，此時鏈表為:

從圖中能夠看到，鏈表 list 為 3->4->3->4 循環中， recursive 為  5->4->3->4->3 循環，咱們看一下程序是不是也是如此(在這里我截了兩個循環作為示例):

接下來程序執行 list.next = null ，執行完畢之后，就是將 list 的 next 指針指向 null :

從圖中能夠看出來， list 為 3->null ， recursive 為 5->4->3->null  ，上圖看看實際結果和分析的是否一致:

說明什么?!說明咱們上面的分析是正確的。接下來的程序分析，讀者們就自行研究吧，相信接下來的分析就難不倒咱們聰明的讀者啦~

反轉單鏈表的前 N 個節點

OK ，咱們趁熱打鐵一下，剛剛是通過遞歸實現了整個單鏈表反轉，那如果我只是想反轉前 N 個節點呢?

比如單鏈表為 1->2->3->4->5->null ，現在我只想反轉前三個節點，變為  3->2->1->4->5->null

有沒有想法?

咱們進行整個單鏈表反轉時，可以理解為傳遞了一個參數 n ，這個 n  就是單鏈表的長度，然后遞歸程序不斷調用自己，然后實現了整個單鏈表反轉。那么，如果我想要反轉前 N 個節點，是不是傳遞一個參數 n 來解決就好了?

咱們就直接上代碼了:

/**    *反轉單鏈表前 n 個節點    * @param list 為傳入的單鏈表 , n 為要反轉的前 n 個節點    */   public static Node next;   public static Node reverseListN(Node list,int n){       if (n == 1) {           // 要進行反轉鏈表時,先將 list 后的節點數據保存到 next 中           next = list.next;           return  list;       }        Node reverse = reverseListN(list.next , n-1);       list.next.next = list;       // 將 list.next 的指針指向沒有進行反轉的鏈表       list.next = next ;       return reverse;   }

反轉單鏈表的一部分

既然反轉整個單鏈表實現了，反轉前 N 個節點實現了，那么如果有個需求是反轉其中的一部分數據呢?大概就是這樣，原來的鏈表為  1->2->3->4->5->null ，反轉其中的一部分，使反轉后的鏈表為  1->4->3->2->5->null

借用反轉前 N 個節點的思路，是不是我傳兩個參數進來，一個是開始反轉的節點，一個是結束反轉的節點，然后遞歸操作就可以了?

瞅瞅代碼是怎么寫的:

/**  *反轉部分單鏈表  * @param list 為傳入的單鏈表, m 為開始反轉的節點, n 為結束的反轉節點  */ public static Node reverseBetween(Node list , int m , int n){     if (m == 1){         return reverseListN(list,n);     }     list.next = reverseBetween(list.next,m-1,n-1);     return list; }

感謝各位的閱讀，以上就是“怎么理解Java遞歸單鏈表反轉”的內容了，經過本文的學習后，相信大家對怎么理解Java遞歸單鏈表反轉這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！