leetcode 合并数组

合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { { if(!l1 || !l2) { return l1 ? l1 : l2; } ListNode head(0); ListNode* tail = &head; ListNode* a = l1; ListNode* b = l2; while(a&&b) { if(a->val > b->val) { tail->next = b; tail = tail->next; b = b->next; } else { tail->next = a; tail = tail->next; a = a->next; } } tail->next = a ? a : b; return head.next; } 合并K个排序链表 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

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

方法一：分治合并

ListNode* mergeKLists(vector<ListNode*>& lists) { //分治合并 递归 ListNode* head = merge(lists, 0, lists.size()-1); return head; } ListNode* merge(vector<ListNode*>&lists, int l, int r) { if(l == r) { return lists[l]; } if(l > r) { return nullptr; } int mid = (l+r)>>1; return mergetwo(merge(lists, l, mid), merge(lists, mid+1, r)); } ListNode* mergetwo(ListNode* l, ListNode* r) { if(!l || !r) { return l ? l : r; } ListNode head(0); ListNode* tail = &head; ListNode* a = l; ListNode* b = r; while(a&&b) { if(a->val > b->val) { tail->next = b; tail = tail->next; b = b->next; } else { tail->next = a; tail = tail->next; a = a->next; } } tail->next = a ? a : b; return head.next; }

方法二：使用优先对列，每层的最小值，中找最小的取出。

// struct VecNode{ // int val; // ListNode * p; // bool operator < (const VecNode& rhs) const { // return val > rhs.val; //小根堆 // } // }; // ListNode* mergeKLists(vector<ListNode*>& lists) { // //使用优先队列来合并 // priority_queue<VecNode> que; // for(int i = 0; i < lists.size(); ++i) // { // if(lists[i]) // que.push({lists[i]->val, lists[i]}); // } // ListNode head(0); // ListNode * tail = &head; // while(!que.empty()) // { // // cout << "s"<<endl; // auto p = que.top(); // que.pop(); // tail->next = p.p; // tail = tail->next; // if(p.p->next) // { // que.push({p.p->next->val, p.p->next}); // } // } // return head.next; // }