运用类结构的相关知识，构造链表类，完成奇偶链表合并：给定一个单链表，将所有的奇数节点和偶数节点分别排在一起（注意：这里的奇数节点和偶数节点指的是编号的奇偶性，而不是节点的值的奇偶性），并输出合并后的结果链表。 说明： 应当保持奇数节点和偶数节点的相对顺序。 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。 当输入链表节点个数为0时，输出“NULL”。 链表结构需按如下定义进行实现，其中Node类自行实现： class List{ public: Node* head; Node* tail; List(){head=NULL;}; void Insert(int n);//插入节点 void Print();//打印链表的数据项 void Solution(); }; 输入 第一行一个整数N，代表有N组测试数据，接下来的N行每行第一个数为链表节点个数M，接下来为M个节点。 输出 奇数链表在前，偶数链表在后，输出合并之后的结果链表。 结果链表中每相邻元素之间使用空格隔开，最后一个节点后没有空格，每输出一个结果链表后换行。

以下是完整的实现代码：

#include<iostream>
using namespace std;

struct Node{
    int value;
    Node* next;
    Node(int val):value(val),next(NULL){}
};

class List{
public:
    Node* head;
    Node* tail;
    List(){head=NULL;};
    void Insert(int n){
        if(head==NULL){
            head = new Node(n);
            tail = head;
        }
        else{
            tail->next = new Node(n);
            tail = tail->next;
        }
    }
    
    void Print(){
        Node* cur = head;
        while(cur!=NULL){
            cout<<cur->value<<" ";
            cur = cur->next;
        }
        cout<<endl;
    }
    
    void Solution(){
        if(head==NULL){
            cout<<"NULL"<<endl;
            return;
        }
        List oddList,evenList;
        Node* cur = head;
        bool isOdd = true;
        while(cur!=NULL){
            if(isOdd){
                oddList.Insert(cur->value);
            }
            else{
                evenList.Insert(cur->value);
            }
            isOdd = !isOdd;
            cur = cur->next;
        }
        oddList.tail->next = evenList.head;
        oddList.Print();
    }
};

int main(){
    int N;
    cin>>N;
    while(N--){
        int M;
        cin>>M;
        List list;
        for(int i=0;i<M;i++){
            int val;
            cin>>val;
            list.Insert(val);
        }
        list.Solution();
    }
    return 0;
}

输入格式如下：

2
5 1 2 3 4 5
4 2 3 4 5

输出格式如下：

1 3 5 2 4 
2 4 3 5