Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * 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 nullptr;
- size_t delta = 1;
- while (delta < lists.size())
- {
- for (int i=0; i<lists.size()-delta; i=i+2*delta)
- lists[i] = mergeTwoLists(lists[i], lists[i+delta]);
- delta *= 2;
- }
- return lists[0];
- }
- ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
- {
- if (l1 == NULL) return l2;
- if (l2 == NULL) return l1;
- auto v1 = l1->val;
- auto v2 = l2->val;
- auto root = v1 <= v2 ? l1 : l2;
- v1 <= v2 ? (l1 = l1->next) : (l2 = l2->next);
- auto cur = root;
- while (l1 != NULL && l2 != NULL)
- {
- if (l1->val <= l2->val)
- {
- cur->next = l1;
- l1 = l1->next;
- }
- else
- {
- cur->next = l2;
- l2 = l2->next;
- }
- cur = cur->next;
- }
- cur->next = l1 != NULL ? l1 : l2;
- return root;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement