#include <cmath>
#include <vector>
#include <iostream>
using namespace std;
 
struct Node
{
	int data;
	Node* next;
};
 
class List {
private:
	Node* head;
public:
	List() {
		head = NULL;
	}
 
	void addNode(int d) {
		Node* nd = new Node;
		nd->data = d;
		nd->next = NULL;
		if (head == NULL) {
			head = nd;
		}
		else {
			Node* current = head;
			while (current->next != NULL) {
				current = current->next;
			}
			current->next = nd;
		}
	}
 
	void PrintList() {
		Node* current = head;
		while (current != NULL) {
			cout << current->data << " ";
			current = current->next;
		}
	}
 
	void sort(List& list, vector<int>& vec,int &pos,vector<int>& vec2) {
		Node* current = head;
		while (current != NULL) {
			int cur = current->data;
			if (pos % 2 != 0) {
				vec.push_back(cur);
			} else vec2.push_back(cur);
			pos++;
			current = current->next;
		}
		for(int i=0;i<vec.size();i++){
		    vec2.push_back(vec[i]);
		}
		for (int i = 0; i < vec.size(); i++) {
			list.addNode(vec[i]);
		}
 
	}
 
	void del(int n) {
		Node* temp = head, * helping = head;
 
		for (int i = 0; i < n; i++) {
			helping = temp;
			temp = temp->next;
		}
 
		if (temp == head)
		{
			head = temp->next;
		}
		else {
			helping->next = temp->next;
		}
		free(temp);
	}
};
 
int main()
{
	vector<int>vec, vec2;
	setlocale(LC_ALL, "Russian");
	List list,newlist;
	srand(time(NULL));
	int n;
	cout << "Размер:"; cin >> n;
	int* mas = new int[n];
	for (int i = 0; i < n; i++) {
		int x = rand() % 10;
		mas[i] = x;
		list.addNode(x);
	}
	int pos=0;
	cout << "old list:\n"; list.PrintList();
	list.sort(list, vec,pos,vec2);
	for (int i = 0; i < n; i++) {
		newlist.addNode(vec2[i]);
	}
	cout << "\nnew list:\n";
	newlist.PrintList();
}