merge_sort_list

#include <iostream>

using namespace std;

struct node {
    int val;
    node * nxt;
    node(int v = 0) {
        val = v;
        nxt = nullptr;
    }
};

void print(node * root) {
    node * p = root;
    while (p != nullptr) {
        cout << p->val << " ";
        p = p->nxt;
    }
    cout << "\n";
}

void add(node * &root, node * &last, node * &p) {
    if (root == nullptr) {
        root = p;
        last = p;
        return;
    }
    else {
        last->nxt = p;
        last = p;
    }
}

void msort(node * &root, node * &last, int sz) {
    if (sz <= 1) {
        return;
    }
    node * L = nullptr;
    node * R = nullptr;

    node * L1 = nullptr;
    node * R1 = nullptr;

    int cnt = 0, L_sz = 0, R_sz = 0;
    node * p = root;
    while (p != nullptr) {
        node * q = p;
        p = p->nxt;

        ++cnt;
        if (cnt <= sz / 2) {
            q->nxt = L;
            L = q;
            if (L->nxt == nullptr) {
                L1 = L;
            }
            ++L_sz;
        }
        else {
            q->nxt = R;
            R = q;
            if (R->nxt == nullptr) {
                R1 = R;
            }
            ++R_sz;
        }
    }

    msort(L, L1, L_sz);
    msort(R, R1, R_sz);

    node * l = L;
    node * r = R;
    node * ans = nullptr;
    node * last1 = nullptr;

    while (l != nullptr && r != nullptr) {
        if (l->val == r->val) {
            node * l1 = l;
            node * r1 = r;

            l = l->nxt;
            r = r->nxt;

            l1->nxt = nullptr;
            r1->nxt = nullptr;

            add(ans, last1, l1);
            add(ans, last1, r1);
        }
        else if (l->val < r->val) {
            node * l1 = l;
            l = l->nxt;
            l1->nxt = nullptr;
            add(ans, last1, l1);
        }
        else {
            node * r1 = r;
            r = r->nxt;
            r1->nxt = nullptr;
            add(ans, last1, r1);
        }
    }

    while (l != nullptr) {
        node * l1 = l;
        l = l->nxt;
        l1->nxt = nullptr;
        add(ans, last1, l1);
    }

    while (r != nullptr) {
        node * r1 = r;
        r = r->nxt;
        r1->nxt = nullptr;
        add(ans, last1, r1);
    }
    root = ans;
    last = last1;
}

int main() {
    node * root = nullptr;
    node * last = nullptr;
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;

        node * p = new node(x);
        add(root, last, p);
    }
    msort(root, last, n);
    print(root);

    return 0;
}