PS：由于微信的更新將所有文章字體縮小了，所以本文是按照新版微信的字體大小進(jìn)行的排版，盡量讓所有代碼塊、解釋、圖片同時(shí)容納在屏幕內(nèi)，方便閱讀。
鏈表是一種很簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)，但是在面試題中常常出現(xiàn)。鏈表的每個(gè)節(jié)點(diǎn)包含一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針，跟串糖葫蘆似得穿起來。
struct Node {
int val;
Node* next;
}
鏈表結(jié)構(gòu)簡(jiǎn)單，但是卻很漂亮，因?yàn)樗哂刑焐倪f歸結(jié)構(gòu)，所以幾乎所有鏈表的操作都有一個(gè)遞歸的實(shí)現(xiàn)方式，這也是本篇文章的主要目的：教大家遞歸地處理鏈表。
這篇文章主要寫兩個(gè)鏈表最?？疾斓膬蓚€(gè)操作，包括鏈表翻轉(zhuǎn)和兩個(gè)有序鏈表的合并，并且給出迭代和遞歸兩種解法。
首先來簡(jiǎn)單熱下身，給一個(gè)鏈表頭，求這個(gè)鏈表的長(zhǎng)度。
迭代版本：
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)一個(gè)鏈表。解釋一下：
比如有個(gè)鏈表是 1->2->3->4，你要把它變成 4->3->2->1，返回頭結(jié)點(diǎn)（這里就是 4 那個(gè)節(jié)點(diǎn)）。
首先，看一下迭代算法：
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;
}
畫個(gè)中間過程的圖就好理解了，注意 prev 指向的節(jié)點(diǎn)和 curr 是不相連的，因?yàn)樗鼈冊(cè)谒惴ㄩ_始的時(shí)候就不相連。prev 走過之后的鏈表已經(jīng)翻轉(zhuǎn)完成了：
這三個(gè)指針的操作過程莫名讓我想起科普片里細(xì)胞中的酶組裝氨基酸的過程。。。
下面上遞歸算法，很漂亮，但絕對(duì)得不好理解（很適合拿去裝逼）：
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;
}
這個(gè)算法很精妙，我畫個(gè)圖就容易理解了（明白遞歸函數(shù)是干什么的，并相信它一定能做好）：
理解之后就一目了然了，如果對(duì)遞歸還不熟悉，請(qǐng)參看舊文的詳細(xì)解說：淺析遞歸。
接下來講解一下合并兩個(gè)有序鏈表。其實(shí)第一次聽到這個(gè)問題，我有點(diǎn)誤解，所以我在解釋一下什么叫合并兩個(gè)有序鏈表。
比如兩個(gè)有序鏈表分別是：
4->6->9->11 和 1->3->6->8->12
我們需要得到這樣一個(gè)鏈表，并返回表頭節(jié)點(diǎn)：
1->3->4->6->6->8->9->11->12
這個(gè)過程有沒有很像拉拉鏈的過程？帶著這個(gè)直覺就很容易理解迭代解法。
迭代的實(shí)現(xiàn)方法很直接，但是需要點(diǎn)常用技巧，如果不想看了就直接看遞歸版本。
Node* merge(Node* head1, Node* head2) {
// 如果有一個(gè)頭結(jié)點(diǎn)是空，就可以直接返回另一個(gè)
if (head1 == NULL || head == NULL)
return head1 == NULL ? head2 : head1;
// 虛擬頭結(jié)點(diǎn)，方便處理
auto dummy = new Node(0);
// 我覺得這個(gè)指針很像拉鏈上的拉鎖
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;
}
// 一個(gè)鏈表耗盡，剩下的元素都比已合并的鏈表元素大
// 所以把剩下的直接連到最后就行了
p->next = head1 == NULL ? head2 : head1;
return dummy->next;
}
這里用到的常用技巧就是虛擬頭結(jié)點(diǎn) dummy 的使用。處理鏈表的時(shí)候經(jīng)常會(huì)造一個(gè)虛擬頭結(jié)點(diǎn)連到一個(gè)真實(shí)頭結(jié)點(diǎn)的前面。
這樣做的好處很多，主要是是方便處理節(jié)點(diǎn)為空的特殊情況，減少大量復(fù)雜的判定代碼。請(qǐng)花時(shí)間理解這個(gè)算法（這是值得的），然后嘗試不要這個(gè)虛擬頭結(jié)點(diǎn)，然后就能理解這樣處理的好處了。
畫個(gè)圖理解一下：
現(xiàn)在開始遞歸版本。其實(shí)遞歸版本一直比迭代簡(jiǎn)潔好理解，體驗(yàn)一下：
Node* merge(Node* head1, Node* head2) {
// 同理，只要有一個(gè)空就可以直接返回
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)前兩個(gè)節(jié)點(diǎn)中（head1 和 head2 中）較小的那個(gè)，然后把剩下的爛攤子一股腦丟給遞歸，因?yàn)槭Ｏ碌膯栴}和原問題具有相同結(jié)構(gòu)，且減小了規(guī)模。畫個(gè)圖理解下：
由于之前寫了好幾篇文章講解遞歸，這里就不贅述了，以上解法還可以再寫得漂亮些（本質(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;聯(lián)系客服
