题解 | #合并k个已排序的链表#刚吃了一个墨西哥卷，又是好汉一条

/**
 * 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) {
        ListNode *ret = nullptr;
        for (auto n : lists) {
            ret = mergeTwo(ret, n);
        }
        return ret;
        
    }
    ListNode *mergeTwo(ListNode *list1, ListNode *list2) {
        if (!list1) {
            return list2;
        }
        if (!list2) {
            return list1;
        }
        ListNode *head = new ListNode(0);
        ListNode *ret = head;
        while(list1 && list2) {
            if (list1->val < list2->val) {
                head->next = new ListNode(list1->val);
                list1 = list1->next;
            } else {
                head->next = new ListNode(list2->val);
                list2 = list2->next;
            }
            head = head->next;
        }
        if (list1) {
            head->next = list1;
        }
        if (list2) {
            head->next = list2;
        }
         
        return ret->next;
    }
};