前言:?
? ? ? ? ??歡迎大家來到Dream_Chaser～的博客??
????????本文收錄于 C--數(shù)據(jù)結(jié)構(gòu)刷題的專欄中 -->http://t.csdn.cn/n6UEP
????????首先歡迎大家的來訪，其次如有錯誤，非常歡迎大家的指正！我會及時更正錯誤！
目錄
一.合并兩個有序鏈表
1.1核心邏輯????????
1.2兩元素相同時選誰尾插?
一.合并兩個有序鏈表
來源:21. 合并兩個有序鏈表 - 力扣（LeetCode）
題目:
解析:
????????函數(shù)的參數(shù)是兩個指向 ListNode 結(jié)構(gòu)體的指針, ListNode 是一個常見的鏈表節(jié)點結(jié)構(gòu)。ListNode 結(jié)構(gòu)一般包含兩個成員：一個是存儲節(jié)點值的變量（比如 val ），另一個是指向下一個節(jié)點的指針（比如 next ）。
????????
????????目的是把兩個已排序的鏈表（?list1?和?list2?）合并為一個新的已排序的鏈表，并返回這個新鏈表的頭節(jié)點。
1.1核心邏輯????????
以下是該函數(shù)的核心邏輯：
-
首先，如果 list1 或 list2 是空鏈表（即NULL），函數(shù)會直接返回另一個鏈表。這是因為合并一個空鏈表和一個非空鏈表的結(jié)果就是那個非空鏈表。
-
接著，它進(jìn)入了一個while循環(huán)。在這個循環(huán)中，只要list1 和list2都不為空，就會比較它們當(dāng)前節(jié)點的值。如果?list1?的當(dāng)前節(jié)點值小于?list2?的當(dāng)前節(jié)點值，就把list1 的當(dāng)前節(jié)點加入到新鏈表中(先讓tail -> next=?list1??,然后tail=tail->next?指向list1)，,然后?list1?把向后移動一位,。否則，就把list2的當(dāng)前節(jié)點加入到新鏈表中(先讓tail -> next=?list2??,然后tail=tail->next?指向list2)，然后把list2向后移動一位。這樣可以保證新鏈表的節(jié)點是按照升序排列的。
-
head和?tail 是兩個輔助指針，用來構(gòu)建新鏈表。head指向新鏈表的頭節(jié)點，tail指向新鏈表的尾節(jié)點。每次添加一個新節(jié)點時，都會更新tail指向新加入的節(jié)點。
-
當(dāng)list1或 list2?中有一個被完全遍歷（即變?yōu)镹ULL）后，while循環(huán)就會結(jié)束。此時，如果list1或list2中還有剩余的節(jié)點，就把這些節(jié)點全部加入到新鏈表的尾部。這是可以做的，因為這些剩余的節(jié)點已經(jīng)是按照升序排列的，而且它們的所有值都大于新鏈表中已有節(jié)點的值。
-
最后，函數(shù)返回新鏈表的頭節(jié)點 head
1.2兩元素相同時選誰尾插?
我解釋一下為什么當(dāng)list1指向的元素與list2指向的元素大小相等時，用list2尾插：
在兩個鏈表元素相等的情況下，默認(rèn)選擇lsit1作為較大的元素。
當(dāng)list1和list2指向的元素都是1時，來到了if else 語句，如果條件為真，進(jìn)入循環(huán)，則證明選擇list2作為較大元素,反之選擇list1為較大元素
?結(jié)果程序來到了else處，此刻list2小于list1，選擇list2尾插,說明list1比list2大
?動圖解析:(點進(jìn)去放大看更清晰)
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if(list1==NULL)
return list2;//若第一個鏈表為 NULL，直接返回第二個鏈表
if(list2 ==NULL)
return list1;//若第二個鏈表為 NULL，直接返回第一個鏈表
struct ListNode* head=NULL,*tail=NULL;
while(list1 && list2)
{
if(list1->val < list2->val)//比較鏈表元素誰大,核心是小的先為尾插
{
if(tail==NULL)
{
head= tail= list1;
}
else
{
tail->next=list1;//讓新鏈表的結(jié)點與list1指向的元素想鏈接
tail=tail->next;
}
list1=list1->next;//list1往原始鏈表后面遍歷
}
else
{
if(tail == NULL)
{
head= tail =list2;
}
else
{
tail->next=list2;//讓新鏈表的結(jié)點與list2指向的元素想鏈接
tail=tail->next;
}
list2=list2->next;//list2往原始鏈表后面遍歷
}
}
//若其中一個鏈表已經(jīng)遍歷到NULL，直接把另一個鏈表的所有元素原封不動拷貝到新鏈表
if(list1)
{
tail->next=list1;
}
if(list2)
{
tail->next=list2;
}
return head;
}
代碼執(zhí)行:?
文章來源：http://www.zghlxwxcb.cn/news/detail-637531.html
? ? ? ? ?本文到此結(jié)束，如有錯誤，隨時歡迎大家指正！文章來源地址http://www.zghlxwxcb.cn/news/detail-637531.html
到了這里，關(guān)于【鏈表OJ 5】合并兩個有序鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
