反轉單連結清單的疊代實作不是一個困難的事情，但是遞歸實作就有點難度了，如果再加一點難度，讓你僅僅反轉單連結清單中的一部分，你是否能
夠遞歸實作呢？
本文就來由淺入深，step by step 地解決這個問題。如果你還不會遞歸地反轉單連結清單也沒關系，
本文會從遞歸反轉整個單連結清單開始拓展，隻要你明白單連結清單的結構，相信你能夠有所收獲。
// 單連結清單節點的結構
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
什麼叫反轉單連結清單的一部分呢，就是給你一個索引區間，讓你把單連結清單中這部分元素反轉，其他部分不變：
。疊代的思路大概是：先用一個 for 循環找到第
m
個位置，然後再用一個 for 循環将
m
和
n
之間的元素反轉。但是我們的遞歸解法不用一個 for 循環，純遞歸實作反轉。
疊代實作思路看起來雖然簡單，但是細節問題很多的，反而不容易寫對。相反，遞歸實作就很簡潔優美，下面就由淺入深，先從反轉整個單連結清單說起。
一、遞歸反轉整個連結清單
這個算法可能很多讀者都聽說過，這裡詳細介紹一下，先直接看實作代碼：
ListNode reverse(ListNode head) {
if (head.next == null) return head;
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
看起來是不是感覺不知所雲，完全不能了解這樣為什麼能夠反轉連結清單？這就對了，這個算法常常拿來顯示遞歸的巧妙和優美，我們下面來詳細解釋一下這段代碼。
對于遞歸算法，最重要的就是明确遞歸函數的定義。具體來說，我們的
reverse
函數定義是這樣的：
輸入一個節點head
head
。
明白了函數的定義，在來看這個問題。比如說我們想反轉這個連結清單：
那麼輸入
reverse(head)
後，會在這裡進行遞歸：
ListNode last = reverse(head.next);
不要跳進遞歸（你的腦袋能壓幾個棧呀？），而是要根據剛才的函數定義，來弄清楚這段代碼會産生什麼結果：
這個
reverse(head.next)
執行完成後，整個連結清單就成了這樣：
并且根據函數定義，
reverse
函數會傳回反轉之後的頭結點，我們用變量
last
接收了。
現在再來看下面的代碼：
head.next.next = head;
接下來：
head.next = null;
return last;
神不神奇，這樣整個連結清單就反轉過來了！遞歸代碼就是這麼簡潔優雅，不過其中有兩個地方需要注意：
1、遞歸函數要有 base case，也就是這句：
if (head.next == null) return head;
意思是如果連結清單隻有一個節點的時候反轉也是它自己，直接傳回即可。
2、當連結清單遞歸反轉之後，新的頭結點是
last
，而之前的
head
變成了最後一個節點，别忘了連結清單的末尾要指向 null：
head.next = null;
了解了這兩點後，我們就可以進一步深入了，接下來的問題其實都是在這個算法上的擴充。
二、反轉連結清單前 N 個節點
這次我們實作一個這樣的函數：
// 将連結清單的前 n 個節點反轉（n <= 連結清單長度）
ListNode reverseN(ListNode head, int n)
比如說對于下圖連結清單，執行
reverseN(head, 3)
：
解決思路和反轉整個連結清單差不多，隻要稍加修改即可：
ListNode successor = null; // 後驅節點
// 反轉以 head 為起點的 n 個節點，傳回新的頭結點
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// 記錄第 n + 1 個節點
successor = head.next;
return head;
}
// 以 head.next 為起點，需要反轉前 n - 1 個節點
ListNode last = reverseN(head.next, n - 1);
head.next.next = head;
// 讓反轉之後的 head 節點和後面的節點連起來
head.next = successor;
return last;
}
具體的差別：
1、base case 變為
n == 1
，反轉一個元素，就是它本身，同時
要記錄後驅節點。
2、剛才我們直接把
head.next
設定為 null，因為整個連結清單反轉後原來的
head
變成了整個連結清單的最後一個節點。但現在
head
節點在遞歸反轉之後不一定是最後一個節點了，是以要記錄後驅
successor
（第 n + 1 個節點），反轉之後将
head
連接配接上。
OK，如果這個函數你也能看懂，就離實作「反轉一部分連結清單」不遠了。
三、反轉連結清單的一部分
現在解決我們最開始提出的問題，給一個索引區間
[m,n]
（索引從 1 開始），僅僅反轉區間中的連結清單元素。
ListNode reverseBetween(ListNode head, int m, int n)
首先，如果
m == 1
，就相當于反轉連結清單開頭的
n
個元素嘛，也就是我們剛才實作的功能：
ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
// 相當于反轉前 n 個元素
return reverseN(head, n);
}
// ...
}
如果
m != 1
怎麼辦？如果我們把
head
的索引視為 1，那麼我們是想從第
m
個元素開始反轉對吧；如果把
head.next
的索引視為 1 呢？那麼相對于
head.next
，反轉的區間應該是從第
m - 1
個元素開始的；那麼對于
head.next.next
呢……
差別于疊代思想，這就是遞歸思想，是以我們可以完成代碼：
ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
return reverseN(head, n);
}
// 前進到反轉的起點觸發 base case
head.next = reverseBetween(head.next, m - 1, n - 1);
return head;
}
至此，我們的最終大 BOSS 就被解決了。
四、最後總結
遞歸的思想相對疊代思想，稍微有點難以了解，處理的技巧是：不要跳進遞歸，而是利用明确的定義來實作算法邏輯。
處理看起來比較困難的問題，可以嘗試化整為零，把一些簡單的解法進行修改，解決困難的問題。
值得一提的是，遞歸操作連結清單并不高效。和疊代解法相比，雖然時間複雜度都是 O(N)，但是疊代解法的空間複雜度是 O(1)，而遞歸解法需要堆棧，空間複雜度是 O(N)。是以遞歸操作連結清單可以作為對遞歸算法的練習或者拿去和小夥伴裝逼，但是考慮效率的話還是使用疊代算法更好。