合并K个排序链表

题目描述

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

示例:

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

题解

利用归并排序的思想，进行分治。

/**
 * 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) {
        //处理为空的时候
        if(lists.size()==0)
            return NULL;
        return merge2List(lists,0,lists.size()-1);
    }

    //类似归并排序
    ListNode* merge2List(vector<ListNode*>& lists, int start, int end)
    {
        if(start==end)
            return lists[start];
        //合并前半段链表集合
        ListNode *l1 = merge2List(lists, start, (start+end)/2);
        //合并后半段链表集合
        ListNode *l2 = merge2List(lists, (start+end)/2+1, end);
        //然后再将这两个链表合并
        return merge(l1,l2);
    }

    //合并两个链表
    ListNode* merge(ListNode* l1,ListNode* l2)
    {
        ListNode* head = new ListNode(0);
        ListNode* tmp = head;

        while(l1!=NULL && l2!=NULL)
        {
            if(l1->val<l2->val)
            {
                tmp->next = l1;
                l1 = l1->next;
            }
            else
            {
                tmp->next = l2;
                l2=l2->next;
            }
            tmp = tmp->next;
        }

        if(l1==NULL)
            tmp->next = l2;
        else
            tmp->next = l1;

        return head->next;
    }

};