|
PS：由于微信的更新將所有文章字體縮小了，所以本文是按照新版微信的字體大小進行的排版，盡量讓所有代碼塊、解釋、圖片同時容納在屏幕內(nèi)，方便閱讀。 鏈表是一種很簡單數(shù)據(jù)結構，但是在面試題中常常出現(xiàn)。鏈表的每個節(jié)點包含一個指向下一個節(jié)點的指針，跟串糖葫蘆似得穿起來。 struct Node {
int val;
Node* next;
}
鏈表結構簡單，但是卻很漂亮，因為它具有天生的遞歸結構，所以幾乎所有鏈表的操作都有一個遞歸的實現(xià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)在開始正題，先來講解一下翻轉一個鏈表。解釋一下： 比如有個鏈表是 1->2->3->4，你要把它變成 4->3->2->1，返回頭結點（這里就是 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)翻轉完成了：
這三個指針的操作過程莫名讓我想起科普片里細胞中的酶組裝氨基酸的過程。。。 下面上遞歸算法，很漂亮，但絕對得不好理解（很適合拿去裝逼）： 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ù)是干什么的，并相信它一定能做好）： 
理解之后就一目了然了，如果對遞歸還不熟悉，請參看舊文的詳細解說：淺析遞歸。
接下來講解一下合并兩個有序鏈表。其實第一次聽到這個問題，我有點誤解，所以我在解釋一下什么叫合并兩個有序鏈表。 比如兩個有序鏈表分別是： 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) {
// 如果有一個頭結點是空，就可以直接返回另一個
if (head1 == NULL || head == NULL)
return head1 == NULL ? head2 : head1;
// 虛擬頭結點，方便處理
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;
}
這里用到的常用技巧就是虛擬頭結點 dummy 的使用。處理鏈表的時候經(jīng)常會造一個虛擬頭結點連到一個真實頭結點的前面。
這樣做的好處很多，主要是是方便處理節(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;
}
}
遞歸解法總是這么精妙?？偟倪壿嬀褪牵撼槌霎斍皟蓚€節(jié)點中（head1 和 head2 中）較小的那個，然后把剩下的爛攤子一股腦丟給遞歸，因為剩下的問題和原問題具有相同結構，且減小了規(guī)模。畫個圖理解下： 
由于之前寫了好幾篇文章講解遞歸，這里就不贅述了，以上解法還可以再寫得漂亮些（本質沒有變）： 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;
|
