23. 合并K个排序链表

题目
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

思路
基本思路是：把k个链表开头的值排个序，每次取最小的一个值放到答案链表中，这次取完之后更新这个值为它后面的一个值。接着这么取一直到全部取完。那么每次更新之后怎么对当前这k个值重新排序以便知道当前最小的是谁呢？用优先队列（或者堆）来维护这k个值就好啦！

由于每个值都要取一次，一共取nk次。每次更新优先队列要logk的复杂度。所以总时间复杂度为O(nklogk)；空间复杂度为优先队列所占空间，为O(k)。

#include "ListNode.h"
#include <iostream>
#include <queue>
using namespace std;

class Solution {
public:
    struct cmp
    {
        bool operator() (const ListNode* a, const ListNode* b)
        {
            return a->val > b->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> que;
        for (auto eve : lists)
        {
            if (eve)
            {
                que.push(eve);
            }
        }
        if (que.empty())
        {
            return nullptr;
        }
        ListNode* result = que.top();
        que.pop();
        ListNode* tail = result;
        if (tail->next)
        {
            que.push(tail->next);
        }
        while (!que.empty())
        {
            tail->next = que.top();
            tail = tail->next;
            que.pop();
            if (tail->next)
            {
                que.push(tail->next);
            }
        }
        return result;
    }
};

int main(int argc, char* argv[])
{
    string test = "1,1,2,3,4,4,5,6";
    auto listNode = stringToListNode(test);
    
    return 0;
}

将string转成vector，然后将vector转成ListNode

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}

vector<int> stringToIntegerVector(string input) {
    vector<int> output;
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    //input = input.substr(1, input.length() - 2);
    stringstream ss;
    ss.str(input);
    string item;
    char delim = ',';
    while (getline(ss, item, delim)) {
        output.push_back(stoi(item));
    }
    return output;
}

ListNode* stringToListNode(string input) {
    // Generate list from the input
    vector<int> list = stringToIntegerVector(input);

    // Now convert that list into linked list
    ListNode* dummyRoot = new ListNode(0);
    ListNode* ptr = dummyRoot;
    for (int item : list) {
        ptr->next = new ListNode(item);
        ptr = ptr->next;
    }
    ptr = dummyRoot->next;
    delete dummyRoot;
    return ptr;
}