当前位置:   article > 正文

合并两个有序链表(超详细)_如何将两个有序链表并为一个有序链表代码

如何将两个有序链表并为一个有序链表代码

文章目录

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

在这里插入图片描述

思路1:带哨兵卫的头节点
定义两个指针 head 和 tail ,比较两个链表中的较小值,放到 tail ->next 中,如果有任意一个链表走到空了,则结束,然后判断找到不为空的链表,把不为空的链表中的数据一次放到新链表中。

画图分析:
在这里插入图片描述
代码的实现:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
	//考虑list1和list2其中一个为空的情况
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    struct ListNode* head=NULL,*tail=NULL;
    //带哨兵卫的头节点,这个头节点不存储有效数据
    head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
    //当list1和list2任意一个为空循环就结束
    while(list1 && list2)
    {
    	//head为空的情况上面已经处理了,这里是head不为空的情况的插入数据
        if(list1->val < list2->val)
        {
            tail->next=list1;
            tail=list1;
            list1=list1->next;
        }
        else
        {
            tail->next=list2;
            tail=list2;
            list2=list2->next;
        }
    }
    //如果list1不为空则把list1后面的数据链接到tail->next的后面
    if(list1)
    tail->next=list1;
    //如果list2不为空则把list2后面的数据链接到tail->next的后面
    if(list2)
    tail->next=list2;
	//在前面malloc的空间需要释放,释放前先保存head->next的地址
    struct ListNode* list=head->next;
    free(head);
    return list;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

思路2:不使用带哨兵卫的头节点

画图分析:
在这里插入图片描述

代码的实现:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    //考虑list1和list2其中一个为空的情况
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    struct ListNode* head=NULL,*tail=NULL;
	//考虑head为空时插入数据
    if(list1->val < list2->val)
    {
        head=tail=list1;
        list1=list1->next;
    }
    else
    {
        head=tail=list2;
        list2=list2->next;
    }
	 //当list1和list2任意一个为空循环就结束
    while(list1 && list2)
    {
    	//head和tail是指向同一块地址的,带哨兵卫的头节点不存储有效数据,所以数据从tail->next开始存
        if(list1->val < list2->val)
        {
            tail->next=list1;
            tail=list1;
            list1=list1->next;
        }
        else
        {
            tail->next=list2;
            tail=list2;
            list2=list2->next;
        }
    }
    	//如果list1不为空则把list1后面的数据链接到tail->next的后面
        if(list1)
        {
            tail->next=list1;
        }
        //如果list2不为空则把list2后面的数据链接到tail->next的后面
        if(list2)
        {
            tail->next=list2;
        }
        //返回头节点
        return head;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

文章到这就结束啦,有问题的小伙伴可以留言噢,谢谢你的赞!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/编程探索家/article/detail/62954
推荐阅读
相关标签