这周课是讲分治法，那就来做一题分治类型的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

题目分析

一开始除了砍半想过其他的砍法(比如三分），但用Master Theorem思考了一下发现复杂度是一样的：
T(n) = 3T(n/3) + O(n)
T(n) = 2T(n/2) + O(n)
复杂度都是

错误分析

0

head 和 result

1

Input:
[[],[1]]
Output:
[]
Expected:
[1]

弱智错误

代码

#include <iostream>
#include <vector>

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

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0){
            return NULL;
        }
        else if(lists.size() == 1){
            return lists[0];
        }
        else if(lists.size() == 2){
            return mergeTwoLists(lists[0], lists[1]);
        }
        else if(lists.size() > 2){
            vector<ListNode*> temp1;
            int i;
            for(i = 0; i < lists.size()/2; ++i){
                temp1.push_back(lists[i]);
            }
            vector<ListNode*> temp2;
            for(i; i< lists.size(); ++i){
                temp2.push_back(lists[i]);
            }
            return mergeTwoLists(mergeKLists(temp1), mergeKLists(temp2));
        }

    }

    ListNode* mergeTwoLists(ListNode* a, ListNode* b){
        if(a == NULL)
            return a;
        else if(b == NULL)
            return b;
    
        ListNode *result;
        if(a->val < b->val){
            result = new ListNode(a->val);
            a = a->next;
        }
        else{
            result = new ListNode(b->val);
            b = b->next;
        }
        result->next = NULL;

        while(1){
            if(a == NULL){
                result->next = b;
                break;
            }
            else if(b == NULL){
                result->next = a;
                break;
            }
            else{
                if(a->val < b->val){
                    result->next = new ListNode(a->val);
                    result = result->next;
                    a = a->next;
                }
                else{
                    result->next = new ListNode(b->val);
                    result = result->next;
                    b = b->next;
                }
            }
        }
        return result;
    }
};

分析

https://leetcode.com/problems/merge-k-sorted-lists/solution/