Leetcode 23. Merge k Sorted Lists | | Leetcode 23. Merge k Sorted Lists 文章作者:Tyan博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Version 1 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849/** * 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 size = lists.size(); if(size == 0) { return NULL; } ListNode* result = lists[0]; for(int i = 1; i < size; i++) { result = mergeTwoLists(result, lists[i]); } return result; } private: ListNode* mergeTwoLists(ListNode* first, ListNode* second) { ListNode* ptrFirst = first; ListNode* ptrSecond = second; ListNode* head = new ListNode(0); ListNode* current = head; while(ptrFirst && ptrSecond) { if(ptrFirst->val > ptrSecond->val) { current->next = ptrSecond; ptrSecond = ptrSecond->next; } else { current->next = ptrFirst; ptrFirst = ptrFirst->next; } current = current->next; } if(ptrFirst) { current->next = ptrFirst; } if(ptrSecond) { current->next = ptrSecond; } return head->next; } }; Version 2 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354/** * 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 size = lists.size(); if(size == 0) { return NULL; } ListNode* result = NULL; while(lists.size() != 1) { ListNode * l1 = lists.back(); lists.pop_back(); ListNode * l2 = lists.back(); lists.pop_back(); result = mergeTwoLists(l1, l2); lists.insert(lists.begin(), result); } return lists[0]; } private: ListNode* mergeTwoLists(ListNode* first, ListNode* second) { ListNode* ptrFirst = first; ListNode* ptrSecond = second; ListNode* head = new ListNode(0); ListNode* current = head; while(ptrFirst && ptrSecond) { if(ptrFirst->val > ptrSecond->val) { current->next = ptrSecond; ptrSecond = ptrSecond->next; } else { current->next = ptrFirst; ptrFirst = ptrFirst->next; } current = current->next; } if(ptrFirst) { current->next = ptrFirst; } if(ptrSecond) { current->next = ptrSecond; } return head->next; } }; Reference https://leetcode.com/problems/merge-k-sorted-lists/description/ 如果有收获,可以请我喝杯咖啡! 赏 微信打赏 支付宝打赏