【21. 合并两个有序链表】

---

一、题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

题目链接

---

二、提供方便走读代码的图

---

三、题目代码

写法一：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    
    struct ListNode* head=NULL;
    struct ListNode* tail=NULL;
    if(list1==NULL)
    return list2;
    if(list2==NULL)
    return list1;
    
    while(list1&&list2)
    {
    
        if(list1->val < list2->val)
        {
    
            if(head==NULL)
            {
    
                head=tail=list1;
            }
            else
            {
    
                tail->next=list1;
                tail=tail->next;
            }
            list1=list1->next;
        }
        else
        {
    
            if(head==NULL)
            {
    
                head=tail=list2;
            }
            else
            {
    
                tail->next=list2;
                tail=tail->next;
            }
            list2=list2->next;
        }
    }
    if(list1!=NULL)
    {
    
        tail->next=list1;
    }
    if(list2!=NULL)
    {
    
        tail->next=list2;
    }
    return head;
}

写法二：带头结点

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    
    struct ListNode* head=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* tail=head;
    if(list1==NULL)
    return list2;
    if(list2==NULL)
    return list1;
    
    while(list1&&list2)
    {
    
        if(list1->val < list2->val)
        {
    
            tail->next=list1;
            tail=tail->next;
            list1=list1->next;
        }
        else
        {
    
           
            tail->next=list2;
            tail=tail->next;
            list2=list2->next;
        }
    }
    if(list1!=NULL)
    {
    
        tail->next=list1;
    }
    if(list2!=NULL)
    {
    
        tail->next=list2;
    }
    struct ListNode* list=head->next;
    free(head);
    return list;
}

---

以上是本篇文章的全部内容，如果文章有错误或者有看不懂的地方，多和喵博主交流。互相学习互相进步。如果这篇文章对你有帮助，可以给喵博主一个关注，你们的支持是我最大的动力。