《手撕链表题系列-5》合并两个有序链表

/**
 * 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*newhead=malloc(sizeof(struct ListNode));
    newhead->next=NULL;
    //遍历指针
    struct ListNode*cur1=l1,*cur2=l2,*cur3=newhead;
    while(cur1&&cur2)
    {
        if(cur1->val>cur2->val)
        {
             cur3->next=cur2;
             cur3=cur3->next;
             cur2=cur2->next;
        }
        else
        {
            cur3->next=cur1;
            cur3=cur3->next;
            cur1=cur1->next;
        }
    }
//存留节点尾插
    if(cur1)
    {
        cur3->next=cur1;
    }
    if(cur2)
    {
        cur3->next=cur2;
    }
    //记录哨兵后一个空间，并释放哨兵
    struct ListNode*next=newhead->next;
    free(newhead);
    return next;
}