[LeetCode] Merge k Sorted Lists

 1 class Solution {
 2 public:
 3     ListNode* mergeKLists(vector<ListNode*>& lists) {
 4         if (lists.empty()) return NULL;
 5         int n = lists.size();
 6         while (n > 1) {
 7             for (int i = 0; i < n / 2; i++)
 8                 lists[i] = mergeLists(lists[i], lists[n - 1 - i]);
 9             n = (n + 1) / 2;
10         }
11         return lists[0];
12     }
13 private:
14     ListNode* mergeLists(ListNode* head1, ListNode* head2) {
15         ListNode* new_head = new ListNode(0);
16         ListNode* run = new_head;
17         ListNode* run1 = head1;
18         ListNode* run2 = head2;
19         while (run1 && run2) {
20             if (run1 -> val <= run2 -> val) {
21                 run -> next = run1;
22                 run1 = run1 -> next;
23             }
24             else {
25                 run -> next = run2;
26                 run2 = run2 -> next;
27             }
28             run = run -> next;
29         }
30         run -> next = run1 ? run1 : run2;
31         return new_head -> next;
32     }
33 };