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) {
- return merge(lists, 0, lists.size()-1);
- }
- ListNode* merge(vector<ListNode*>& lists, int i, int j) {
- if(i == j) return lists[i];
- if(i+1 == j)
- {
- return merge2(lists[i], lists[j]);
- }
- int m = (i+j)/2;
- ListNode* a = merge(lists, i, m);
- ListNode* b = merge(lists, m+1, j);
- }
- ListNode* merge2(ListNode* l1, ListNode* l2){
- ListNode* pre = NULL, *tmp, *head;
- while(l1 != NULL && l2 != NULL)
- {
- if(l1->val > l2->val)
- {
- if(pre != NULL)
- {
- tmp = l2;
- l2 = l2->next;
- tmp->next = l1;
- pre->next = tmp;
- }
- else
- {
- tmp = l2;
- l2 = l2->next;
- head = tmp;
- pre = tmp;
- pre->next = l1;
- }
- }
- else
- {
- if(head == NULL)
- {
- head = l1;
- }
- pre = l1;
- l1 = l1->next;
- }
- }
- if(l2 != NULL)
- {
- l1->next = l2;
- }
- return head;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement