• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest May 25th, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. public:
11.     ListNode* mergeKLists(vector<ListNode*>& lists)
12.     {
13.         if (lists.size()==0) return nullptr;
14.         size_t delta = 1;
15.         while (delta < lists.size())
16.         {
17.             for (int i=0; i<lists.size()-delta; i=i+2*delta)
18.                 lists[i] = mergeTwoLists(lists[i], lists[i+delta]);
19.             delta *= 2;
20.         }
21.
22.         return lists[0];
23.     }
24.
25.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
26.     {
27.         if (l1 == NULL) return l2;
28.         if (l2 == NULL) return l1;
29.
30.         auto v1 = l1->val;
31.         auto v2 = l2->val;
32.         auto root = v1 <= v2 ? l1 : l2;
33.         v1 <= v2 ? (l1 = l1->next) : (l2 = l2->next);
34.
35.         auto cur = root;
36.         while (l1 != NULL && l2 != NULL)
37.         {
38.             if (l1->val <= l2->val)
39.             {
40.                 cur->next = l1;
41.                 l1 = l1->next;
42.             }
43.             else
44.             {
45.                 cur->next = l2;
46.                 l2 = l2->next;
47.             }
48.             cur = cur->next;
49.         }
50.         cur->next = l1 != NULL ? l1 : l2;
51.
52.         return root;
53.     }
54. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top