您现在的位置是:首页 >学无止境 >合并两个有序链表网站首页学无止境

合并两个有序链表

fighting小泽 2023-06-16 16:00:02
简介合并两个有序链表

1.题目描述

题目链接力扣21,合并两个有序链表

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

在这里插入图片描述

2.解题思路

方法1:

首先我们能够想到的就是遍历一遍数组,判断两个结点的大小,将数值小的结点放在前面,数值大的不断尾插在后面。是不是听着挺简单的?

具体实现:

我们可以创建两个空指针,head用来存放链表的头结点,tail用来遍历两条链表,将两条链表链接起来。

  • 当某个链表为空时,我们可以直接返回另一条链表
  • 当两个链表都不为空时,我们可以不断比较两条链表的大小,当 head 和 tail 为空时,我们将较小的结点同时赋给 head 和 tail。然后就是比较两条list的大小,将tail指向较小的结点,并将 tail 移到它的下一个结点位置。同时也将 list 指向它的下一个结点。
  • 当一条链表遍历完后,由于链表是链接起来的,我们可以直接将尾指针 tail 指向另一条链表。这样两条链表就链接起来了。
  • 最后我们再返回头结点 head 就可以了。

在这里插入图片描述

上代码:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1==NULL)
    return list2;
    if(list2==NULL)
    return list1;

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

        }
        else
        {
             if(head == NULL)
            {
                head = list2;
                tail = head;
                list2 = list2->next;
            }
            else
            {
                tail->next = list2;
                list2 = list2->next;
                tail = tail->next;
            }
        }
        if(list1)
        tail->next=list1;
        else
        tail->next=list2;
    }
    return head;
}

在这里插入图片描述

方法2:

  • 方法二和方法一差不多,我们可以创建一个带哨兵位的头结点,将小的结点不断尾插到这个带哨兵位的头节点后面,这样我们就不用判断链表是不是空链表了。
  • 所谓带哨兵位的链表,就是一个附加的链表的节点,该节点作为第一个节点,它的值域并不存储任何东西,只是为了操作的方便引用的。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* f1=list1;
    struct ListNode* f2=list2;
    struct ListNode* head=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* f3=head;
   

    while(f1 && f2)
    {
        if(f1->val < f2->val)
        {
           f3->next=f1;
            f1=f1->next;
        }
        else
        {
            f3->next=f2;
            f2=f2->next;
        }
            f3=f3->next;
            f3->next=NULL;
    }
        if(f2==NULL)
         {
          f3->next=f1;
         }
         else 
        {
          f3->next=f2;
        }    
    return head->next;
}

在这里插入图片描述

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。