單連結清單逆轉（含頭結點）

// 字串查找.cpp : 定義控制台應用程式的入口點。
//單連結清單
#include "stdafx.h"
#include <iostream>
#include <complex>
using namespace std;

typedef struct node {
	int data;//節點内容
	node *next;//下一個節點
}node;

//建立單連結清單
node *create(){
	node *head,*p,*q;
	int i=0; //單連結清單中資料的個數
	int a=-1;
	head=new node;//建立頭節點
	head->next=NULL;
	while (1)
	{
		cout<<"please input the data(input -1,quit):";
		cin>>a;
		if (-1==a) //如果輸入的是-1，退出
		{
			break;
		}
		p=new node;
		p->data=a;
		p->next=NULL;//連結清單的最後一個指針為NULL
		if (++i==1) //連結清單隻有一個元素
		{           //連接配接到head的後面
			head->next=p;
		}
		else{
			q->next=p;//連接配接到連結清單尾端
		}
		q=p;//q指向末節點
	}
	return head;
}


//列印單連結清單
void print(node *head){
	node *p=head->next;
	int index=0;
	if (p==NULL)//連結清單為NULL
	{
		cout<<"Link is empty!"<<endl;
		getchar();
		return;
	}
	while (p!=NULL)//周遊連結清單
	{
		cout<<"The "<<++index<<"th node is :"<<p->data<<endl;//列印元素
		p=p->next;
	}
}

//單連結清單逆置
node *reverse(node *head){
	node *p,*q,*r;
	if (head->next==NULL)//連結清單為空
	{
		return head;
	}
	p=head->next;
	q=p->next;//儲存原第2個節點
	p->next=NULL;//原第1個節點為末節點
	while (q!=NULL)//周遊，各個節點的next指針反轉
	{
		r=q->next;
		q->next=p;
		p=q;
		q=r;
	}
	head->next=p;//新的第一個節點為原末節點
	return head;
}
int _tmain(int argc, _TCHAR* argv[])
{
	node *head=create();//建立單連結清單
	node *preverse=reverse(head);
	print(preverse);
	system("pause");
	delete [] head;
	return 0;
}