C/C++練習題之合并k個已排序的鏈表
前言:
今天給大家分享一道面試中常見的題目——合并K個升序鏈表,我會用暴力和分治兩鐘方法去求解這道題目,通過動圖展示問題求解的全過程。這里提醒大家,畫圖是我們求解復雜問題的有效手段,有時可以起到事半功倍的效果,各位小伙伴在做題的過程中如果遇到麻煩,不妨動手畫畫圖喲。
題目描述:
合并K個升序的鏈表并將結果作為一個升序的鏈表返回其頭節(jié)點。例如:
- 輸入:[{1,2},{1,4,5},{6},{2,3,5}]
- 輸出:{1,1,2,2,3,4,5,5,6}
思路一:暴力求解法
首先根據(jù)題目的描述,畫出如下模擬圖。
第一步:確定合并后鏈表的頭節(jié)點rhead
從上圖中可以看出:lists
中存放是每個鏈表的頭節(jié)點,那合并后鏈表的頭節(jié)點一定是這四個頭結點中最小的那個,因此我們只需要遍歷lists
就可以找到最小的頭節(jié)點,然后把它賦值給rhead
,執(zhí)行完第一步得到的結果如下圖,用黃色標注已經(jīng)排好序的節(jié)點:
第二步:選擇次小的進行尾插
如上圖,接下來我們需要在所有藍色節(jié)點中選出最小的一個尾插到rhead
指向的鏈表,因此我們再定義一個rtail
指向合并后鏈表的最后一個節(jié)點。但是我們發(fā)現(xiàn)如果按照上圖的結構,直接從四個藍色節(jié)點里面選出最小的,顯然十分困難, 因為第一個鏈表中待比較的節(jié)點不再數(shù)組中。如果向第一步那樣,所有的節(jié)點都在數(shù)組中,那選出最小的節(jié)點簡直是易如反掌,只需要遍歷一遍數(shù)組即可。因為lists
數(shù)組中存的永遠都是頭節(jié)點,所以這里我們直接修改第一個鏈表的頭節(jié)點即可,通過lists[0] = lists[0]->next
就可以實現(xiàn)。修改后的結構如下圖所示:
此時所有待比較的節(jié)點都來到了數(shù)組中,和第一步的邏輯一樣,只需要遍歷一遍數(shù)組就可以找到最小的節(jié)點,找到后尾插到rhead
指向的鏈表。如下圖,其中黃色節(jié)點是已排好序的節(jié)點,藍色節(jié)點是待比較的節(jié)點。
總體邏輯就是這樣,接下來循環(huán)執(zhí)行第二步,找到次小的進行尾插,直到數(shù)組中的所有節(jié)點都為空,此時說明數(shù)組中的所有鏈表都已經(jīng)排好序了,返回rhead
即可??偟倪^程動圖如下:
??代碼實現(xiàn):
class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode* rhead = nullptr;//定義合并后鏈表的頭節(jié)點 ListNode* rtail = nullptr;//定義合并后鏈表的尾結點 while (true) { int minIndex = -1;//定義lists數(shù)組中最小節(jié)點下標,最初等于-1,(下簡稱最小位置) int i = lists.size();// while (i--) { if (lists[i] != nullptr)//首先判斷數(shù)組當前位置的節(jié)點是否為空 { //當前節(jié)點不為空再進來 if (minIndex == -1)//判斷最小位置是否是-1,如果是就直接把當前位置賦值給minIndex { minIndex = i; } else if (lists[i]->val < lists[minIndex]->val)//如果minIndex不為-1,則用數(shù)組當前位置節(jié)點的val與記錄的最小位置上節(jié)點的val進行比較 { minIndex = i;//如果當前節(jié)點的val值更小,那就更新minIndex } } } if (minIndex == -1)//遍歷完一遍數(shù)組如果minIndex的值還是-1,說明當前數(shù)組中的所有節(jié)點全是空 { return rhead;//此時說明所有鏈表已經(jīng)合并完成,可以返回頭節(jié)點 } if (rhead == nullptr)//確定新鏈表的頭節(jié)點 { rhead = rtail = lists[minIndex]; } else//之后每找出一個最小的節(jié)點,進行尾插即可 { rtail->next = lists[minIndex]; rtail = rtail->next; } lists[minIndex] = lists[minIndex]->next;//最小的節(jié)點已經(jīng)尾插到新鏈表,因此要對最小位置上的節(jié)點更新 } } };
上面代碼中需要注意的有:minIndex
是用來記錄lists
中最小節(jié)點的位置,它的初始值必須是-1
,不能是0
或其他數(shù)字,因為我們不知道0或其他位置上的節(jié)點是否為空。還有需要注意的地方是,每當遍歷到一個節(jié)點,首先要判斷是否為nullptr
,當不為空的時候再進行比較,避免出現(xiàn)空指針問題,其次要判斷minIndex
當前是否為-1
,如果是-1,就不用比較,直接把當前位置賦值給minIndex
即可,因為如果當minIndex == -1
的時候進行比較,會導致數(shù)組越界。
思路二:分治歸并法
分治即“分而治之”,“分”指的是將一個大而復雜的問題劃分成多個性質(zhì)相同但是規(guī)模更小的問題,子問題繼續(xù)按照這樣劃分,直到問題可以被輕易解決;“治”指的是將子問題單獨進行處理。經(jīng)過分治后的子問題,需要將解進行合并,也就是所謂的“歸并”,這樣才能得到原問題的解,因此整個分支過程經(jīng)常采用遞歸來實現(xiàn)。
針對這道題目來說,我們比較熟悉的是合并兩個有序鏈表,因此我們就可以把合并K個有序鏈表的問題,劃分成合并兩個有序鏈表的問題,具體過程我通過動圖來給大家演示,其中相同的顏色代表一個子問題
通過上面的動圖我們可以發(fā)現(xiàn),當子問題被分解到只剩一個鏈表的時候,就無法再進行分解,此時就需要返回了,其實這就是遞歸的終止條件,也就是當left == right
的時候就只剩一個鏈表,此時就應該返回了,返回的結果就是這一個鏈表。等左右區(qū)間各返回一個鏈表,此時就要開始對這兩個鏈表進行合并,從而得到一個新的有序鏈表,再把這個鏈表作為子問題的處理結果進行返回。這其實很像二叉樹的后序遍歷,如此循環(huán)往復,直到最終的大問題被解決。
??代碼實現(xiàn):
class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { return dividemerge(lists, 0, lists.size() - 1); } private: ListNode* dividemerge(vector<ListNode*>& lists, int left, int right) { if (left > right) { return nullptr; } else if (left == right) { return lists[left]; } int mid = left + (right - left) / 2; //分治 ListNode* head1 = dividemerge(lists, left, mid); ListNode* head2 = dividemerge(lists, mid + 1, right); //對子問題處理 return Merge(head1, head2); } private: ListNode* Merge(ListNode* pHead1, ListNode* pHead2)//合并兩個有序鏈表 { if (pHead1 == nullptr) { return pHead2; } if (pHead2 == nullptr) { return pHead1; } ListNode* pHeadret, * tail; if (pHead1->val < pHead2->val) { pHeadret = tail = pHead1; pHead1 = pHead1->next; } else { pHeadret = tail = pHead2; pHead2 = pHead2->next; } while (pHead1 != nullptr && pHead2 != nullptr) { if (pHead1->val < pHead2->val) { tail->next = pHead1; pHead1 = pHead1->next; } else { tail->next = pHead2; pHead2 = pHead2->next; } tail = tail->next; } if (pHead2 != nullptr) { tail->next = pHead2; } if (pHead1 != nullptr) { tail->next = pHead1; } return pHeadret; } };
分治的大思想,其實就體現(xiàn)在下面三行代碼中:
//分治 ListNode* head1 = dividemerge(lists, left, mid); ListNode* head2 = dividemerge(lists, mid + 1, right); //對子問題處理 return Merge(head1, head2);
我們只需要知道,前兩行代碼將一個大問題進行分解,得到的兩個子問題,并且經(jīng)過dividemerge
函數(shù)把這兩個子問題都處理好了,并且得到了兩個結果,針對本題,就是得到了兩個有序的鏈表,分別是head1
和head2
,然后我們只需要對這兩個鏈表進行合并就可以完成題目的要求,也就是第三行代碼實現(xiàn)的功能。這就是分治的思想
總結
到此這篇關于C/C++練習題之合并k個已排序的鏈表的文章就介紹到這了,更多相關C/C++合并k個已排序的鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
使用ShellClass獲取文件屬性詳細信息的實現(xiàn)方法
本篇文章是對ShellClass獲取文件屬性詳細信息的實現(xiàn)方法進行了詳細的分析介紹,需要的朋友參考下2013-05-05在C++中高效使用和處理Json格式數(shù)據(jù)的示例代碼
最近的項目在用c處理后臺的數(shù)據(jù)時,因為好多外部接口都在使用Json格式作為返回的數(shù)據(jù)結構和數(shù)據(jù)描述,如何在c中高效使用和處理Json格式的數(shù)據(jù)就成為了必須要解決的問題,需要的朋友可以參考下2023-11-11