07月17日, 2015 1,415 views次
链接:https://leetcode.com/problems/merge-k-sorted-lists/
题目:Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
题意:给定k个有序链表,合并成一个有序链表
分析:类似上个合并两个链表的题目,对于k个链表,可以二分合并
CPP代码:
//struct ListNode { // int val; // ListNode *next; // ListNode(int x) : val(x), next(NULL) {} //}; class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { if(lists.empty()) return NULL; while(lists.size() >= 2) { int sz = lists.size(); for(int i = 0, j; (j = sz - i - 1) > i; ++i) { lists[i] = mergeTwoLists(lists[i], lists[j]); lists.pop_back(); } } return lists[0]; } private: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode * head = new ListNode(0); ListNode * p = head; while(l1 != NULL || l2 != NULL) { if(l1 == NULL || (l2 != NULL && l2->val < l1->val)) { p->next = new ListNode(l2->val); l2 = l2->next; } else { p->next = new ListNode(l1->val); l1 = l1->next; } p = p->next; } return head->next; } };