[[320439]]

關(guān)于單鏈表反轉(zhuǎn)，阿粉以前寫(xiě)過(guò)一篇文章，是用迭代法實(shí)現(xiàn)的，還有一種方法是使用遞歸來(lái)實(shí)現(xiàn)的，阿粉一直沒(méi)敢寫(xiě)，因?yàn)楹ε轮v不清楚。但是不能因?yàn)楹ε轮v不清楚就不寫(xiě)了，對(duì)不對(duì)。

所以這篇文章來(lái)使用遞歸來(lái)實(shí)現(xiàn)一下，并且嘗試將里面的細(xì)節(jié)一一剖出來(lái)，不廢話。

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

在看完例子之后，咱們接下來(lái)不 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)過(guò)上面的代碼，應(yīng)該能夠看到核心代碼就是，遞歸實(shí)現(xiàn)單鏈表反轉(zhuǎn)部分的那 5 行代碼，別小看了這 5 行代碼，想要真正弄清楚還真的挺不容易的。

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

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); 這行代碼之后，咱們來(lái)看一下此時(shí)的程序執(zhí)行結(jié)果:

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

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

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

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

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

完全一樣有沒(méi)有!

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

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

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

繼續(xù)執(zhí)行程序，咱們來(lái)看結(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)作為示例):

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

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

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

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

OK ，咱們趁熱打鐵一下，剛剛是通過(guò)遞歸實(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

有沒(méi)有想法?

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

咱們就直接上代碼了:

/** 
   *反轉(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 的指針指向沒(méi)有進(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ù)呢?大概就是這樣，原來(lái)的鏈表為 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)來(lái)，一個(gè)是開(kāi)始反轉(zhuǎn)的節(jié)點(diǎn)，一個(gè)是結(jié)束反轉(zhuǎn)的節(jié)點(diǎn)，然后遞歸操作就可以了?

瞅瞅代碼是怎么寫(xiě)的:

/** 
 *反轉(zhuǎn)部分單鏈表 
 * @param list 為傳入的單鏈表, m 為開(kāi)始反轉(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; 
} 

終于給弄清楚了 最后兩個(gè)例子，讀者們可以自行研究，我這里因?yàn)槠膯?wèn)題就不進(jìn)行解析了，如果第一個(gè)例子自己能夠剖析清楚，下面兩個(gè)也沒(méi)啥大問(wèn)題~

其中實(shí)現(xiàn)的思路借鑒了網(wǎng)上，真是太巧妙了，分享給大家。

最后，看到阿粉又是調(diào)試程序又是畫(huà)圖來(lái)幫助大家理解的份上，點(diǎn)點(diǎn)在看支持一下?