题解 | #链表合并#

链表合并

https://www.nowcoder.com/practice/27c833289e5f4f5e9ba3718ce9136759

#include <iostream>
#include <stdio.h>
#include <sys/types.h>
using namespace std;
typedef struct ListNode
{
    int data;
    struct ListNode* next;
    ListNode(int data=0):data(data),next(nullptr)
    {}

}ListNode;
class SingleList
{
    public:
    SingleList()
    {
        head=new ListNode();
        tail=head;
    }
    ~SingleList()
    {
        for(ListNode* p=head;p!=nullptr;)
        {
            ListNode* t=p;
            p=p->next;
            delete t;
            t=nullptr;
        }
        tail=nullptr;
        head=nullptr;
    }
    void push_back(int val)
    {
        ListNode* p=new ListNode(val);
        tail->next=p;
        tail=p;
    }
    ListNode* gethead()
    {
        return head;
    }
    private:
    ListNode* head;
    ListNode* tail;
};
void mergelist(ListNode* head1,ListNode* head2)
{
    ListNode* p=head1->next;
    ListNode* q=head2->next;
    ListNode* tail=head1;//head1或head2都可以,最终head1和head2都是指向一条链表
    head2->next=nullptr;//这里要避免两条链表节点的二次析构
    while(p!=nullptr&&q!=nullptr)
    {
        if(q->data<p->data)
        {
            tail->next=q;
            q=q->next;
        }
        else 
        {
            tail->next=p;
            p=p->next;
        }
        tail=tail->next;
    }
    if(p==nullptr)
    {
        tail->next=q;
    }
    else 
    {
        tail->next=p;
    }
}
int main() {
    SingleList list1;
    int data;
    while(scanf("%d",&data)!=-1)
    {
        list1.push_back(data);
        if(getchar()=='\n')break;//必须加上这句话,不然会出问题
    }
    SingleList list2;
    while(scanf("%d",&data)!=-1)
    {
        list2.push_back(data);
        if(getchar()=='\n')break;
    }
    mergelist(list1.gethead(), list2.gethead());
    for(ListNode* p=list1.gethead()->next;p!=nullptr;p=p->next)
    {
        cout<<p->data<<" ";
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

可以使用双指针的思想进行求解,两个指针分别指向两条链表,但是还要增加一个tail指针,作为合并链表的末尾节点,tail永远会接上两个指针中值小的那个(从小到大排序的情况),当一个指针为空时,tail就接上指向了另一条链表的那个指针就行了,需要注意析构函数的问题,在析构两条链表的时候,会再次析构同一个节点,只需要将一条链表的头节点指向空就行了。

全部评论

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
06-28 22:48
已编辑
广东金融学院 Java
小浪_Coding:学院本+这俩项目不是buff叠满了嘛
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务