leetcode--21 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

 

 


//合并两个有序链表
ListNode* mergeTwoLists(ListNode* headA, ListNode* headB)
{
    if (headA == nullptr&&headB == nullptr)
    {
        return nullptr;
    }

    if (headA == nullptr&&headB != nullptr)
    {
        return headB;
    }

    if (headA != nullptr&&headB == nullptr)
    {
        return headB;
    }

    ListNode* currentA = headA;
    ListNode* currentB = headB;
    ListNode* root = new ListNode('#');
    ListNode* p = root;
    while (currentA != nullptr)
    {
        if (currentA != nullptr && currentB != nullptr)
        {
            if (currentA->data > currentB->data)
            {
                p->next = currentB;
                currentB = currentB->next;
            }
            else
            {
                p->next = currentA;
                currentA = currentA->next;
            }
            p = p->next;
        }

        if (currentB == nullptr &&currentA != nullptr)
        {
            p->next = currentA;
            break;
        }

    }

    if (currentA == nullptr &&currentB!=nullptr)
    {
        p->next = currentB;
    }

 
    currentA = root->next;
    delete root;
    root = nullptr;
    return currentA;
}

//优化

ListNode* mergeTwoLists(ListNode* headA, ListNode* headB)
{
    if (headA == nullptr)
    {
        return headB;
    }

    if (headB == nullptr)
    {
        return headA;
    }

 

    ListNode* currentA = headA;
    ListNode* currentB = headB;
    ListNode* root = new ListNode('#');
    ListNode* p = root;
    while (currentA != nullptr)
    {
        if (currentA != nullptr && currentB != nullptr)
        {
            if (currentA->data > currentB->data)
            {
                p->next = currentB;
                currentB = currentB->next;
            }
            else
            {
                p->next = currentA;
                currentA = currentA->next;
            }
            p = p->next;
        }

        if (currentB == nullptr &&currentA != nullptr)
        {
            p->next = currentA;
            break;
        }

    }

    if (currentA == nullptr &&currentB!=nullptr)
    {
        p->next = currentB;
    }

 
    currentA = root->next;
    delete root;
    root = nullptr;
    return currentA;
}

;