讀完本文，你可以去力扣拿下如下題目：
-----------
反轉(zhuǎn)單鏈表的迭代實(shí)現(xiàn)不是一個(gè)困難的事情，但是遞歸實(shí)現(xiàn)就有點(diǎn)難度了，如果再加一點(diǎn)難度，讓你僅僅反轉(zhuǎn)單鏈表中的一部分，你是否能夠遞歸實(shí)現(xiàn)呢？
本文就來由淺入深，step by step 地解決這個(gè)問題。如果你還不會(huì)遞歸地反轉(zhuǎn)單鏈表也沒關(guān)系，本文會(huì)從遞歸反轉(zhuǎn)整個(gè)單鏈表開始拓展，只要你明白單鏈表的結(jié)構(gòu)，相信你能夠有所收獲。
// 單鏈表節(jié)點(diǎn)的結(jié)構(gòu)
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
什么叫反轉(zhuǎn)單鏈表的一部分呢，就是給你一個(gè)索引區(qū)間，讓你把單鏈表中這部分元素反轉(zhuǎn)，其他部分不變：
e
注意這里的索引是從 1 開始的。迭代的思路大概是：先用一個(gè) for 循環(huán)找到第 m 個(gè)位置，然后再用一個(gè) for 循環(huán)將 m 和 n 之間的元素反轉(zhuǎn)。但是我們的遞歸解法不用一個(gè) for 循環(huán)，純遞歸實(shí)現(xiàn)反轉(zhuǎn)。
迭代實(shí)現(xiàn)思路看起來雖然簡(jiǎn)單，但是細(xì)節(jié)問題很多的，反而不容易寫對(duì)。相反，遞歸實(shí)現(xiàn)就很簡(jiǎn)潔優(yōu)美，下面就由淺入深，先從反轉(zhuǎn)整個(gè)單鏈表說起。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
一、遞歸反轉(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)鏈表？這就對(duì)了，這個(gè)算法常常拿來顯示遞歸的巧妙和優(yōu)美，我們下面來詳細(xì)解釋一下這段代碼。
對(duì)于遞歸算法，最重要的就是明確遞歸函數(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) 后，會(huì)在這里進(jìn)行遞歸：
ListNode last = reverse(head.next);
不要跳進(jìn)遞歸（你的腦袋能壓幾個(gè)棧呀？），而是要根據(jù)剛才的函數(shù)定義，來弄清楚這段代碼會(huì)產(chǎn)生什么結(jié)果：
這個(gè) reverse(head.next) 執(zhí)行完成后，整個(gè)鏈表就成了這樣：
并且根據(jù)函數(shù)定義，reverse 函數(shù)會(huì)返回反轉(zhuǎn)之后的頭結(jié)點(diǎn)，我們用變量 last 接收了。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
現(xiàn)在再來看下面的代碼：
head.next.next = head;
接下來：
head.next = null;
return last;
神不神奇，這樣整個(gè)鏈表就反轉(zhuǎn)過來了！遞歸代碼就是這么簡(jiǎ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：
head.next = null;
理解了這兩點(diǎn)后，我們就可以進(jìn)一步深入了，接下來的問題其實(shí)都是在這個(gè)算法上的擴(kuò)展。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
二、反轉(zhuǎn)鏈表前 N 個(gè)節(jié)點(diǎn)
這次我們實(shí)現(xiàn)一個(gè)這樣的函數(shù)：
// 將鏈表的前 n 個(gè)節(jié)點(diǎn)反轉(zhuǎn)（n <= 鏈表長(zhǎng)度）
ListNode reverseN(ListNode head, int n)
比如說對(duì)于下圖鏈表，執(zhí)行 reverseN(head, 3)：
解決思路和反轉(zhuǎn)整個(gè)鏈表差不多，只要稍加修改即可：
ListNode successor = null; // 后驅(qū)節(jié)點(diǎn)
// 反轉(zhuǎn)以 head 為起點(diǎn)的 n 個(gè)節(jié)點(diǎn)，返回新的頭結(jié)點(diǎn)
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// 記錄第 n + 1 個(gè)節(jié)點(diǎn)
successor = head.next;
return head;
}
// 以 head.next 為起點(diǎn)，需要反轉(zhuǎn)前 n - 1 個(gè)節(jié)點(diǎn)
ListNode last = reverseN(head.next, n - 1);
head.next.next = head;
// 讓反轉(zhuǎn)之后的 head 節(jié)點(diǎn)和后面的節(jié)點(diǎn)連起來
head.next = successor;
return last;
}
具體的區(qū)別：
1、base case 變?yōu)?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)了。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
三、反轉(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)的功能：
ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
// 相當(dāng)于反轉(zhuǎn)前 n 個(gè)元素
return reverseN(head, n);
}
// ...
}
如果 m != 1 怎么辦？如果我們把 head 的索引視為 1，那么我們是想從第 m 個(gè)元素開始反轉(zhuǎn)對(duì)吧；如果把 head.next 的索引視為 1 呢？那么相對(duì)于 head.next，反轉(zhuǎn)的區(qū)間應(yīng)該是從第 m - 1 個(gè)元素開始的；那么對(duì)于 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é)
遞歸的思想相對(duì)迭代思想，稍微有點(diǎn)難以理解，處理的技巧是：不要跳進(jìn)遞歸，而是利用明確的定義來實(shí)現(xiàn)算法邏輯。
處理看起來比較困難的問題，可以嘗試化整為零，把一些簡(jiǎn)單的解法進(jìn)行修改，解決困難的問題。
值得一提的是，遞歸操作鏈表并不高效。和迭代解法相比，雖然時(shí)間復(fù)雜度都是 O(N)，但是迭代解法的空間復(fù)雜度是 O(1)，而遞歸解法需要堆棧，空間復(fù)雜度是 O(N)。所以遞歸操作鏈表可以作為對(duì)遞歸算法的練習(xí)或者拿去和小伙伴裝逼，但是考慮效率的話還是使用迭代算法更好。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目，建議收藏！對(duì)應(yīng)的 GitHub 算法倉(cāng)庫(kù) 已經(jīng)獲得了 70k star，歡迎標(biāo)星！
