??題目分析

將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

??解題思路

??思路1: 歸并排序思想（不使用帶哨兵衛(wèi)的頭節(jié)點(diǎn)）

取小的進(jìn)行尾插

??圖解??

??接口源碼：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	//考慮list1和list2其中一個(gè)為空的情況
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }

    struct ListNode* head = NULL, * tail = NULL;
    
    //當(dāng)list1和list2任意一個(gè)為空循環(huán)就結(jié)束
    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            if (tail == NULL)
            {
                head = tail = list1;
            }
            else
            {
                tail->next = list1;
                tail = tail->next;
            }

            list1 = list1->next;
        }
        else
        {
            if (tail == NULL)
            {
                head = tail = list2;
            }
            else
            {
                tail->next = list2;
                tail = tail->next;
            }

            list2 = list2->next;
        }
        
		//如果list1沒空則把list1后面剩下的數(shù)據(jù)直接鏈接到tail->next的后面
        if (list1)
        {
            tail->next = list1;
        }
        //如果list2沒空則把list2后面剩下的數(shù)據(jù)直接鏈接到tail->next的后面
        if (list2)
        {
            tail->next = list2;
        }
    }

    return head;
}

??解題思路

??思路2: 歸并排序思想（使用帶哨兵衛(wèi)的頭節(jié)點(diǎn)）

取小的進(jìn)行尾插

??圖解??

??接口源碼：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	//考慮list1和list2其中一個(gè)為空的情況
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }

    struct ListNode* head = NULL, * tail = NULL;
    //帶哨兵衛(wèi)的頭節(jié)點(diǎn),這個(gè)頭節(jié)點(diǎn)不存儲有效數(shù)據(jù)
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
	
	//當(dāng)list1和list2任意一個(gè)為空循環(huán)就結(jié)束
    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            tail->next = list1;
            tail = tail->next;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            tail = tail->next;
            list2 = list2->next;
        }
    }
	
	//如果list1沒空則把list1后面剩下的數(shù)據(jù)直接鏈接到tail->next的后面
    if (list1)
    {
        tail->next = list1;
    }
    //如果list2沒空則把list2后面剩下的數(shù)據(jù)直接鏈接到tail->next的后面
    if (list2)
    {
        tail->next = list2;
    }
	
	//在前面malloc的空間需要釋放，釋放前先保存head->next的地址
    struct ListNode* del = head;
    head = head->next;
    free(del);

    return head;
}

??希望烙鐵們能夠理解歐！

總結(jié)??
以上就是本題講解的全部內(nèi)容啦????????
本文章所在【C/C++刷題系列】專欄，感興趣的烙鐵可以訂閱本專欄哦??????
前途很遠(yuǎn)，也很暗，但是不要怕，不怕的人面前才有路。??????
小的會繼續(xù)學(xué)習(xí)，繼續(xù)努力帶來更好的作品??????
創(chuàng)作寫文不易，還多請各位大佬uu們多多支持哦??????
文章來源地址http://www.zghlxwxcb.cn/news/detail-645511.html

到了這里，關(guān)于LeetCode 21.合并兩個(gè)有序鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！