合併兩個有序鏈表

描述#

將兩個有序鏈表合併為一個新的有序鏈表並返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

示例：

輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

思路#

有空鏈表時，返回另一個鏈表，無論另一個鏈表是否為空鏈表皆符合規則
將首元素較小的鏈表設為被插入鏈表，另一個設為插入鏈表，被插入鏈表即最後返回的鏈表
當前插入鏈表非空或被插入鏈表還有下一個元素時，如果插入鏈表的元素不大於被插入鏈表下一個元素，則插入到下一個元素之前，否則當前插入鏈表往後遞增
插入鏈表仍有元素存在時（當有大於被插入鏈表最後一個數時，上個過程不會插入進去），需要直接接在被插入鏈表後

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* l_get_buffer,*l_set_buffer,*l_final,*l_get,*l_set;
    //有空鏈表時
    if(!(l1 && l2)) {
        return l1?l1:l2;//l1非空則返回l1,否則返回l2
    }
    //l_set設為首元素較小的一個
    l_set = (l1->val <= l2->val)?l1:l2;
    l_get = (l_set == l1)?l2:l1;
    //最終返回首元素較小的鏈表
    l_final = l_set;
    while (l_get != 0 && l_set->next != 0)
    {
        if((l_get->val) <= (l_set->next->val))  {
            //記錄當前兩個指針
            l_get_buffer = l_get;
            l_set_buffer = l_set;
            //next指針更新   
            l_get = l_get->next; 
            //指針重組  
            l_get_buffer->next = l_set_buffer->next;
            l_set_buffer->next = l_get_buffer; 
        }  
        else 
            l_set = l_set->next;
    }
    //有剩餘元素未插入
    if(l_get != 0)
        l_set->next = l_get;
    return l_final;
}

注意#

插入元素時，被插入鏈表指針不能後移，否則會漏過被插入鏈表的一個元素的比較