题解 | #牛群的合并#

考察的知识点：与链表有关的题基本都是插入，删除，交换顺序等，解决这些问题通常将链表的指针进行修改。

问题分析：这道题是合并多个有序链表，是在合并两个有序链表的基础上进行循环，用一个变量 head 指向合并的链表，第 i 次循环把第 i 个链表和 head 合并，答案保存到 head 中。

本题解析所用的编程语言：c++

对mergeTwoLists()函数修改一下，单链表中通常构造(new)头结点后，其中c++需要删除(delete)，但如果实例化一个对象，这个对象出作用域就会自动销毁，修改后比较简洁些。

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
    ListNode head(-1);
    ListNode* cur = &head;
    while (l1 && l2)
    {
        if (l1->val < l2->val)
        {
            cur->next = l1;
            l1 = l1->next;
        }
	    else
	    {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    //至少有一个链表为空，cur->next连接不为空的链表
    cur->next = l1 ? l1 : l2;

    return head.next;
}

原代码(现在看以前写的感觉有些挫)：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
    if (!l1 || !l2)
        return l1 ? l1 : l2;
    ListNode* head = new ListNode(-1);
    ListNode* cur = head, * p1 = l1, * p2 = l2; //原错误* p2 = l1
    while (p1 && p2)  //原错误 l1 && l2
    {
        if (p1->val < p2->val)
        {
            cur->next = p1;
            p1 = p1->next;
        }
        else
        {
            cur->next = p2;
            p2 = p2->next;
        }
        cur = cur->next;
    }
    //至少有一个链表为空，cur->next连接不为空的链表
    cur->next = (p1 ? p1 : p2);

    cur = head->next;
    delete head;
    return cur;
}
ListNode* mergeKLists(vector<ListNode*>& lists)
{
    // write code here
    ListNode* head = nullptr;
    for (int i = 0; i < lists.size(); ++i)
        head = mergeTwoLists(head, lists[i]);
    
    return head;
}