#include<iostream>

struct node{
    int payload;
    node* next;
    node(int payload){this->payload=payload;next=nullptr;}
};

void bianli(node* head){
  node* iterator = head;
  while(iterator){
    std::cout << iterator->payload << " ";
    iterator = iterator->next;
  }
  std::cout<<" "<<std::endl;
}

class linkedlist{
    node* head,*tail;
public:
    linkedlist():head(nullptr),tail(nullptr){};
    void push_back(int value){
        if(empty()){
            head = tail = new node(value);
        }else{
            tail->next = new node(value);
            tail = tail->next;
        }
    }

    int front(){
        if(empty()){
            throw "The list is empty";
        }
        return head->payload;
    }
    void pop_front(){
        if(empty()){
            throw "The list is empty";
        }
        node* first_node = head;
        head = head->next;
        delete first_node;
    }
    bool empty(){
        return head==nullptr;
    }
    void output(){
        node* iterator = head;
        while(iterator){
            std::cout << iterator->payload << " ";
            iterator = iterator->next;
        }
        std::cout << std::endl;
    }
};

linkedlist merge(linkedlist a,linkedlist b){
    linkedlist result ;
    while(!a.empty() || !b.empty()){
        if(a.empty()){
            result.push_back(b.front());
            b.pop_front();
        }else if(b.empty()){
            result.push_back(a.front());
            a.pop_front();
        }else if(a.front() > b.front()){
            result.push_back(b.front());
            b.pop_front();
        }else{
            result.push_back(a.front());
            a.pop_front();
        }
    }
    return result;
}

int main(){

    linkedlist a,b;
    a.push_back(4);
    a.push_back(7);
    a.push_back(20);
    a.push_back(21);

    b.push_back(2);
    b.push_back(3);
    b.push_back(5);
    b.push_back(9);
    b.push_back(29);
    b.push_back(40);

    linkedlist result = merge(a,b);
    result.output();
    system("pause");
    return 0;
}