dbhllnr 2020-04-26
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这题并不难,50%的通过率,在空输入的报错上花了很多时间
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { int i,minn,minpos; ListNode* s=(ListNode*)malloc(sizeof(ListNode)); ListNode* p=s; s->next=NULL;//这里对于处理空输入很关键 while(true){ minn=100000; minpos=-1; for(i=0;i<lists.size();i++){ if(lists[i]!=NULL&&lists[i]->val<minn){ minn=lists[i]->val; minpos=i; } } if(minpos==-1){ break; } p->next=lists[minpos]; lists[minpos]=lists[minpos]->next; p->next->next=NULL; p=p->next; } return s->next; } };