这道题我是用递归做的,注定了只打败了一半的人- - 讲真,这道题和MergeSort根本没有任何差别啊
不过我的是尾递归,尾递归总是可以改成while循环的。改了的话应该会快很多吧。
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6
class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode * res = NULL; if(lists.size() == 0) return res; int len; len = lists.size() - 1; res = mergeLists(lists, 0, len); return res; } ListNode * mergeLists(vector<ListNode *> & lists, int begin, int end){ if(begin > end) return NULL; if(begin == end) return lists[begin]; ListNode *p1 = mergeLists(lists, begin, (begin + end)/2 ); //递归 ListNode *p2 = mergeLists(lists, (begin+ end)/2 + 1, end); //递归 return mergeTwoLists(p1,p2); } ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { //套用了上一题的答案 struct ListNode * res = NULL; struct ListNode * p1 = l1; //p1 p2用来跟踪l1,l2; p3永远指向新的链表的最后一个元素 struct ListNode * p2 = l2; struct ListNode * p3 = res; while(p1 != NULL && p2 != NULL){ int x ; if( p1->val < p2->val ){ x = p1->val; p1 = p1->next; } else{ x = p2->val; p2 = p2->next; } struct ListNode * temp = new ListNode(x); //新建一个节点 if(p3 == NULL){ //没有头节点就是很烦啊,各种NULL的判断 res = temp; p3 = res; } else{ p3->next = temp; p3 = p3->next; } } //一个结束了另一个还没有结束 if(p1 == NULL && p2 != NULL){ if(p3 == NULL) //一个都没加进去- - res = p2; else p3->next = p2; } else if(p1 != NULL && p2 == NULL){ if(p3 == NULL) //同样,一个都没加进去 res = p1; else p3->next = p1; } return res; } };