C/C++練習題之合并k個已排序的鏈表

更新時間：2023年06月19日 10:46:00 作者：春人.

這篇文章主要給大家介紹了關于C/C++練習題之合并k個已排序的鏈表的相關資料,文中通過圖文以及實例代碼介紹的非常詳細,對大家學習或者使用C/C++具有一定的參考學習價值,需要的朋友可以參考下

前言：

今天給大家分享一道面試中常見的題目——合并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ù)組越界。

思路二：分治歸并法

分治即“分而治之”，“分”指的是將一個大而復雜的問題劃分成多個性質相同但是規(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)的功能。這就是分治的思想