• Leetcode 23. Merge k Sorted Lists
  • 題目
  • 題目解析
  • 代碼
  • 連結清單類題目總結

Leetcode 23. Merge k Sorted Lists

題目

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  ->->,
  ->->,
  ->
]
Output: ->->->->->->->
           

題目解析

題目的意思很簡單，合并多個排序的連結清單，看起來和歸并排序非常相似，可以說基本相同的。按照正常的思路，設立一個連結清單頭，然後依次比較這

k

個連結清單中較小的一個，挂在這個連結清單頭上。很快就寫出代碼，但果然，肯定是逾時的，

hard

的應該沒這麼簡單==

分析一下，時間主要花在每次擴充時對這些連結清單頭進行周遊，如果加快搜尋呢，當然是進行排序。我們需要維護的是一個已經排序的結構，每次能夠迅速找到最小值，可以選擇的是排序的二叉樹，堆等。考慮到STL中實作的

set

，

map

這些都是排序的結構，是以直接應用即可。

接下來就是程式設計的問題了，我們需要的是把節點放入到

set

中，但如何重定義他的比較函數呢，因為重載運算符必須是對象，不能直接對指針重載運算符，是以我們用一個

pair

結構，結構的第一個元素是連結清單節點，第二個參數是連結清單的值，然後重載運算符就可以了。由于可能會有重複值，是以需要用有重複值的

set

代碼

經過上面的分析，代碼如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
// 定義結構并重載運算符
using PointX = pair<ListNode *, int>;
bool operator<(const PointX &a, const PointX &b)
{
    return a.second < b.second;
}

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        multiset<PointX, less<PointX>> mpset;
        for (auto i : lists)
            if(i)   // 對應于[[]]的測試用力
                mpset.insert(make_pair(i,i->val));
        ListNode * tmp = nullptr;
        ListNode * head = nullptr;
        while (!mpset.empty())
        {
            auto it = mpset.begin();
            if (tmp == nullptr) // 确定表頭，head記錄表頭
            {
                tmp = it->first;
                head = tmp;
            }
            else
            {
                tmp->next = it->first;
                tmp = tmp->next;
            }
            auto ptr = it->first;
            mpset.erase(it);    // 删除節點，注意是删除疊代器，不然重複值可能會全部删除了
            if (ptr->next)
            {
                mpset.insert(make_pair(ptr->next, ptr->next->val));
            }
        }
        if(tmp)     // 特殊情況判斷
            tmp->next = nullptr;
        return head;
    }
};
           

連結清單類題目總結

最近準備秋招，做了一些連結清單類的題目，總體感覺連結清單類題目容易出錯，需要考慮一些特殊的情況，總結如下：

1. 獲得

->next

和

->val

前，需要判斷節點是否為空

2. 可以增加一個頭節點，減少頭節點是否為空的判斷，傳回的時候傳回

nhead->next

就可以

3. 判斷題目需求連結清單分成幾段，記錄每一段的開頭和結尾，先在紙上畫出圖，确定要使用幾個指針來記錄

4. 判斷輸入節點是否為空

5. 注意尾巴指針置空，否則會無限循環