• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

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

互联网 diligentman 4小时前 1次浏览

题目:

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

题目分析:

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

代码实现:

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

}


程序员灯塔
转载请注明原文链接:【力扣LeetCode】合并两个有序链表
喜欢 (0)