[Leetcode]合并两个有序链表

力扣链接

依次比较,取小的尾插:

初步代码:

/**
 * 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,*tail = NULL;
    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;
    while(cur1 && cur2)
    {
        if(cur1->val<cur2->val)
        {
            if(head == NULL)
            {
                head = tail = cur1;//为空直接赋值
            }
            else
            {
                 tail->next = cur1;
                 tail = tail->next;

            }
           
            cur1 = cur1->next;
            
        }
        else
        {
            if(head == NULL)
            {
                head = tail = cur2;
            }
            else
            {
                 tail->next = cur2;
                 tail = tail->next;

            }
           
            cur2 = cur2->next;

        }
    
    }
    if(cur2)
    {
        tail->next = cur2;
    }
    if(cur1)
    {
        tail->next = cur1;
    }
    return head;


}

通过测试用例来看,当其中一个链表为空时,上面的代码不执行while循环,直接执行下面的if语句,而此时tail为空,所以出现了错误.

修改方法

1.直接判空返回(在声明前加入)

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if(list1 == NULL)//判空返回
         return list2;//
    if(list2 == NULL)//
         return list1;//

    struct ListNode* head = NULL,*tail = NULL;
    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;
    while(cur1 && cur2)
    {
        if(cur1->val<cur2->val)
        {
            if(head == NULL)
            {
                head = tail = cur1;//为空直接赋值
            }
            else
            {
                 tail->next = cur1;
                 tail = tail->next;


            }
           
            cur1 = cur1->next;
            
        }
        else
        {
            if(head == NULL)
            {
                head = tail = cur2;
            }
            else
            {
                 tail->next = cur2;
                 tail = tail->next;


            }
           
            cur2 = cur2->next;


        }
    
    }
    if(cur2)
    {
        tail->next = cur2;
    }
    if(cur1)
    {
        tail->next = cur1;
    }
    return head;



}

2.引用带哨兵卫的头结点(可以减少代码量,不存放有效数据)

哨兵位的头结点不存放有效数据,但是一直存在,所以不需要判空,需要开辟和释放空间

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



struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;
     struct ListNode* guard = NULL,*tail = NULL;
    guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    tail->next = NULL;
    while(cur1 && cur2)
    {
        if(cur1->val<cur2->val)
        {
        //     if(head == NULL)
        //     {
                // head = tail = cur1;//为空直接赋值
            // }
            // else
            // {
                 tail->next = cur1;
                 tail = tail->next;
            // }          
                 cur1 = cur1->next;           
        }
        else
        {
            // if(head == NULL)
            // {
                // head = tail = cur2;
            // }
            // else
            // {
                 tail->next = cur2;
                 tail = tail->next;
            // }         
                cur2 = cur2->next;
        }
    
    }
    if(cur2)
    {
        tail->next = cur2;
    }
    if(cur1)
    {
        tail->next = cur1;
    }

    struct ListNode* head = guard->next;//存放哨兵位头结点的下一位,方便返回
    free(guard);
    return head;
}