LeetCode 21 23：Merge Two Sorted Lists & Merge K Sorted Lists

LeetCode 21:

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

题目分析：对两个有序列表进行合并，这个是数据结构基本题目比较简单，代码如下（这个代码有点长，可以简化）：

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode* head =NULL, *tmp;
        while (l1 && l2)
        {
            if (l1->val <= l2->val)
            {
                if (!head)
                {
                    head = l1;
                    tmp = head;
                } else {
                    tmp ->next= l1;
                    tmp = tmp->next;
                }
                l1 = l1->next;
            } else {
                if (!head)
                {
                    head = l2;
                    tmp = head;
                }
                else
                {
                    tmp ->next = l2;
                    tmp = tmp->next;
                }
                l2 = l2->next;
            }
        }
        ListNode* tmp2 = l1 ? l1:l2;
        if(!head) {
            head = tmp2;
            tmp = head;
        } else {
            tmp->next = tmp2;
            tmp = tmp->next;
        }
        return head;
    }

LeetCode 23： Merge K Sorted Lists

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

本题在上一题的基础上再加深了一步，链表个数从两个改为K个。

此题有如下几种解法：

1、最简单的方法莫过于每次都从K个链表头中找到最小的那个元素，加入结果链表中。基于此，有人通过最小堆来简化最小元素的比较。

2、每次从数组中取两个链表，将合并结果加入到链表中，反复这个过程，直到数组中只剩一个链表为止。

3、将数组拆分成左、右两个子数组，递归的对左、右两个子数组进行合并，再将合并得到的两个链表合并在一起。

方法3比较简洁

复用上题两个链表的合并代码，方法3的实现代码如下：

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int length = lists.size();
        if (length == 0) {
            return NULL;
        } else if(length == 1)
            return lists[0];
        else if(length == 2) {
            return mergeTwoLists(lists[0], lists[1]);
        }
        vector<ListNode*> leftHalf(lists.begin(), lists.begin()+length/2);
        vector<ListNode*> rightHalf(lists.begin()+length/2, lists.end());
        return mergeTwoLists(mergeKLists(leftHalf), mergeKLists(rightHalf));
    }

LeetCode 21 23：Merge Two Sorted Lists & Merge K Sorted Lists

原文：http://blog.csdn.net/sunao2002002/article/details/46056015