运用类结构的相关知识，构造链表类，完成奇偶链表合并：给定一个单链表，将所有的奇数节点和偶数节点分别排在一起（注意：这里的奇数节点和偶数节点指的是编号的奇偶性，而不是节点的值的奇偶性），并输出合并后的结果链表。 说明： 应当保持奇数节点和偶数节点的相对顺序。 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。 当输入链表节点个数为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个节点。 输出 奇数链表在前，偶数链表在后，输出合并之后的结果链表。 结果链表中每相邻元素之间使用空格隔开，最后一个节点后没有空格，每输出一个结果链表后换行。

为了方便理解和实现，我先给出 Node 类的定义：

class Node{
public:
    int val;
    Node* next;
    Node(int v):val(v),next(NULL){};
};

然后是 List 类的实现：

class List{
public:
    Node* head;
    Node* tail;
    List(){head=NULL;tail=NULL;};
    void Insert(int n){
        Node* node = new Node(n);
        if(head==NULL){
            head=node;
            tail=node;
        }
        else{
            tail->next=node;
            tail=node;
        }
    }
    void Print(){
        Node* p=head;
        while(p!=NULL){
            cout<<p->val<<" ";
            p=p->next;
        }
        cout<<endl;
    }
    void Solution(){
        if(head==NULL){
            cout<<"NULL"<<endl;
            return;
        }
        Node* odd=head;
        Node* even=head->next;
        Node* even_head=even;
        while(even!=NULL && even->next!=NULL){
            odd->next=even->next;
            odd=odd->next;
            even->next=odd->next;
            even=even->next;
        }
        odd->next=even_head;
        Print();
    }
};

其中 Solution 函数实现了奇偶链表合并的算法。具体来说，我们使用三个指针 odd、even 和 even_head。odd 指向奇数节点的末尾，even 指向偶数节点的末尾，even_head 则指向偶数节点的开头。我们从 head 开始遍历链表，每次将 odd 指向当前节点，even 指向下一个节点，然后依次将 odd 指向下一个奇数节点，even 指向下一个偶数节点。最后，将奇数链表的末尾指向偶数链表的开头，即 odd->next=even_head，得到合并后的链表。

最后，我们在主函数中读入数据并调用 List 类的 Insert 和 Solution 函数即可：

int main(){
    int n;
    cin>>n;
    while(n--){
        int m;
        cin>>m;
        List list;
        for(int i=0;i<m;i++){
            int x;
            cin>>x;
            list.Insert(x);
        }
        list.Solution();
    }
    return 0;
}