作者 Ivan Chien
始于 2019/08/31
分类：LeetCode
Tags: [ LeetCode ]
LeetCode 百题计划 - 23. Merge k Sorted Lists

LeetCode 23. Merge k Sorted Lists

23. Merge k Sorted Lists

Difficulty: hard

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

Example:

Input: [
1->4->5,
1->3->4,
2->6
]

Output: 1->1->2->3->4->4->5->6

哟~嚯, 又是一题hard. 大致思路是, 两两合并.

Only Version:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge2list(ListNode* lhs, ListNode* rhs) {
        ListNode* head, * itr;
        head = itr = NULL;
        while (lhs != NULL && rhs != NULL) {
            ListNode*& next = lhs->val < rhs->val ? lhs : rhs;
            if (itr == NULL) {
                itr = head = next;
            } else {
                itr = itr->next = next;
            }
            next = next->next;
        }
        if (itr != NULL)
            itr->next = lhs != NULL ? lhs : rhs;
        else 
            itr = head = lhs != NULL ? lhs : rhs;
        return head;
    }
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty())
            return NULL;
        deque<ListNode*> ideque (lists.begin(), lists.end());
        while (ideque.size() != 1) {
            ListNode* a = ideque.front();
            ideque.pop_front();
            ListNode* b = ideque.front();
            ideque.pop_front();
            ideque.push_back(this->merge2list(a, b));
        }
        return ideque.back();
    }
};

Rate:
Runtime: 24 ms, faster than 90.78% of C++ online submissions for Merge k Sorted Lists.
Memory Usage: 11.2 MB, less than 64.28% of C++ online submissions for Merge k Sorted Lists.

讨论区可能还有一些什么骚操作, 暂且不看了.(期待二刷)

⇦ ⇨