首页 > 代码库 > Merge k Sorted Lists
Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
思路：不断将相邻的链表两两合并，知道只剩一个链表为止。
1 class Solution { 2 public: 3 ListNode *mergeKLists( vector<ListNode *> &lists ) { 4 if( lists.empty() ) { return 0; } 5 int size = lists.size(); 6 while( size > 1 ) { 7 vector<ListNode*> newLists; 8 for( int i = 0; i < size-1; i += 2 ) { 9 newLists.push_back( merge( lists[i], lists[i+1] ) );10 }11 if( size % 2 == 1 ) { newLists.push_back( lists[size-1] ); }12 lists = newLists;13 size = lists.size();14 }15 return lists.front();16 }17 private:18 ListNode* merge( ListNode *node1, ListNode *node2 ) {19 if( !node1 ) { return node2; }20 if( !node2 ) { return node1; }21 ListNode *head = 0, **ppNode = &head;22 while( node1 && node2 ) {23 if( node1->val <= node2->val ) {24 *ppNode = node1;25 node1 = node1->next;26 } else {27 *ppNode = node2;28 node2 = node2->next;29 }30 ppNode = &((*ppNode)->next);31 }32 if( node1 ) {33 *ppNode = node1;34 } else {35 *ppNode = node2;36 }37 return head;38 }39 };
Merge k Sorted Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。