力扣---LeetCode21. 合并两个有序链表(链表经典题)

2023-06-28 70

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 第八弹——力扣LeetCode每日一题

前言

焦虑不会消除明天的悲伤只会让你今天的力量荡然无存

本章的内容是力扣每日随机一题的部分方法的解析

提示：以下是本篇文章正文内容，下面案例可供参考

21. 合并两个有序链表

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

链接：

21. 合并两个有序链表link

方法一：取小尾插

1.1代码：

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(tail==NULL)
            {
                head=tail=list1;
            }
            else
            {
                tail->next=list1;
                tail=tail->next;
            }
            list1=list1->next;
        }
        else
        {
            if(tail==NULL)
            {
                head=tail=list2;
            }
            else
            {
                tail->next=list2;
                tail=tail->next;
            }
            list2=list2->next;
        }
    }
    if(list1)
    {
        tail->next=list1;
    }
    if(list2)
    {
        tail->next=list2;
    }
    return head;
}

1.2 流程图：

1.3 注意：

要注意判断list1和;ist2是否是空链表

要考虑第一次插入的情况是没有结点的

方法二：带哨兵位

所谓带哨兵位的链表，就是一个附加的链表的节点，该节点作为第一个节点，它的值域并不存储任何东西，只是为了操作的方便引用的。

如果一个链表有哨兵节点的话,那么线性表的第一个元素应该是链表的第二个节点.

2.1代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* head=NULL;
    struct ListNode* tail=NULL;
    head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
    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)
    {
        tail->next=list1;
    }
    if(list2)
    {
        tail->next=list2;
    }
    struct ListNode* del=head;
    head=head->next;
    free(del);
    del=NULL;
    return head;
}