【数据结构与算法】合并两个有序链表

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* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));//新链表头节点指针
    struct ListNode* newtail = newhead;//新链表尾指针

    struct ListNode* p1 = list1;//遍历两个链表的指针
    struct ListNode* p2 = list2;

    while (p1 && p2)//两个链表都不为空执行循环
    {   //哪个链表节点数据小，就将其尾插到新链表
        if (p1->val > p2->val)
        {
            newtail->next = p2;
            p2 = p2->next;
        }
        else
        {
            newtail->next = p1;
            p1 = p1->next;
        }
        newtail = newtail->next;//新链表尾指针向后移动
    }
    //一定有一个链表先走到空，出循环后将另一个链表剩余节点尾插到新链表
    if (p1 == NULL)
    {
        newtail->next = p2;
    }
    if (p2 == NULL)
    {
        newtail->next = p1;
    }
    struct ListNode* ret = newhead->next;
    free(newhead);
    newhead = NULL;
    return ret;
}