文章目錄
- 題目描述
- 思路
- 代碼實作
題目描述
將兩個升序鏈表合并為一個新的 升序 鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，（題目來源）
思路
該題的思路比較簡單，我們只需創建一個頭結點，然后從兩個鏈表的表頭開始依次比較傳入的兩個鏈表的結點的大小，并將兩個鏈表中較小的結點尾插到新鏈表的后面即可，
完成一次尾插后，接著比較未尾插的結點，并將較小的結點繼續尾插到新鏈表后面，
直到最后兩個鏈表的結點都被尾插到新鏈表的后面，
注意兩點：
1.在尾插程序中，若某一鏈表已被遍歷完畢，則直接將另一個未遍歷完的鏈表剩下的結點尾插到新鏈表后面即可，
2.函式回傳的時候，不是回傳頭結點的地址，而是第一個結點的地址，所以我們要回傳頭結點指向的位置并將頭結點釋放，
代碼實作
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));//申請一個頭結點
struct ListNode* tail = guard;//尾指標
struct ListNode* cur1 = l1;//記錄當前遍歷到的l1鏈表的結點位置
struct ListNode* cur2 = l2;//記錄當前遍歷到的l2鏈表的結點位置
while (cur1&&cur2)//當l1，l2中有一個鏈表遍歷完畢時便停止
{
//取小的結點尾插到新鏈表后面
if (cur1->val < cur2->val)
{
tail->next = cur1;
cur1 = cur1->next;
}
else
{
tail->next = cur2;
cur2 = cur2->next;
}
tail = tail->next;//結點增加，尾指標后移
}
//將未遍歷完的鏈表的剩余結點接到新鏈表后面
if (cur1)
tail->next = cur1;
else
tail->next = cur2;
struct ListNode* head = guard->next;//新鏈表的頭指標
free(guard);//釋放頭結點
return head;//回傳新鏈表
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/276663.html
標籤：其他
上一篇：java SSM校園兼職平臺（完整原始碼+sql可直接運行）主要實作的兼職資訊的查看、發布兼職、審核、合同簽訂、論壇交流、收藏、用戶管理、平臺公告、我的兼職、我的發布、我的簽訂等功能、
下一篇：爬蟲入門級別教程(小白水平)