題目：
將兩個升序鏈表合并為一個新的升序鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，
題目分析：
解決這個問題的方法是，可以將兩個鏈表中的資料依次比較，然后我們可以將較小的取下來尾插，就這樣依次進行，直到其中一個走到空，就可以結束了，
代碼實作：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if(l1 == NULL)
return l2;
if(l2 == NULL)
return l1;
struct ListNode*n1,*n2;
n1 = l1;
n2 = l2;
struct ListNode*newhead,*tail;
newhead = tail = NULL;
while(n1 && n2)
{
if(n1->val<n2->val)
{
if(tail == NULL)
{
newhead = tail = n1;
}
else
{
tail->next = n1;
tail = n1;
}
n1 = n1->next;
}
else
{
if(tail == NULL)
{
newhead = tail = n2;
}
else
{
tail->next = n2;
tail = n2;
}
n2 = n2->next;
}
}
if(n1)
{
tail->next = n1;
}
if(n2)
{
tail->next = n2;
}
return newhead;
}
優化方案：
看上面的代碼，我們可能會發現其中的回圈有點冗余，因此我們可以改進一下，我們可以在這兩個鏈表中首先比較找出一個較小的值作為頭節點，然后進行尾插；我們還可以用一個帶哨兵位的頭節點來解決這個問題，下面我們就分別給出兩端優化的代碼：
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if(l1 == NULL)
return l2;
if(l2 == NULL)
return l1;
struct ListNode*n1,*n2;
n1 = l1;
n2 = l2;
struct ListNode*newhead,*tail;
newhead = tail = NULL;
//先取一個小的做頭節點
if(n1->val < n2->val)
{
newhead = tail = n1;
n1 = n1->next;
}
else
{
newhead = tail = n2;
n2 = n2->next;
}
while(n1 && n2)
{
if(n1->val<n2->val)
{
tail->next = n1;
tail = n1;
n1 = n1->next;
}
else
{
tail->next = n2;
tail = n2;
n2 = n2->next;
}
}
if(n1)
{
tail->next = n1;
}
if(n2)
{
tail->next = n2;
}
return newhead;
}
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if(l1 == NULL)
return l2;
if(l2 == NULL)
return l1;
struct ListNode*n1,*n2;
n1 = l1;
n2 = l2;
struct ListNode*newhead,*tail;
newhead = tail = NULL;
//給一個哨兵位的頭節點，方便尾插，處理完以后，再刪掉，
newhead = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
while(n1 && n2)
{
if(n1->val<n2->val)
{
tail->next = n1;
tail = n1;
n1 = n1->next;
}
else
{
tail->next = n2;
tail = n2;
n2 = n2->next;
}
}
if(n1)
{
tail->next = n1;
}
if(n2)
{
tail->next = n2;
}
struct ListNode* first = newhead->next;
free(newhead);
return first;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/299980.html
標籤：其他
上一篇：微信小程式使用sass