题解 | #牛群的合并#

知识点：

链表/合并

分析：

先会两个有序链表的合并，然后再链表数组中，两两合并即可。

如图，然后依次比较cur1和cur2的值，小的就放到head的next，依次比较即可。

注意：

1. 链表不一样长可能，所以要处理这种情况。在每一次while的循环结束之后（两个链表合并结束后），判断一下cur1遍历完了没，或者cur2遍历完了没，谁完了，就让pre的next指向另一个。
2. 最后返回head即可。
3. 遍历链表数组，两两合并，最终即可。

编程语言：

C++

完整代码：

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr ||
                list2 == nullptr) return list1 == nullptr ? list2 : list1;
        ListNode* head = list1->val <= list2->val ? list1 : list2;
        ListNode* pre = head;
        ListNode* cur1 = head->next;
        ListNode* cur2 = head == list1 ? list2 : list1;
        while (cur1 && cur2) {
            if (cur1->val > cur2->val) {
                pre->next = cur2;
                cur2 = cur2->next;
            } else {
                pre->next = cur1;
                cur1 = cur1->next;
            }
            pre = pre->next;
        }
        pre->next = cur1 == nullptr ? cur2 : cur1;
        return head;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* head = nullptr;
        for (int i = 0; i < lists.size(); ++i)
            head = mergeTwoLists(head, lists[i]);
     
        return head;
    }