反轉(zhuǎn)單鏈表的迭代實(shí)現(xiàn)不是一個(gè)困難的事情，但是遞歸實(shí)現(xiàn)就有點(diǎn)難度了，如果再加一點(diǎn)難度，讓你僅僅反轉(zhuǎn)單鏈表中的一部分，你是否能夠遞歸實(shí)現(xiàn)呢？

本文就來由淺入深，step by step 地解決這個(gè)問題。如果你還不會遞歸地反轉(zhuǎn)單鏈表也沒關(guān)系，本文會從遞歸反轉(zhuǎn)整個(gè)單鏈表開始拓展，只要你明白單鏈表的結(jié)構(gòu)，相信你能夠有所收獲。

什么叫反轉(zhuǎn)單鏈表的一部分呢，就是給你一個(gè)索引區(qū)間，讓你把單鏈表中這部分元素反轉(zhuǎn)，其他部分不變：

注意這里的索引是從 1 開始的。迭代的思路大概是：先用一個(gè) for 循環(huán)找到第m個(gè)位置，然后再用一個(gè) for 循環(huán)將m和n之間的元素反轉(zhuǎn)。但是我們的遞歸解法不用任何 for 循環(huán)，純遞歸實(shí)現(xiàn)反轉(zhuǎn)。

迭代實(shí)現(xiàn)思路看起來雖然簡單，但是細(xì)節(jié)問題很多的，反而不容易寫對。相反，遞歸實(shí)現(xiàn)就很簡潔優(yōu)美，下面就由淺入深，先從反轉(zhuǎn)整個(gè)單鏈表說起。

一、遞歸反轉(zhuǎn)整個(gè)鏈表

這個(gè)算法可能很多讀者都聽說過，這里詳細(xì)介紹一下，先直接看實(shí)現(xiàn)代碼：

ListNode reverse(ListNode head) {
    if (head.next == null) return head;
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

看起來是不是感覺不知所云，完全不能理解這樣為什么能夠反轉(zhuǎn)鏈表？這就對了，這個(gè)算法常常拿來顯示遞歸的巧妙和優(yōu)美，我們下面來詳細(xì)解釋一下這段代碼。

對于遞歸算法，最重要的就是明確遞歸函數(shù)的定義。具體來說，我們的reverse函數(shù)定義是這樣的：

輸入一個(gè)節(jié)點(diǎn)head，將「以head為起點(diǎn)」的鏈表反轉(zhuǎn)，并返回反轉(zhuǎn)之后的頭結(jié)點(diǎn)。

明白了函數(shù)的定義，再來看這個(gè)問題。比如說我們想反轉(zhuǎn)這個(gè)鏈表：

那么輸入reverse(head)后，會在這里進(jìn)行遞歸：

不要跳進(jìn)遞歸（你的腦袋能壓幾個(gè)棧呀？），而是要根據(jù)剛才的函數(shù)定義，來弄清楚這段代碼會產(chǎn)生什么結(jié)果：

按照定義，這個(gè)reverse(head.next)執(zhí)行完成后，整個(gè)鏈表應(yīng)該變成了這樣：

并且根據(jù)函數(shù)定義，reverse函數(shù)會返回反轉(zhuǎn)之后的頭結(jié)點(diǎn)，我們用變量last接收了。

現(xiàn)在再來看下面的代碼：

head.next.next = head;

接下來進(jìn)行的操作：

神不神奇，這樣整個(gè)鏈表就反轉(zhuǎn)過來了！遞歸代碼就是這么簡潔優(yōu)雅，不過其中有兩個(gè)地方需要注意：

1、遞歸函數(shù)要有 base case，也就是這句：

if (head.next == null) return head;

意思是如果鏈表只有一個(gè)節(jié)點(diǎn)的時(shí)候反轉(zhuǎn)也是它自己，直接返回即可。

2、當(dāng)鏈表遞歸反轉(zhuǎn)之后，新的頭節(jié)點(diǎn)是last，而之前的head變成了最后一個(gè)節(jié)點(diǎn)，別忘了鏈表的末尾要指向 null：

理解了這兩點(diǎn)后，我們就可以進(jìn)一步深入了，接下來的問題其實(shí)都是在這個(gè)算法上的擴(kuò)展。

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

這次我們實(shí)現(xiàn)一個(gè)這樣的函數(shù)：

// 將鏈表的前 n 個(gè)節(jié)點(diǎn)反轉(zhuǎn)（n <= 鏈表長度）
ListNode reverseN(ListNode head, int n)

比如說對于下圖鏈表，執(zhí)行reverseN(head, 3)：

解決思路和反轉(zhuǎn)整個(gè)鏈表差不多，只要稍加修改即可：

具體的區(qū)別：

1、base case 變?yōu)?code>n == 1，反轉(zhuǎn)一個(gè)元素，就是它本身，同時(shí)要記錄后驅(qū)節(jié)點(diǎn)。

2、剛才我們直接把head.next設(shè)置為 null，因?yàn)檎麄€(gè)鏈表反轉(zhuǎn)后原來的head變成了整個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)。但現(xiàn)在head節(jié)點(diǎn)在遞歸反轉(zhuǎn)之后不一定是最后一個(gè)節(jié)點(diǎn)了，所以要記錄后驅(qū)successor（第 n + 1 個(gè)節(jié)點(diǎn)），反轉(zhuǎn)之后將head連接上。

OK，如果這個(gè)函數(shù)你也能看懂，就離實(shí)現(xiàn)「反轉(zhuǎn)一部分鏈表」不遠(yuǎn)了。

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

現(xiàn)在解決我們最開始提出的問題，給一個(gè)索引區(qū)間[m,n]（索引從 1 開始），僅僅反轉(zhuǎn)區(qū)間中的鏈表元素。

ListNode reverseBetween(ListNode head, int m, int n)

首先，如果m == 1，就相當(dāng)于反轉(zhuǎn)鏈表開頭的n個(gè)元素嘛，也就是我們剛才實(shí)現(xiàn)的功能：

如果m != 1怎么辦？如果我們把head的索引視為 1，那么我們是想從第m個(gè)元素開始反轉(zhuǎn)對吧；如果把head.next的索引視為 1 呢？那么相對于head.next，反轉(zhuǎn)的區(qū)間應(yīng)該是從第m - 1個(gè)元素開始的；那么對于head.next.next呢……

區(qū)別于迭代思想，這就是遞歸思想，所以我們可以完成代碼：

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前進(jìn)到反轉(zhuǎn)的起點(diǎn)觸發(fā) base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

至此，我們的最終大 BOSS 就被解決了。

四、最后總結(jié)

遞歸的思想相對迭代思想，稍微有點(diǎn)難以理解，處理的技巧是：不要跳進(jìn)遞歸，而是利用明確的定義來實(shí)現(xiàn)算法邏輯。

處理看起來比較困難的問題，可以嘗試化整為零，把一些簡單的解法進(jìn)行修改，解決困難的問題。

值得一提的是，遞歸操作鏈表并不高效。和迭代解法相比，雖然時(shí)間復(fù)雜度都是 O(N)，但是迭代解法的空間復(fù)雜度是 O(1)，而遞歸解法需要堆棧，空間復(fù)雜度是 O(N)。所以遞歸操作鏈表可以作為對遞歸算法的練習(xí)或者拿去和小伙伴裝逼，但是考慮效率的話還是使用迭代算法更好。