反轉(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)。但是我們的遞歸解法不用任何 for 循環(huán)，純遞歸實(shí)現(xiàn)反轉(zhuǎn)。
迭代實(shí)現(xiàn)思路看起來雖然簡單，但是細(xì)節(jié)問題很多的，反而不容易寫對。相反，遞歸實(shí)現(xiàn)就很簡潔優(yōu)美，下面就由淺入深，先從反轉(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)后，會(huì)在這里進(jìn)行遞歸：
ListNode last = reverse(head.next);
不要跳進(jìn)遞歸（你的腦袋能壓幾個(gè)棧呀？），而是要根據(jù)剛才的函數(shù)定義，來弄清楚這段代碼會(huì)產(chǎn)生什么結(jié)果：
按照定義，這個(gè)reverse(head.next)執(zhí)行完成后，整個(gè)鏈表應(yīng)該變成了這樣：
并且根據(jù)函數(shù)定義，reverse函數(shù)會(huì)返回反轉(zhuǎn)之后的頭結(jié)點(diǎn)，我們用變量last接收了。
現(xiàn)在再來看下面的代碼：
head.next.next = head;
接下來進(jìn)行的操作：
head.next = null;
return last;
神不神奇，這樣整個(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：
head.next = null;
理解了這兩點(diǎn)后，我們就可以進(jìn)一步深入了，接下來的問題其實(shí)都是在這個(gè)算法上的擴(kuò)展。
這次我們實(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è)鏈表差不多，只要稍加修改即可：
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)?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)了。
現(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)對吧；如果把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 就被解決了。
遞歸的思想相對迭代思想，稍微有點(diǎn)難以理解，處理的技巧是：不要跳進(jìn)遞歸，而是利用明確的定義來實(shí)現(xiàn)算法邏輯。
處理看起來比較困難的問題，可以嘗試化整為零，把一些簡單的解法進(jìn)行修改，解決困難的問題。
值得一提的是，遞歸操作鏈表并不高效。和迭代解法相比，雖然時(shí)間復(fù)雜度都是 O(N)，但是迭代解法的空間復(fù)雜度是 O(1)，而遞歸解法需要堆棧，空間復(fù)雜度是 O(N)。所以遞歸操作鏈表可以作為對遞歸算法的練習(xí)或者拿去和小伙伴裝逼，但是考慮效率的話還是使用迭代算法更好。
聯(lián)系客服
