遞歸實現(xiàn)鏈表操作

華府九五二七 2019-11-15

展開全文

預(yù)計閱讀時間： 7分鐘

PS：由于微信的更新將所有文章字體縮小了，所以本文是按照新版微信的字體大小進(jìn)行的排版，盡量讓所有代碼塊、解釋、圖片同時容納在屏幕內(nèi)，方便閱讀。

鏈表是一種很簡單數(shù)據(jù)結(jié)構(gòu)，但是在面試題中常常出現(xiàn)。鏈表的每個節(jié)點包含一個指向下一個節(jié)點的指針，跟串糖葫蘆似得穿起來。

struct Node {
    int val;
    Node* next;
}

鏈表結(jié)構(gòu)簡單，但是卻很漂亮，因為它具有天生的遞歸結(jié)構(gòu)，所以幾乎所有鏈表的操作都有一個遞歸的實現(xiàn)方式，這也是本篇文章的主要目的：教大家遞歸地處理鏈表。

這篇文章主要寫兩個鏈表最?？疾斓膬蓚€操作，包括鏈表翻轉(zhuǎn)和兩個有序鏈表的合并，并且給出迭代和遞歸兩種解法。

首先來簡單熱下身，給一個鏈表頭，求這個鏈表的長度。

迭代版本：

int size(Node* head) {
    int len = 0;
    while(head != NULL) {
        head = head->next;
        len++;
    }
    return len;
}

遞歸版本：

int size(Node* head) {
    if (head == NULL) return 0;
    return size(head->next) + 1;
}

現(xiàn)在開始正題，先來講解一下翻轉(zhuǎn)一個鏈表。解釋一下：

比如有個鏈表是 1->2->3->4，你要把它變成 4->3->2->1，返回頭結(jié)點（這里就是 4 那個節(jié)點）。

首先，看一下迭代算法：

Node* reverse(Node* head) {
    if (head == NULL) return NULL;
    Node *curr = head, *prev = NULL;
    while (curr != NULL){
        Node* next = curr->next;
        curr->next = prev;
        prve = curr;
        curr = next;
    }
    return prev;
}

畫個中間過程的圖就好理解了，注意 prev 指向的節(jié)點和 curr 是不相連的，因為它們在算法開始的時候就不相連。prev 走過之后的鏈表已經(jīng)翻轉(zhuǎn)完成了：

這三個指針的操作過程莫名讓我想起科普片里細(xì)胞中的酶組裝氨基酸的過程。。。

下面上遞歸算法，很漂亮，但絕對得不好理解（很適合拿去裝逼）：

Node* reverse(Node* head) {
    if (head == NULL || head->next == NULL) 
        return head;
    Node* newHead = reverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

這個算法很精妙，我畫個圖就容易理解了（明白遞歸函數(shù)是干什么的，并相信它一定能做好）：

理解之后就一目了然了，如果對遞歸還不熟悉，請參看舊文的詳細(xì)解說：淺析遞歸。

接下來講解一下合并兩個有序鏈表。其實第一次聽到這個問題，我有點誤解，所以我在解釋一下什么叫合并兩個有序鏈表。

比如兩個有序鏈表分別是：

4->6->9->11 和 1->3->6->8->12

我們需要得到這樣一個鏈表，并返回表頭節(jié)點：

1->3->4->6->6->8->9->11->12

這個過程有沒有很像拉拉鏈的過程？帶著這個直覺就很容易理解迭代解法。

迭代的實現(xiàn)方法很直接，但是需要點常用技巧，如果不想看了就直接看遞歸版本。

Node* merge(Node* head1, Node* head2) {
    // 如果有一個頭結(jié)點是空，就可以直接返回另一個
    if (head1 == NULL || head == NULL)
        return head1 == NULL ? head2 : head1;
    // 虛擬頭結(jié)點，方便處理 
    auto dummy = new Node(0); 
    // 我覺得這個指針很像拉鏈上的拉鎖
    Node *p = dummy;
    // 開始拽著 p 拉拉鏈
    while (head1 != NULL && head2 != NULL) {
        if (head1->val > head2->val) {
            p->next = head2;
            head2 = head2->next;
        } else {
            p->next = head1;
            head1 = head1->next;
        }
        p = p->next;
    }
    // 一個鏈表耗盡，剩下的元素都比已合并的鏈表元素大
    // 所以把剩下的直接連到最后就行了
    p->next = head1 == NULL ? head2 : head1;
    return dummy->next;
}

這里用到的常用技巧就是虛擬頭結(jié)點 dummy 的使用。處理鏈表的時候經(jīng)常會造一個虛擬頭結(jié)點連到一個真實頭結(jié)點的前面。

這樣做的好處很多，主要是是方便處理節(jié)點為空的特殊情況，減少大量復(fù)雜的判定代碼。請花時間理解這個算法（這是值得的），然后嘗試不要這個虛擬頭結(jié)點，然后就能理解這樣處理的好處了。

畫個圖理解一下：

現(xiàn)在開始遞歸版本。其實遞歸版本一直比迭代簡潔好理解，體驗一下：

Node* merge(Node* head1, Node* head2) {
    // 同理，只要有一個空就可以直接返回
    if (head1 == NULL || head2 == NULL)
        return head1 == NULL ? head2 : head1;
    if (head1->val > head2->val) {
        head2->next = merge(head1, head2->next);
        return head2;
    } else {
        head1->next = merge(head1->next, head2);
        return head1;
    }
}

遞歸解法總是這么精妙。總的邏輯就是：抽出當(dāng)前兩個節(jié)點中（head1 和 head2 中）較小的那個，然后把剩下的爛攤子一股腦丟給遞歸，因為剩下的問題和原問題具有相同結(jié)構(gòu)，且減小了規(guī)模。畫個圖理解下：

由于之前寫了好幾篇文章講解遞歸，這里就不贅述了，以上解法還可以再寫得漂亮些（本質(zhì)沒有變）：

Node* merge(Node* head1, Node* head2) {
    if (head1 == NULL || head2 == NULL)
        return head1 == NULL ? head2 : head1;
    // 保證 head1 總是值較小的，這樣就不用 if else 分支了
    if (head1->val > head2->val) swap(head1, head2);
    head1->next = merge(head1->next, head2);
    return head1;