[21] Merge Two Sorted Lists

真是世界廢Orz
初版長這樣
晚點再想怎麼修... Orz

Merge Two Sorted Lists
題意就是字面上的意思XD
請不要問我為什麼那個head好像有點多餘
我也說不上來啊啊啊啊啊啊～～～～
我還是喝西北風吧（奔入雨中）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* p1 = l1;
    struct ListNode* p2 = l2;
    struct ListNode* new, *head;
    if (p1 == NULL)
        return p2;
    if (p2 == NULL)
        return p1;
 
    if (p1->val < p2->val)
    {
        head = p1;
        p1 = p1->next;
    }
    else
    {
        head = p2;
        p2 = p2->next;
    }
    new = head;
    for(;;)
    {
        if (p1 == NULL)
        {
            new->next= p2;
            break;
        }
        if (p2 == NULL)
        {
            new->next= p1;
            break;
        }      

     
        if (p1->val < p2->val)
        {
            new->next = p1;
            p1 = p1->next;
            new = new->next;
        }
        else
        {
            new->next = p2;
            p2 = p2->next;
            new = new->next;
        }      
    }  
 
    return head;
}

update:
看到別人說可以用recursive寫法
但是比較慢啊XD
降子有比較好嗎@__@?!
update 2:
後來發現我多做了幾步贅步XD
其實根本沒想懂吧哈哈哈哈哈哈哈(奔入雨中)

但是有跑過recursive快也有慢的時候,

是個快慢很看系統的寫法?! （sensitive~~~~~)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* head, *tmp;
    if (l1 == NULL)
        return l2;
    if (l2 == NULL)
        return l1;
#if 0        //別人的簡潔版
    if (l1->val < l2->val)
    {
        l1->next = mergeTwoLists(l1->next,l2);
        return l1;
    }
    else
    {
        l2->next = mergeTwoLists(l1,l2->next);
        return l2;
    }
#else    //我的贅步版XD
    if (l1->val < l2->val)
    {
        head = l1;
        tmp = mergeTwoLists(l1->next,l2);
    }
    else
    {
        head = l2;
        tmp = mergeTwoLists(l1,l2->next);      
    }
    head->next = tmp;
    return head;
#endif  
}

20230829 再次更新

沒想到被考這題XD 總覺得開頭的head 很贅步，想把它加進while 裡，

發現加進去以後的code 也是蠻醜的 XD 

好吧那我比較想要把它擺在開頭，有種 initialize 的感覺！！！

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){

if (list1== NULL)

return list2;

if (list2==NULL)

return list1;

struct ListNode *p1,*p2, *head,*ptr;

head = NULL;

p1=list1;

p2=list2;

while (p1!=NULL && p2 != NULL)

{

if (p1->val < p2->val)

{

if (head == NULL)

{

head = p1;

ptr = p1;

}

else

{

ptr->next = p1;

ptr=ptr->next;

}

p1=p1->next;

}

else

{

if (head == NULL)

{

head = p2;

ptr = p2;

}

else

{

ptr->next =p2;

ptr=ptr->next;

}

p2=p2->next;

}

}

if (p1==NULL)

ptr->next=p2;

else

ptr->next=p1;

return head;

}

20230901 更新

最終～過了兩天再寫了一次revursive版本XD

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){

if (list1 ==NULL)

return list2;

if (list2 == NULL)

return list1;

if (list1->val < list2->val)

{

list1->next = mergeTwoLists(list1->next, list2);

return list1;

}

else

{

list2->next = mergeTwoLists(list1, list2->next);

return list2;

}

}