遞歸反轉鏈表：如何拆解復雜問題

華府九五二七 2019-11-15

展開全文

預計閱讀時間：6 分鐘

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

本文就來由淺入深，step by step 地解決這個問題。如果你還不會遞歸地反轉單鏈表也沒關系，本文會從遞歸反轉整個單鏈表開始拓展，只要你明白單鏈表的結構，相信你能夠有所收獲。

// 單鏈表節(jié)點的結構
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

什么叫反轉單鏈表的一部分呢，就是給你一個索引區(qū)間，讓你把單鏈表中這部分元素反轉，其他部分不變：

注意這里的索引是從 1 開始的。迭代的思路大概是：先用一個 for 循環(huán)找到第m個位置，然后再用一個 for 循環(huán)將m和n之間的元素反轉。但是我們的遞歸解法不用任何 for 循環(huán)，純遞歸實現(xiàn)反轉。

迭代實現(xiàn)思路看起來雖然簡單，但是細節(jié)問題很多的，反而不容易寫對。相反，遞歸實現(xiàn)就很簡潔優(yōu)美，下面就由淺入深，先從反轉整個單鏈表說起。

一、遞歸反轉整個鏈表

這個算法可能很多讀者都聽說過，這里詳細介紹一下，先直接看實現(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;
}

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

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

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

明白了函數(shù)的定義，再來看這個問題。比如說我們想反轉這個鏈表：

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

ListNode last = reverse(head.next);

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

按照定義，這個reverse(head.next)執(zhí)行完成后，整個鏈表應該變成了這樣：

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

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

head.next.next = head;

接下來進行的操作：

head.next = null;
return last;

神不神奇，這樣整個鏈表就反轉過來了！遞歸代碼就是這么簡潔優(yōu)雅，不過其中有兩個地方需要注意：

1、遞歸函數(shù)要有 base case，也就是這句：

if (head.next == null) return head;

意思是如果鏈表只有一個節(jié)點的時候反轉也是它自己，直接返回即可。

2、當鏈表遞歸反轉之后，新的頭節(jié)點是last，而之前的head變成了最后一個節(jié)點，別忘了鏈表的末尾要指向 null：

head.next = null;

理解了這兩點后，我們就可以進一步深入了，接下來的問題其實都是在這個算法上的擴展。

二、反轉鏈表前 N 個節(jié)點

這次我們實現(xiàn)一個這樣的函數(shù)：

// 將鏈表的前 n 個節(jié)點反轉（n <= 鏈表長度）
ListNode reverseN(ListNode head, int n)

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

解決思路和反轉整個鏈表差不多，只要稍加修改即可：

ListNode successor = null; // 后驅節(jié)點

// 反轉以 head 為起點的 n 個節(jié)點，返回新的頭結點
ListNode reverseN(ListNode head, int n) {
    if (n == 1) { 
        // 記錄第 n + 1 個節(jié)點
        successor = head.next;
        return head;
    }
    // 以 head.next 為起點，需要反轉前 n - 1 個節(jié)點
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    // 讓反轉之后的 head 節(jié)點和后面的節(jié)點連起來
    head.next = successor;
    return last;
}

具體的區(qū)別：

1、base case 變?yōu)?code>n == 1，反轉一個元素，就是它本身，同時要記錄后驅節(jié)點。

2、剛才我們直接把head.next設置為 null，因為整個鏈表反轉后原來的head變成了整個鏈表的最后一個節(jié)點。但現(xiàn)在head節(jié)點在遞歸反轉之后不一定是最后一個節(jié)點了，所以要記錄后驅successor（第 n + 1 個節(jié)點），反轉之后將head連接上。

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

三、反轉鏈表的一部分

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

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

首先，如果m == 1，就相當于反轉鏈表開頭的n個元素嘛，也就是我們剛才實現(xià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，反轉的區(qū)間應該是從第m - 1個元素開始的；那么對于head.next.next呢……

區(qū)別于迭代思想，這就是遞歸思想，所以我們可以完成代碼：

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前進到反轉的起點觸發(fā) base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

至此，我們的最終大 BOSS 就被解決了。