21.合并两个有序链表Leetcode C语言

方法一：新建一个临时变量temp，用temp将L1和L2头部的较小的存储起来，然后往后依次存储，具体代码如下。
时间复杂度：O（M+N） 取决于L1和L2的长度
空间复杂度：O（1）

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
   
    struct ListNode* p=l1;
    struct ListNode* q=l2;
    struct ListNode* temp = malloc(sizeof(struct ListNode));
    temp->next=NULL;
    temp->val=0;
    struct ListNode* t = temp;
    while(q||p){
        if(!p){
           t->next=q;
            break;
        }
        if(!q){
           t->next=p;
            break;
        }
        if(p->val <= q->val ){
            t->next=p;
            p=p->next;
            t=t->next;
        }else{
            t->next=q;
            q=q->next;
            t=t->next;
        }
    }
    return temp->next;
}

方法二：
通过问题转化，利用递归解题。
原问题：将L1和L2中的元素按照从小到大用一个链表串起来。
转化：先找到L1和L2头部最小的元素拿出来。该元素的指针域指向用该函数将剩下的元素串起来的链表。
代码如下：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(!l1)
       return l2;
    if(!l2)
        return l1;
    if(l1->val <= l2->val){
        l1->next = mergeTwoLists(l1->next,l2);
        return l1;    
    }
    else{
        l2->next = mergeTwoLists(l1,l2->next);
        return l2;
    }         
}