当前位置:首页 » 《资源分享》 » 正文

【力扣LeetCode】合并两个有序链表_Layman光~的博客

15 人参与  2021年10月31日 11:43  分类 : 《资源分享》  评论

点击全文阅读


题目:

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
在这里插入图片描述

题目分析:

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

代码实现:

/**
 * 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;

}

点击全文阅读


本文链接:http://zhangshiyu.com/post/30305.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1