23. Merge k Sorted Lists

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

给定k个排序了的链表，合并k个链表成一个排序链表。

本程序思路：

1）首先得到K个链表的长度和存在len中

2）从K个链表中找到值最小的那个节点，把该节点添加到合并链表中

3）重复len次即可把所有节点添加到合并链表中。

注意事项：

1）K个链表中有的链表全部添加完会变成空链表，应做相应的处理

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){    struct ListNode *list = NULL;    /*获取链表长度*/    int cnt = 0, len = 0;    for ( ; cnt < listsSize; cnt++ )    {        list = lists[cnt];        for ( ; list; list = list->next )        {            len += 1;        }    }        list = NULL;    struct ListNode **head = &list;    struct ListNode *node = NULL;    int key = 0;    for ( cnt = 0; cnt < len; cnt++ )    {        int index = 0;        int nullSizes = 0;                /*获取链表中空链表数量*/        for ( index = 0; index < listsSize; index++ )        {            if ( lists[index] == NULL )            {                nullSizes += 1;            }        }                /*删掉链表数组中空链表，组成新的链表数组*/        int nulls = 0;        int flag = 0;        for ( nulls = 0; nulls < nullSizes; nulls++ )        {            flag = 0;            for ( index = 0; index < listsSize; index++ )            {                if ( lists[index] == NULL )                {                    lists[index] = lists[index + 1];                    flag = 1;                }                else if ( flag == 1)                {                    lists[index] = lists[index + 1];                }            }        }        /*删掉空链表并及时修改现存链表数量*/        if ( flag == 1 )        {            listsSize -= nullSizes;        }                /*找到所有链表中值最小的节点*/        int min = INT_MAX;        for ( index = 0; index < listsSize; index++ )        {            if ( lists[index]->val < min )            {                min = lists[index]->val;                node = lists[index];                key = index;            }        }                /*把最小节点添加到合并链表中*/        (*head) = node;        node = node->next;        head = &(*head)->next;        /*最小值所在链表往后移*/        lists[key] = node;    }        return list;}