首页 > 代码库 > [LeetCode] 23. Merge k Sorted Lists
[LeetCode] 23. Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 11 public:12 ListNode* mergeKLists(vector<ListNode*>& lists) {13 int k = lists.size();14 if (k == 0) return NULL;15 16 while (k > 1){17 for (int i = 0; i < k /2; i++){18 lists[i] = mergeTwoLists(lists[i], lists[k-1-i]);19 }20 if (k%2){21 k = k/2 + 1;22 }else{23 k = k / 2;24 }25 }26 27 return lists[0];28 }29 30 private:31 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {32 ListNode *dummy = new ListNode(0);33 ListNode *ret = NULL;34 35 36 ListNode *p1 = l1;37 ListNode *p2 = l2;38 39 ListNode *p = dummy;40 41 while(p1 && p2){42 if (p1->val < p2->val){43 p->next = p1;44 p1 = p1->next;45 }else{46 p->next = p2;47 p2 = p2->next;48 }49 p = p->next;50 }51 52 p1 = (!p1) ? p2 : p1;53 54 while (p1){55 p->next = p1;56 // don‘t forget to move p1 !!57 p1 = p1->next;58 p = p->next;59 }60 61 ret = dummy->next;62 delete dummy;63 return ret;64 }65 };
[LeetCode] 23. Merge k Sorted Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。