[leetcode] 23. Merge k Sorted Lists

[leetcode] 23. Merge k Sorted Lists

Description

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

分析一

题目的意思是：k个有序链表合并。

归并排序，分治法，把多路归并转换为二路归并。

代码一

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* mergeKLists(vector& lists) { if(lists.size()==0){ return NULL; } int n=lists.size(); while(n>1){ int k=(n+1)/2; for(int i=0;ivalval){ cur->next=l1; l1=l1->next; }else{ cur->next=l2; l2=l2->next; } cur=cur->next; } if(l1){ cur->next=l1; } if(l2){ cur->next=l2; } return dump->next; }};

分析二

最小堆,用优先级队列来进行模拟,自定义里面的compare函数，即自定义升序。

代码二

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */struct cmp { bool operator () (ListNode *a, ListNode *b) { return a->val > b->val; }};class Solution {public: ListNode *mergeKLists(vector &lists) { priority_queue,cmp> q; for(int i=0;inext=temp; } pre=temp; if(temp->next){ q.push(temp->next); } } return head; }};

参考文献

​​[LeetCode] Merge k Sorted Lists 合并k个有序链表​​​​23. Merge k Sorted Lists​​​​priority_queue的用法​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。