题解 | #划分链表#
合并k个已排序的链表
http://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
我思考了一下才解决的，非常的直接，直觉，我的思路是这样的。
1.设计一个头部指针来指向这个新的链表，设计一个当前指针来指向新链表最后一个位置。
2.设计一个字段来表示所有的链表都是否合并完成了。
3.从所有链表中找到最小元素所在的链表。主要是找到这个索引，然后把元素取出，拼接到新链表最后的位置。
4.返回新链表的头部指针指向的下一个元素。
/**
* 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) {
ListNode *head = new ListNode(0);
ListNode *cur = head;
bool hasNumber = true;
while(hasNumber){
int index = 0;
int val = INT32_MAX;
hasNumber = false;
for(int i=0;i<lists.size();i++){
if(lists[i] != NULL){
hasNumber = true;
if(lists[i]->val < val){
index = i;
val = lists[i]->val;
}
}
}
if(!hasNumber){
break;
}
ListNode *p = lists[index];
lists[index] = p->next;
p->next = NULL;
cur->next = p;
cur = p;
}
return head->next;
}
};
投递OPPO等公司6个岗位 >
