LeetCode题目:Merge k Sorted Lists

By | 2012 年 10 月 5 日

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



分析
设总长度为n。
最简单的办法就是扫一遍k个链表的开头,哪个最小就把它移除,加入到结果链表中。这样时间复杂度是kn
第二个办法就是进行二分,将k个链表分为两个一组,组内进行merge。形成一个新的链表集合,大小为(k + 1)/2。继续两个一组merge,这样下去一共会进行logk次merge,最后merge成为一个链表。总的时间复杂度是n
logk

其中两个list合并的代码同LeetCode题目:Merge Two Sorted Lists



代码:72ms过大集合

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *proot = NULL;
        ListNode **pplast = &proot;
        while(l1 || l2){
            if(l1) {
                ListNode *minNode;
                if(!l2 || l1->val <= l2->val){
                    //l1 is min
                    minNode = l1;
                    l1 = l1->next;
                } else if(l2) {
                    //l2 is min
                    minNode = l2;
                    l2 = l2->next;
                }
                //proceed root
                *pplast = minNode;
                pplast = &(minNode->next);
            } else {
                //l1 is empty
                *pplast = l2;
                break;
            }
        }
        return proot;
    }
    ListNode *mergeKLists(vector &lists) {
        if(lists.size() == 0)
            return NULL;
        int curSize = lists.size();
        while(curSize > 1) {
            int halfSize = (1 + curSize) / 2;
            //merge i,i + halfSize
            for(int i = 0 ; i < halfSize && i + halfSize < curSize; ++i) {
                ListNode *first = lists[i];
                ListNode *second = lists[i + halfSize];
                ListNode *result = mergeTwoLists(first,second);
                lists[i] = result;
            }
            //set curSize to halfsize
            curSize = halfSize;
        }
        return lists[0];
    }
};

7 thoughts on “LeetCode题目:Merge k Sorted Lists

  1. kakuka

    假如用n来表示单个数组长度:
    第一种情况下是O(k*(k*n)) ,因为一共要添加k*n个节点,而添加每个需要的是k次比较;
    第二种情况下是O(k*n);
    差不多是这样的吧。

    Reply
  2. pf

    分组merge的复杂度并不是n*logk
    因为随着每次merge数组长度增加 复杂度不再是O(2n)了
    而是O(4n), O(8n), … 一共大概有logk项的等比数列
    最后结果应该还是O(n*k)

    Reply
    1. uniEagle Post author

      针对第一种方法,我假设总长度是n,那么对于每个加到结果链表中的节点,需要扫一遍k个list找到前端最小的那一个节点(这次扫描是O(k)),那么n个节点总共需要O(n*k)的。

      Reply

pf进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注