#include <stdio.h>
#include <malloc.h>

struct ListElement
{
	int elem;
	struct ListElement* next;
};
typedef struct ListElement Element;
typedef Element* List;

List createList(int n)
{
	//проверка на плешивость
	if (n < 1) return NULL;

	List head = calloc(1, sizeof(Element));//создаем голову, от которой будем шагать    
	head->elem = 1;//присваиваем значение гоовы    
	head->next = NULL;//следующего элемента массива пока нет, поэтому никуда не ведет

	List current = head, next;//создаем экземпляры для текущего и сдедующего элементов

	//расширяем лист до момента, пока не закончатся элементы
	for (size_t i = 1; i < n; i++)
	{
		next = calloc(1, sizeof(Element));//выделяем память для следующего элемента        
		current->next = next;//адресс следующего элемента записываем соответствующую ячейку текущего
		next->elem = i + 1; //присваиваем значение следующей ячейки
		current = next;//текущая ячеука становится следующей
	}
	current->next = NULL;//поскольку это последний элемент, то ссылки на след быть не может

	return head;
}

void showList(List list)
{
	if (!list) return NULL;
	while (list)
	{
		printf("%d ", list->elem);
		list = list->next;
	}
	printf("\n");
}

void deleteList(List list)
{
	if (list->next == NULL) return NULL; //если лист пустой возвращаем NULL

	while (list->next)//идем в цикле пока у элемента есть ссылка на следующий элемент
	{
		List previous = list;//создаем ссылку на текущий элемент
		list = list->next;//переходим на следующий элемент
		//free(previous);//текущий элемент 
	}
	free(list);//освобождем последний элемент	
}

List insertIn(List list, int place, Element value)
{
	List head = calloc(1, sizeof(Element));
	if (place <= 0)
	{
		head->elem = value.elem;
		head->next = list;
	}
	else
	{
		head = list;
		for (size_t i = 0; i < place - 1; i++)
		{
			if (list->next)list = list->next;
		}
		value.next = list->next;
		list->next = &value;
	}
	return head;
}

List deleteElement(List list, int place)
{
	place -= 1;//приводим к индексам
	if (place <= 0)//если 1 позиция или номер позиции меньше 0 
	{
		List head = list->next; //новое начало коллекции
		free(list);//освобождение памяти
		return(head);//ссылка на новое начало
	}
	else
	{
		List head = list;//ссылка на начало
		for (size_t i = 0; i < place - 1; i++)//идем пока не дойдем до нужного элемента
		{
			if (list->next->next)//проверка на наличие продолжение у последующего элемента есть 
			{
				if (list->next)list = list->next; //проверяем есть ли ссылка
				else break;//если ссылки нет, значит место больше количества листа и удаляем последний элемент
			}
			else break;
		}
		if (list->next->next)//проверяем есть ли какой-то элемент дальше, после удаляемого
		{
			List elem = list->next->next;//создаем ссылку на следующий после удаляемого элемент
			free(list->next);//освобождаем память
			list->next = elem;//меняем ссылку на следующий элемент
		}
		else //позиция больше нужной освобождаем последний элемент
		{
			List elem = list->next;
			list->next = NULL;
			free(elem);//освобождаем память
		}
		return(head);//возвращаем начало
	}
}

List replaceElement(List list, int place1, int place2)
{
	if (place1 > 0 && place1 < place2)
	{
		List head = list;//ссылка на начало
		int num = 0;//счетчик

		place1 -= 1;//приводим к индексам
		place2 -= 1;//приводим к индексам

		List lastElem1 = calloc(1, sizeof(Element));
		if (place1 != 0)
		{
			for (size_t i = 0; i < place1 - 1; i++)//идем до первого элемента
			{
				if (list->next)
				{
					list = list->next;
					num++;
				}
				else break;
			}
			lastElem1 = list;//запоминаем 1 предыдущий элемент
		}
		else
		{
			lastElem1 = head;
		}

		for (size_t i = num; i < place2 - 1; i++)//идем до второго элемента
		{
			if (list->next)list = list->next;
			else break;
		}
		List lastElem2 = list;//запоминаем 2 предыдущий элемент

		if (lastElem2 == lastElem1)
		{
			lastElem2 = lastElem2->next;
		}

		if (lastElem2->next && lastElem1->next)
		{
			if (place1 != 0 && lastElem1->next != lastElem2)//любой не соседний и не 1 элемент
			{
				//запоминаем элементы которыми меняемся
				List elem1 = lastElem1->next;
				List elem2 = lastElem2->next;
				//меняем ссылки на следующий элемент
				List freeEl = calloc(1, sizeof(Element));
				freeEl->next = list->next->next;
				elem2->next = elem1->next;
				elem1->next = freeEl->next;
				free(freeEl);
				//меняем ссылки предыдущих элементов на новые
				lastElem1->next = elem2;
				lastElem2->next = elem1;

				return head;//возвращаем начало
			}
			else if (lastElem1->next != lastElem2)//1 элемент с каким нибудь другим
			{
				//запоминаем элементы которыми меняемся
				List elem1 = head;
				List elem2 = lastElem2->next;
				//меняем ссылки на следующий элемент
				List freeEl = calloc(1, sizeof(Element));
				freeEl->next = list->next->next;
				elem2->next = elem1->next;
				elem1->next = freeEl->next;
				free(freeEl);
				//меняем ссылки предыдущих элементов на новые
				lastElem2->next = elem1;

				return elem2;//возвращаем новое начало
			}
			else if (place1 != 0)//соседние элементы
			{
				//запоминаем элементы которыми меняемся
				List elem1 = lastElem1->next;
				List elem2 = lastElem2->next;
				//меняем ссылки на следующий элемент
				List freeEl = calloc(1, sizeof(Element));
				freeEl->next = elem2->next;
				if (freeEl->next)elem1->next = freeEl->next;
				else return list;
				free(freeEl);
				elem2->next = elem1;

				//меняем ссылки предыдущих элементов на новые
				lastElem1->next = elem2;

				return head;//возвращаем начало
			}
			else if (place1 == 0 && place2 == 1)
			{
				List elem1 = lastElem1;
				List elem2 = lastElem2;

				head = elem2;
				elem1->next = elem2->next;
				head->next = elem1;
			}
			else//соседние элементы 1 из которых голова
			{
				//запоминаем элементы которыми меняемся
				List elem1 = head;
				List elem2 = lastElem2->next;
				//меняем ссылки на следующий элемент
				List freeEl = calloc(1, sizeof(Element));
				freeEl->next = elem2->next;
				if (freeEl->next)elem1->next = freeEl->next;
				else return list;
				elem2->next = head;
				free(freeEl);

				return elem2;//возвращаем новое начало
			}
		}
		else
		{
			return head;
		}
	}
	else return list;
}

int main()
{
	int n = 10;
	//printf("%d %d", sizeof(List), sizeof(Element));

	List newList = createList(n);//создание		
	showList(newList);//вывод на экран	

	Element elem = { 45, NULL };//создаем новый элемент
	newList = insertIn(newList, 2, elem);//добавление элемента в лист
	showList(newList);

	newList = deleteElement(newList, 1);//удаление элемента
	showList(newList);

	newList = replaceElement(newList, 1, 5);//замена элементов местами
	showList(newList);

	//1 и 2 элемент обмен
	deleteList(newList);//удаление
}