#include "stdafx.h"
#include <iostream>
#include <cassert>
using namespace std;

// Структура - элемент списка

struct list {
  int val;
  list* next;

  list(int val_, list* next_) :
    val(val_), next(next_)
  {}
};

// Добавить элемент в начало списка

void add(list*& head, int n)
{
  head = new list(n, head);
}

// Напечатать все элементы списка

void print(const list* head)
{
  for (const list* p = head; p != 0; p = p->next) {
    cout << p->val << " ";
  }
  cout << "\n";
}

// Удалить из списка первый элемент

void delete_first(list*& head)
{
  assert(head != 0);	// Условие: В списке должен быть хотя бы один элемент

  list* temp = head;
  head = head->next;
  delete temp;
}

// Удалить из списка n-ный элемент

void delete_nth(list*& head, int n)
{
  // Найдем n-1-вый элемент
  list* p = head;
  for (int i = 0; i < n-1; i++) {
    assert(p != 0);
    p = p->next;
  }

  list* temp = p->next;
  assert(temp != 0);     // Условие: в списке одлжно быть не меньше n элементов 

  p->next = p->next->next;
  delete temp;
}

// Создать копию списка, в которой элементы идут в обратном порядке

void reverse_copy(list*& head1, const list* head)
{
  head1 = 0;

  // Просто идем по списку и добавляем все элементы в новый список

  for (const list* p = head; p != 0; p = p->next) {
    add(head1, p->val);
  }
}

// Переставить в списке элементы в обратном порядке

void reverse(list*& head)
{
  list* new_head = 0; // Как бы создаем новый список

  list* p = head; 
  while (p != 0) { // Цикл по всем элементам
    list* next = p->next;

    p->next = new_head; // Элемент добавляем в начало нового списка
    new_head = p;

    p = next;
  }

  head = new_head;
}

int main ()
{
  list* head = 0;

  for (int i = 0; i < 10; i++)
    add(head, i);
  print(head);

  delete_first(head);
  print(head);

  delete_nth(head, 3);
  print(head);

  list* head1;
  reverse_copy(head1, head);
  print(head1);

  reverse(head);
  print(head);

  return 0;
}