【力扣LeetCode】合并两个有序链表

DevTTL 发布于2021-09-14 17:57 / 1576人阅读

摘要：题目将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。下面我们就分别给出两端优化的代码先取一个小的做头节点给一个哨兵位的头节点，方便尾插，处理完以后，再删掉。

题目：

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

题目分析：

解决这个问题的方法是，可以将两个链表中的数据依次比较，然后我们可以将较小的取下来尾插，就这样依次进行，直到其中一个走到空，就可以结束了。

代码实现：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){    if(l1 == NULL)        return l2;    if(l2 == NULL)        return l1;    struct ListNode*n1,*n2;    n1 = l1;    n2 = l2;    struct ListNode*newhead,*tail;    newhead = tail = NULL;    while(n1 && n2)    {        if(n1->val<n2->val)        {            if(tail == NULL)            {                newhead = tail = n1;            }            else            {                tail->next = n1;                tail = n1;            }            n1 = n1->next;        }        else        {            if(tail == NULL)            {                newhead = tail = n2;            }            else            {                tail->next = n2;                tail = n2;            }            n2 = n2->next;        }    }    if(n1)    {        tail->next = n1;    }    if(n2)    {        tail->next = n2;    }    return newhead;}

优化方案：

看上面的代码，我们可能会发现其中的循环有点冗余，因此我们可以改进一下，我们可以在这两个链表中首先比较找出一个较小的值作为头节点，然后进行尾插；我们还可以用一个带哨兵位的头节点来解决这个问题。下面我们就分别给出两端优化的代码：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){    if(l1 == NULL)        return l2;    if(l2 == NULL)        return l1;    struct ListNode*n1,*n2;    n1 = l1;    n2 = l2;    struct ListNode*newhead,*tail;    newhead = tail = NULL;    //先取一个小的做头节点    if(n1->val < n2->val)    {        newhead = tail = n1;        n1 = n1->next;    }    else    {        newhead = tail = n2;        n2 = n2->next;    }    while(n1 && n2)    {        if(n1->val<n2->val)        {            tail->next = n1;            tail = n1;            n1 = n1->next;        }        else        {            tail->next = n2;            tail = n2;            n2 = n2->next;        }    }    if(n1)    {        tail->next = n1;    }    if(n2)    {        tail->next = n2;    }    return newhead;}

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){    if(l1 == NULL)        return l2;    if(l2 == NULL)        return l1;    struct ListNode*n1,*n2;    n1 = l1;    n2 = l2;    struct ListNode*newhead,*tail;    newhead = tail = NULL;    //给一个哨兵位的头节点，方便尾插，处理完以后，再删掉。    newhead = tail = (struct ListNode*)malloc(sizeof(struct ListNode));    while(n1 && n2)    {        if(n1->val<n2->val)        {            tail->next = n1;            tail = n1;            n1 = n1->next;        }        else        {            tail->next = n2;            tail = n2;            n2 = n2->next;        }    }    if(n1)    {        tail->next = n1;    }    if(n2)    {        tail->next = n2;    }    struct ListNode* first = newhead->next;    free(newhead);    return first;}

云服务器私有云合并链表的c语言合并两个单链表 linux 两个硬盘合并 js 两个数据合并

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/119939.html

力扣(LeetCode)21

摘要：题目地址题目描述将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。若两者其中有一个为就返回另一个。题目地址：https://leetcode-cn.com/probl...题目描述：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。解答：递归思想。若两者其中有一个为null就返回另一个。否则，val...

gougoujiang 2019-08-16 15:13 评论0 收藏0
数据结构之链表OJ练习检验你的链表水平是否合格

摘要：同时让当前结点的指针指向，从而实现从链表尾部开始的局部反转当递归函数全部出栈后，链表反转完成。这个链表的倒数第个节点是值为的节点。新链表是通过拼接给定的两个链表的所有节点组成的。目录 1.反转链表 K个一组翻转链表链表的中间节点：链表倒数第k个节点：删除链表倒数第k个节...

andycall 2021-11-25 09:43 评论0 收藏0
＜LeetCode天梯＞Day027 合并两个有序链表（递归法+改进递归） | 初级算法 | Pyt

摘要：示例输入输出示例输入输出示例输入输出提示两个链表的节点数目范围是和均按非递减顺序排列递归法分析递归法，和之前的一样，还是需要先设置跳出判断，这里设置为空的时候跳出。 ...

zhonghanwen 2021-11-18 10:02 评论0 收藏0
Chain Surfase Test - java 链表经典 OJ 面试题 - 巨细

摘要：新链表是通过拼接给定的两个链表的所有节点组成的。保证链表长度小于等于。注意，函数返回结果后，链表必须保持其原始结构。注意不作为参数进行传递，仅仅是为了标识链表的实际情况。如果是，则在该链表中没有环。说明不允许修改给定的链表。 ...

aristark 2021-11-11 16:54 评论0 收藏0
k个一组翻转链表哔哩哔哩2020校园招聘笔试题/LeetCode_25（困难）讲解

摘要：三代码实现用空格分割链表每个元素将链表分为组组组内翻转，如果不够一组，就不进行翻转。下一组的起始位置为什么的上限是输入的要求是每个元素后面跟个但是最后一个没有，最后一个元素就要最后输出。 ...

CntChen 2021-09-10 10:50 评论0 收藏0