题解 | #链表合并#

#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就接上指向了另一条链表的那个指针就行了，需要注意析构函数的问题，在析构两条链表的时候，会再次析构同一个节点，只需要将一条链表的头节点指向空就行了。