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

本文就來(lái)由淺入深，step by step 地解決這個(gè)問(wèn)題。如果你還不會(huì)遞歸地反轉(zhuǎn)單鏈表也沒(méi)關(guān)系，本文會(huì)從遞歸反轉(zhuǎn)整個(gè)單鏈表開(kāi)始拓展，只要你明白單鏈表的結(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)，其他部分不變：

image

注意這里的索引是從 1 開(kāi)始的。迭代的思路大概是：先用一個(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)思路看起來(lái)雖然簡(jiǎn)單，但是細(xì)節(jié)問(wèn)題很多的，反而不容易寫(xiě)對(duì)。相反，遞歸實(shí)現(xiàn)就很簡(jiǎn)潔優(yōu)美，下面就由淺入深，先從反轉(zhuǎn)整個(gè)單鏈表說(shuō)起。

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

這個(gè)算法可能很多讀者都聽(tīng)說(shuō)過(guò)，這里詳細(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;
}

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

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

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

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

image

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

ListNode last = reverse(head.next);

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

image

這個(gè) reverse(head.next) 執(zhí)行完成后，整個(gè)鏈表就成了這樣：

image

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

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

head.next.next = head;

image

接下來(lái)：

head.next = null;
return last;

image

神不神奇，這樣整個(gè)鏈表就反轉(zhuǎn)過(guò)來(lái)了！遞歸代碼就是這么簡(jiǎn)潔優(yōu)雅，不過(guò)其中有兩個(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)一步深入了，接下來(lái)的問(wè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)

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

image

解決思路和反轉(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)連起來(lái)
    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)后原來(lái)的 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 連接上。

image

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

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

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

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

首先，如果 m == 1，就相當(dāng)于反轉(zhuǎn)鏈表開(kāi)頭的 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è)元素開(kāi)始反轉(zhuǎn)對(duì)吧；如果把 head.next 的索引視為 1 呢？那么相對(duì)于 head.next，反轉(zhuǎn)的區(qū)間應(yīng)該是從第 m - 1 個(gè)元素開(kāi)始的；那么對(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)遞歸，而是利用明確的定義來(lái)實(shí)現(xiàn)算法邏輯。

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

值得一提的是，遞歸操作鏈表并不高效。和迭代解法相比，雖然時(shí)間復(fù)雜度都是 O(N)，但是迭代解法的空間復(fù)雜度是 O(1)，而遞歸解法需要堆棧，空間復(fù)雜度是 O(N)。所以遞歸操作鏈表可以作為對(duì)遞歸算法的練習(xí)或者拿去和小伙伴裝逼，但是考慮效率的話(huà)還是使用迭代算法更好。
我最近精心制作了一份電子書(shū)《labuladong的算法小抄》，分為【動(dòng)態(tài)規(guī)劃】【數(shù)據(jù)結(jié)構(gòu)】【算法思維】【高頻面試】四個(gè)章節(jié)，共 60 多篇原創(chuàng)文章，絕對(duì)精品！限時(shí)開(kāi)放下載，在我的公眾號(hào) labuladong 后臺(tái)回復(fù)關(guān)鍵詞【pdf】即可免費(fèi)下載！

目錄

歡迎關(guān)注我的公眾號(hào) labuladong，技術(shù)公眾號(hào)的清流，堅(jiān)持原創(chuàng)，致力于把問(wèn)題講清楚！

labuladong