DLL

#include<iostream>

using namespace std;

struct DLLnode {
    int value;
    DLLnode *left;
    DLLnode *right;
};

void add(DLLnode *start, int val) 
{
    DLLnode *p = start;
    while ((p->right)) {
        p = p->right;
    }
    DLLnode *n = new DLLnode();
    n->value = val;
    n->left = p;
    n->right = p->right;
    p->right = n;
}

void merge_sorted(DLLnode *l1, DLLnode *l2, DLLnode *r)
{
    DLLnode *p, *q, *n;
    p=l1->right;
    q=l2->right;
    while(p && q)
    {
        if(p->value<= q->value)
        {
            n=p->right;
            if(p->right!=nullptr)
            {
                p->right->left=p->left;
            }
            p->left->right=p->right;
            r->right=p;
            r->left=r;
            r=r->right;
            p=n;
        }
        else
        {
            n=q->right;
            if(q->right!=nullptr)
            {
                q->right->left=q->left;
            }
            q->left->right=q->right;
            r->right=q;
            r->left=r;
            r=r->right;
            q=n;
        }
    }
    while(p!=nullptr)
    {
        r->right=p;
        r->left=r;
        r=r->right;
        p=p->right;
    }
    while(q!=nullptr)
    {
        r->right=q;
        r->left=r;
        r=r->right;
        q=q->right;
    }
    
}

void print(DLLnode *start)
{
    DLLnode *p=start->right;
    while (p!=nullptr)
    {
        cout<<p->value<<" ";
        p=p->right;
    }
}

int main() {
    DLLnode *l1 = new DLLnode();
    l1->left = l1->right = nullptr;

    DLLnode *l2 = new DLLnode();
    l2->left = l2->right = nullptr;

    DLLnode *l3 = new DLLnode();
    l3->left = l3->right = nullptr;

 int i, n, m, aa;
    cin>>n>>m;
    for(i=1; i<=n; i++)
    {
        cin>>aa;
        add(l1, aa);
    }
    for(i=0; i<m; i++)
    {
        cin>>aa;
        add(l2, aa);
    }
    //print(l1);
    merge_sorted(l1, l2, l3);
    print(l3);
    return 0;
}