题目地址：https://leetcode.com/PRoblems/merge-k-sorted-lists/?tab=Description 题目描述：Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
我的代码：
/** * 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) { if(lists.size()==0) return NULL; while(lists.size()>1){ ListNode* a0=lists[0]; ListNode* a1=lists[1]; ListNode* a; if(a0==NULL||(a1!=NULL&&a0->val>a1->val)){ a=a0; a0=a1; a1=a; } a=a0; if(a0!=NULL) a0=a0->next; lists.push_back(a); while(a0!=NULL){ while(a1!=NULL&&a1->val<=a0->val){ a->next=a1; a=a->next; a1=a1->next; } a->next=a0; a=a->next; a0=a0->next; } if(a!=NULL) a->next=a1; lists[0]=NULL;lists[1]=NULL; lists.erase(lists.begin(),lists.begin()+2); } return lists[0]; }};解题思路： 对于k个链表，将其两两分组，每次对[k+1]/2组做两个链表的合并即可。 由于使用的是vector，所以这一步就想当于每次将前两个链表合并后放到末尾。直到仅剩1个链表。 因为链表是有序的，所以可直接顺序比较将两个链表合并。 由于存在空链表的情况，所以需小心判断。 设最后链表元素个数为n个，由于链表数没减少一半，就需遍历所有的元素一次，因此复杂度为O(nlogk)。
新闻热点
疑难解答
