【LeetCode】23.合并K个排序链表(Merge k So

简书内代码已上传GitHub：点击我 去GitHub查看代码
点击 这里 跳转到LeetCode官网查看题目
点击 这里 跳转到LeetCode中国官网查看题目

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

中文：

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

示例:

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

思路：

写这道题...写了3版才AC

第一版直接对K个链表循环，然后每次找出最小值插入新链表，这样做显然超时了。源代码已经...不见了，就不丢人现眼了。

第二版我想着直接套两个有序链表合并的模板算了，就依次1 和 2合并为newlist，然后newlist 和 3合并，如此下去直到K。这样写还是...一样的丑...但是简单。然后还是超时了。

超时代码：

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
    if(listsSize == 0)      return NULL;
    else if(listsSize == 1) return lists[0];
    /*
    struct ListNode** l = (struct ListNode**)malloc(sizeof(struct ListNode*) * listsSize);
    for(int i = 0 ; i < listsSize ; ++i){
        l[i] = lists[i];
    }
    */
    struct ListNode* newp;
    newp = merge2Lists(lists[1], lists[2]);
    
    for(int i = 2; i < listsSize ; ++i){
        newp = merge2Lists(newp, lists[i]);
    }
    
    
    return newp;
}

第三版，也就是正确的一种思路如下：

• 首先也是和第二版一样先把K个链表合并为一个链表，这里直接头尾相接就可以了。
• 然后对链表进行归并排序。归并排序就是切分后再合并的排序算法，先把链表不断地切分，直至不能切分（也可以选择步长），然后再合并，合并的同时进行排序。比如一段长为8的链表，就相当于把它分成了8个子链表，子链表两两合并，然后4个2长度的子链表再两两合并，最后两个长度为4的子链表合并。这样就得到了排完序的链表。简单的来说，就是把任务分割，子任务做完后再合并。

Accept by C:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* sortList(struct ListNode* head);
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
    //定义工作指针， 新链表的指针
    struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode)), * newp;
    //保存头节点
    newp = p;
    //置空
    p -> next = NULL;
    //合并K个链表
    for(int i = 0 ; i < listsSize ; ++i){
        p -> next = lists[i];
        while(p -> next != NULL){
            p = p -> next;
        }
    }
    //进行归并排序
    newp = sortList(newp -> next);
    return newp;
}

//归并排序
struct ListNode* sortList(struct ListNode* head) {
    struct ListNode* merge2Lists(struct ListNode*, struct ListNode*);
    //如果是空链表，或者单节点，直接返回
    if (head == NULL || head->next == NULL) return head;
    //定义工作指针p,以及两个定位的指针
    struct ListNode p, *all = &p, *half = &p;
    p.next = head;
    //all更新速率为half 2倍，借此定位half到链表中间节点
    while (all->next && all->next->next) {
        all = all->next->next;
        half = half->next;
    }
    //保存后半段链表
    struct ListNode* next = half->next;
    //截断
    half->next = NULL;
    //继续划分，直到不能再划分为止
    struct ListNode* partOne = sortList(head);
    struct ListNode* partTwo = sortList(next);
    //归并
    return merge2Lists(partOne, partTwo);
}

//将两非递减链表合并为一个非递减新链表
struct ListNode* merge2Lists(struct ListNode* l1, struct ListNode* l2){
    //定义一个新链表
    struct ListNode* l3 = (struct ListNode*)malloc(sizeof(struct ListNode)), *newp;
    l3 -> val = 0;
    newp = l3;
    l3 -> next = NULL;
    //l1 、 l2 均非空 ，需要进行比较
    while(l1 != NULL && l2 != NULL){
        if(l1 -> val <= l2 -> val){
            //l1 接入 newp 尾部，工作指针l3向前移动
            l3 = l3 -> next = l1;
            l1 = l1 -> next;
        }else{
            l3 = l3 -> next = l2;
            l2 = l2 -> next;
        }
    }
    l3 -> next = l1 ? l1 : l2;
    //返回不带头节点的新链表
    return newp -> next;
}

END