合并两个链表—>合并k个链表

将问题“合并 k 个链表”转化为“ k 次合并两个链表”

维护一个链表 ans，初始为 nullptr。遍历 lists 中的每个 list，每次调用 mergerTwoLists 函数将 ans 和 list 合并，并更新 ans，最后返回的 ans 就是合并后的链表。

/**
 * 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) {
        int n = lists.size();
        ListNode *ans = nullptr;
        for (auto list : lists) {
            ans = mergeTwoLists(ans, list);
        }
        return ans;
    }

    ListNode *mergeTwoLists(ListNode *head1, ListNode *head2) {
        if (!head1) {
            return head2;
        } else if (!head2) {
            return head1;
        }
        ListNode *dummy = new ListNode(-1);
        ListNode *cur = dummy;
        while (head1 && head2) {
            if (head1->val < head2->val) {
                cur->next = head1;
                head1 = head1->next;
            } else {
                cur->next = head2;
                head2 = head2->next;
            }
            cur = cur->next;
        }
        if (head1) {
            cur->next = head1;
        } else if (head2) {
            cur->next = head2;
        }
        return dummy->next;
    }
};