Инвертировать связный список

[levandowskiy]

Доброго времени суток, уважаемые посетители форума)

Я продолжаю изучать связные списки. Хочу поблагодарить пользователя pu4koff за оказанную помощь в написании функции по заполнению списка по порядку (очень вам благодарен). Теперь передо мной стоит новая задача нужно написать функцию, принимающую список чисел и заменяющую порядок узлов обратным.
Я написал некий код. Идея его такова :
Запомнить указатель на последний элемент, как last;
1 Найти указатель на предпоследний элемент списка (назовём его i);
2 Последнему указателю, который равен NULL, присвоить значение указателя i (i->link->link = i);
3 Указателю, на который указывает i (i->link), присвоить значение NULL;
И так повторять пока i не будет равно head.;
И наконец присвоить head значение last (head = last);

Не знаю насколько рациональна эта идея, но код, который я написал по ней не работает:

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

struct INT
{
	int num;
	INT *link;
};

typedef INT* intptr;

void insert (intptr& head, intptr& last, int number);
void input (intptr& head);
void output (intptr head);
void inversion (intptr& head);

int _tmain(int argc, _TCHAR* argv[])
{
	char ans;
	int n;
	do
	{
		intptr head=NULL;
		input(head);
		inversion (head);
		output(head);

		cout<<"Continue: ";
		cin>>ans;
	} while (ans=='y'||ans=='Y');
	return 0;
}

void insert (intptr& head, intptr& last, int number)
{
	intptr temp = new INT;
	temp->num = number;
	if (!head)
	{
		head = temp;
		last = head;
		last->link = NULL;
	}
	else
	{
		last->link = temp;
		last = temp;
		last->link = NULL;
	}
}
void input (intptr& head)
{
	int n;
	cout<<"What numbers you want pop: ";
	cin>>n;
	int next;
	intptr last=NULL;
	for (int i=0; i<n; i++)
	{
		cout<<"Input number #"<<i+1<<" : ";
		cin>>next;
		insert(head,last,next);
	}
}
void output (intptr head)
{
	for (intptr i=head; i!=NULL; i=i->link)
	{
		cout<<i->num<<endl;
	}
}
void inversion (intptr& head)
{
	intptr last, temp, i;
	for (i=head; i!=NULL; i->link)
	{
		if (i->link->link==NULL)
		{
			last = i->link;
			i->link->link = i;
			i->link = NULL;
		}
	}
	do
	{
	for (i=head; i!=NULL; i->link)
	{
		if (i->link->link==NULL)
		{
			i->link->link = i;
			i->link = NULL;
		}
	}
	} while (i!=head);
	temp = head->link;
	head->link->link = head;
	head->link = NULL;
	head = last;

}

Плюс ко всему прикрепляю картинку в виде схемы, показывающую, что есть и что должно быть

Заранее благодарю за помощь)

[Sazary]

Можно проще. Достаточно менять связи по ходу движения к концу.
Возьмем три указателя a,b и c.
a указывает на второй элемент.
b - на первый, а c - на третий.
Меняем связь у a, чтобы он указывал на b.
Теперь приравниваем b к a и a к c. Таким образом сместились вправо.
Все это дело продолжается до тех пор, пока c!=NULL.
И в конце ставим делаем head->link=NULL.

#include <iostream>
#include <cstdlib>
#include <cstddef>
using namespace std;

struct INT
{
	int num;
	INT *link;
};

typedef INT* intptr;

void insert (intptr& head, intptr& last, int number);
void input (intptr& head);
void output (intptr head);
intptr inversion (intptr head);

int main()
{
	char ans;
	int n;
	do
	{
		intptr head=NULL;
		input(head);
		head = inversion (head);
		output(head);

		cout<<"Continue: ";
		cin>>ans;
	} while (ans=='y'||ans=='Y');
	return 0;
}

void insert (intptr& head, intptr& last, int number)
{
	intptr temp = new INT;
	temp->num = number;
	if (!head)
	{
		head = temp;
		last = head;
		last->link = NULL;
	}
	else
	{
		last->link = temp;
		last = temp;
		last->link = NULL;
	}
}

void input (intptr& head)
{
	int n;
	cout<<"What numbers you want pop: ";
	cin>>n;
	int next;
	intptr last=NULL;
	for (int i=0; i<n; i++)
	{
		cout<<"Input number #"<<i+1<<" : ";
		cin>>next;
		insert(head,last,next);
	}
}
void output (intptr head)
{
	for (intptr i=head; i!=NULL; i=i->link)
	{
		cout<<i->num<<endl;
	}
}


intptr inversion (intptr head)
{
intptr a, b, c;
a=head->link;
b=head;
c=head->link->link;
while(c!=NULL)
 {
  a->link=b;
  b=a;
  a=c;
  c=c->link;
 }
a->link=b;
head->link=NULL;
return a;
}

[levandowskiy]

Спасибо, Sazary)