反轉(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)，其他部分不變：
注意這里的索引是從 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è)單鏈表說起。
一鸦致、遞歸反轉(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 接收了。
現(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ò)展鹅很。
二嘶居、反轉(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)了。
三抖所、反轉(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í)或者拿去和小伙伴裝逼，但是考慮效率的話還是使用迭代算法更好垢袱。
我最近精心制作了一份電子書《labuladong的算法小抄》墓拜，分為【動(dòng)態(tài)規(guī)劃】【數(shù)據(jù)結(jié)構(gòu)】【算法思維】【高頻面試】四個(gè)章節(jié)，共 60 多篇原創(chuàng)文章请契，絕對(duì)精品咳榜！限時(shí)開放下載，在我的公眾號(hào) labuladong 后臺(tái)回復(fù)關(guān)鍵詞【pdf】即可免費(fèi)下載爽锥！
歡迎關(guān)注我的公眾號(hào) labuladong涌韩，技術(shù)公眾號(hào)的清流，堅(jiān)持原創(chuàng)氯夷，致力于把問題講清楚臣樱！
