题目

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

思路

K 路归并链表；

注意：不能用 ListNode *cur 来记录当前的链表节点（因为这样的话无法修改数组中的链表），而是要直接在数组中修改链表，所以要用 index 记录要修改的链表。

假设所有的节点总数是 Sum， 共有 Num 个链表， 时间复杂度是：O(Num*Sum).

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int num = lists.size();
        if(num==0)  return NULL;
        if(num==1)  return lists[0];
        ListNode *head = NULL;
        ListNode *tail = NULL;
        int index = -1;
        while(true) {
            int min = INT_MAX;
            index = -1;
            for(int i=0;i<num;i++) {
                if(lists[i]) { 
                    if(lists[i]->val<min) {
                        min = lists[i]->val;
                        index = i;
                    }
                }
            }
            // There is no extra node to sort
            if(index<0) 
                break;
            if(head==NULL)
                head = lists[index];
            else
                tail->next = lists[index];
            tail = lists[index];
            lists[index] = lists[index]->next;                        
        }
        return head;
    }
};