LeetCode | 21. 合并两个有序链表-阿里云开发者社区

LeetCode | 21. 合并两个有序链表

2024-01-24 52

版权

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

简介： LeetCode | 21. 合并两个有序链表

LeetCode | 21. 合并两个有序链表

OJ链接

定义一个新链表，把小的结点尾插到新的链表
注意在插入新的链表中，1. 空链表，插入的节点就是链表的头节点和尾结点。2. 非空链表，插入的节点就是链表的新的尾结点，头结点不变

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1 == NULL)
        return list2;
    if(list2 == NULL)
        return list1;
    struct ListNode* newTail,*newHead;
    newHead = newTail = NULL;
    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;
    while(cur1 && cur2)
    {
        if(cur1->val<cur2->val)
        {
            //将cur1放入新的链表
            if(newHead == NULL)
            {
                newHead = newTail = cur1;
            }
            else
            {
                newTail->next = cur1;
                newTail = newTail->next;
            }
            cur1 = cur1->next;
        }
        else
        {
            //将cur2放入新的链表
            if(newHead == NULL)
            {
                newHead = newTail = cur2;
            }
            else
            {
                newTail->next = cur2;
                newTail = newTail->next;
            }
            cur2 = cur2->next;
        }
    }
    if(cur1)
    {
        newTail->next = cur1;
    }
    if(cur2)
    {
        newTail->next = cur2;
    }
    return newHead;
}

大家可可以看到这个代码很长，很冗余
需要考虑新链表的头结点为空或者非空，所以导致这里的重复代码比较多
我们还有一个方法，创建一个带头单向不循环链表，后续就不需要考虑节点问题了

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1 == NULL)
        return list2;
    if(list2 == NULL)
        return list1;
    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;
    //创建一个带头单向不循环
    struct ListNode* newTail,*newHead;
    newHead = newTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    while(cur1 && cur2)
    {
        if(cur1->val<cur2->val)
        {
            newTail->next = cur1;
            newTail = newTail->next;
            cur1 = cur1->next;
        }
        else
        {
            newTail->next = cur2;
            newTail = newTail->next;
            cur2 = cur2->next;
        }
    }
    if(cur1)
    {
        newTail->next = cur1;
    }
    if(cur2)
    {
        newTail->next = cur2;
    }
    //把动态开辟的空间释放掉
    struct ListNode* tmp = newHead->next;
    free(newHead);
    return tmp;
}