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

為哈巴河等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計(jì)制作服務(wù)，及哈巴河網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、哈巴河網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長期合作。這樣，我們也可以走得更遠(yuǎn)！

首先，咱們要先明確，什么是遞歸。遞歸就是自己調(diào)用自己對吧。比如:有一個(gè)函數(shù)為 f(n) = f(n-1) * n  ，(注意，我這里是舉例子，這個(gè)函數(shù)沒有給出遞歸的結(jié)束條件)給 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：

/**  * 單鏈表反轉(zhuǎn)---遞歸實(shí)現(xiàn)  */ 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);          // 調(diào)用反轉(zhuǎn)方法         Node recursiveList = recursiveList(node1);         System.out.println(recursiveList);     }     /**      *遞歸實(shí)現(xiàn)單鏈表反轉(zhuǎn)      * @param list 為傳入的單鏈表      */     public static Node recursiveList(Node list){         // 如果鏈表為空 或者 鏈表中只有一個(gè)節(jié)點(diǎn),直接返回         // 也是遞歸結(jié)束的條件         if (list == null || list.next == null) return list;         Node recursive = recursiveList(list.next);         // 將 list.next.next 指針指向當(dāng)前鏈表 list         list.next.next = list ;         // 將 list.next 指針指向 null         list.next = null;         // 返回反轉(zhuǎn)之后的鏈表 recursive         return recursive;     } }

經(jīng)過上面的代碼，應(yīng)該能夠看到核心代碼就是，遞歸實(shí)現(xiàn)單鏈表反轉(zhuǎn)部分的那 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;

第一行就是一個(gè)判斷，條件不滿足，那就往下走，第二行是自己調(diào)用自己，程序又回到第一行，不滿足條件程序向下執(zhí)行，自己調(diào)用自己

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

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

接下來程序該執(zhí)行 list.next.next = list 執(zhí)行結(jié)束之后，鏈表大概就是這個(gè)樣子:

那是圖，下面是程序斷點(diǎn)調(diào)試程序的結(jié)果，發(fā)現(xiàn)和上面的圖是一樣的:

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

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

完全一樣有沒有!

OK ，還記得咱們剛開始的遞歸函數(shù)例子嘛?現(xiàn)在執(zhí)行完畢，開始執(zhí)行下一次，咱們繼續(xù)來看，此時(shí)的鏈表是這個(gè)樣子的:

接下來程序執(zhí)行的代碼就是四行了:

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

繼續(xù)執(zhí)行程序，咱們來看結(jié)果，將 list.next.next = list 運(yùn)行結(jié)束時(shí)，此時(shí)鏈表為:

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

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

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

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

反轉(zhuǎn)單鏈表的前 N 個(gè)節(jié)點(diǎn)

OK ，咱們趁熱打鐵一下，剛剛是通過遞歸實(shí)現(xiàn)了整個(gè)單鏈表反轉(zhuǎn)，那如果我只是想反轉(zhuǎn)前 N 個(gè)節(jié)點(diǎn)呢?

比如單鏈表為 1->2->3->4->5->null ，現(xiàn)在我只想反轉(zhuǎn)前三個(gè)節(jié)點(diǎn)，變?yōu)? 3->2->1->4->5->null

有沒有想法?

咱們進(jìn)行整個(gè)單鏈表反轉(zhuǎn)時(shí)，可以理解為傳遞了一個(gè)參數(shù) n ，這個(gè) n  就是單鏈表的長度，然后遞歸程序不斷調(diào)用自己，然后實(shí)現(xiàn)了整個(gè)單鏈表反轉(zhuǎn)。那么，如果我想要反轉(zhuǎn)前 N 個(gè)節(jié)點(diǎn)，是不是傳遞一個(gè)參數(shù) n 來解決就好了?

咱們就直接上代碼了:

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

反轉(zhuǎn)單鏈表的一部分

既然反轉(zhuǎn)整個(gè)單鏈表實(shí)現(xiàn)了，反轉(zhuǎn)前 N 個(gè)節(jié)點(diǎn)實(shí)現(xiàn)了，那么如果有個(gè)需求是反轉(zhuǎn)其中的一部分?jǐn)?shù)據(jù)呢?大概就是這樣，原來的鏈表為  1->2->3->4->5->null ，反轉(zhuǎn)其中的一部分，使反轉(zhuǎn)后的鏈表為  1->4->3->2->5->null

借用反轉(zhuǎn)前 N 個(gè)節(jié)點(diǎn)的思路，是不是我傳兩個(gè)參數(shù)進(jìn)來，一個(gè)是開始反轉(zhuǎn)的節(jié)點(diǎn)，一個(gè)是結(jié)束反轉(zhuǎn)的節(jié)點(diǎn)，然后遞歸操作就可以了?

瞅瞅代碼是怎么寫的:

/**  *反轉(zhuǎn)部分單鏈表  * @param list 為傳入的單鏈表, m 為開始反轉(zhuǎn)的節(jié)點(diǎn), n 為結(jié)束的反轉(zhuǎn)節(jié)點(diǎ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遞歸單鏈表反轉(zhuǎn)”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對怎么理解Java遞歸單鏈表反轉(zhuǎn)這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！