[LeetCode]合并兩個有序鏈表
- 題目
- 分析
- 代碼
- 總結
題目
將兩個升序鏈表合并為一個新的 升序 鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，
鏈接：https://leetcode-cn.com/problems/merge-two-sorted-lists/
分析
我們在進行鏈表合并分析前先回顧這一篇博客https://blog.csdn.net/weixin_52664715/article/details/120741216?spm=1001.2014.3001.5501
在這篇博客中我們學習到了一種思路，就是我們在鏈表的相關問題中，相對簡單一些的問題都是鏈表中增刪查改的使用來解決的
在這里我們根據給出的圖解，可知在這里我們要想合并兩個鏈表可以使用尾插來實作，我們常見兩個指標分別指向兩個鏈表，然后遍歷比較，較小元素尾插的新的鏈表中，當一方鏈表指標指向NULL時，我們的結束兩個指標的遍歷，將未遍歷結束的剩余鏈表鏈接到我們新的鏈表中即可，
代碼
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
if(l1 == NULL)//這里我們對兩個鏈表進行判斷，如果一方鏈表為空，那么我們合并之后的鏈表就是另一個鏈表
return l2;
if(l2 == NULL)
return l1;
struct ListNode* n1 = l1;
struct ListNode* n2 = l2;
struct ListNode* newhead,*tail = NULL;
while(n1 && n2)//我們對兩個同時進行遍歷
{
if(n1->val < n2->val)
{
if(tail == NULL)//當鏈表還沒有第一個元素時，我們對合并鏈表進行初始化
{
tail = newhead = n1;
}
else
{
tail = n1;
tail = tail->next;
}
n1 = n1->next;
}
else
{
if(tail == NULL)
{
tail = newhead = n2;
}
else
{
tail = n2;
tail = tail->next;
}
n2 = n2->next;
}
}
if(n1)//這里我們對兩個鏈表進行判讀，因為一方鏈表已經為遍歷結束，我們將未遍歷結束的鏈表鏈接到合并鏈表之后
{
tail->next = n1;
}
if(n2)
{
tail->next = n2;
}
return newhead;
}
總結
合并鏈表的實作比合并順序表要簡單一些，因為我們不用在計算兩個順序表的空間大小后再進行創建新的順序表，鏈表的合成只需要不斷的尾插即可，不涉及空間的創建與銷毀，但我們在實作這一道題中我們需要注意特殊情況，比如一方鏈表為慷訓者我們在進行尾插時，合成鏈表還沒有進行初始化，
以上就是我對這道題目的個人理解
上述內容如果有錯誤的地方，還麻煩各位大佬指教【膜拜各位了】【膜拜各位了】
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/316635.html
標籤：其他
上一篇：程式的編譯