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

//初始定义链表的长度
#define SIZE 5  

//定义节点
typedef struct Node
{
	int data;
	struct Node * pNext;
}NODE, * PNODE;

//定义栈
typedef struct Stack
{
	int * base; //栈空间基址
	int * top;  //指向栈顶有效元素的下一个位置
}Stack;


void traversing_linklist(PNODE pHead);   //遍历链表
void reverseTrans_reverse(PNODE pHead);   //反转链表
void reverseTrans_stack(PNODE pHead);  //用栈反向输出链表
Stack creat_stack();   //创建栈
void stack_push(Stack &s, int val);   //元素入栈
  
int main(void)
{
	int i, val;

	//创建链表
	//malloc 分配一个给NODE结构体分配一个空间，pHead 指向这个地址空间
	//pTail也指向这个空间，因为pTail没有其他地方去了，先收留在这个地址空间
	//这个时候，这个链表只有一个元素
	PNODE pHead = (PNODE)malloc(sizeof(NODE));  //头结点
	PNODE pTail = pHead;    //尾节点
	PNODE pNew;  //新节点

	printf("创建链表的长度为：SIZE = %d\n", SIZE);

	for(i = 0; i < SIZE; i++)
	{
		printf("输入第%d个元素：", i+1);
		scanf("%d", &val);

		//创建新节点
		//创建一个新的空间，pNew是个指针，指向这个新的空间位置
		pNew = (PNODE)malloc(sizeof(NODE));
		pNew->data = val;//空间里面有一个变量专门用来存值的。先把这个值存下来。
		pNew->pNext = NULL;//因为是最新的空间地址，这个内存的pNext指针是空的

		//新节点添加在尾节点后面
		//之前的那个尾部的指针是指向的是第1个位置的，pTail->pNext是空的
		//现在有了第二个位置，所以pTail->pNext就指向第二个位置了，也就是pNew
		//pNext是把1和2 粘合起来，pTail是最后的那个空间
		pTail->pNext = pNew;
		pTail = pNew;
	}

	//遍历链表
	traversing_linklist(pHead);

	//反向遍历链表， 从头到尾节点入栈，然后再出栈
	printf("用栈，反向输出链表:");
	reverseTrans_stack(pHead);

	//反向遍历链表，反转链表
	printf("反转链表:");
	reverseTrans_reverse(pHead);

	return 0;
}

void traversing_linklist(PNODE pHead)
{
	printf("遍历链表：");
	PNODE p = pHead->pNext;

	//从pHead开始，依次检查pHead->pNext指针是否为空
	while(p != NULL)
	{
		printf("%d ", p->data);
		p = p->pNext;
	}

	printf("\n");
}

//反转链表，并遍历
//比较核心，，装逼解析开始
void reverseTrans_reverse(PNODE pHead)
{
	//反向链表的头结点
	PNODE pRever = (PNODE)malloc(sizeof(NODE));
	pRever->pNext = NULL;

	//先指向pHead->pNext
	PNODE p = pHead->pNext;

	//两个临时变量
	PNODE pMid = NULL;  
	PNODE pTail;

	while(p != NULL)
	{
		//刚开始pTail = mid = NULL
		pTail = pMid;
		//pMid移动到p的位置，把pTail留在原来的位置
		pMid = p;
		//p就跑了，让pMid在原来的房子，自己跑到下一个房子去了
		p = p->pNext;
		//这个是关键，pMid->pNext 的指向重新赋值，指向上面的尾部pTail
		//原来是这样子的1->2->3->4->5  ->NULL变成了NULL<-  1<-2<-3<-4<-5
		pMid->pNext = pTail;
	}

	//再把这个鸡头放上去就完美了
	pRever->pNext = pMid;

	//遍历链表
	traversing_linklist(pRever);

}

//根据栈，反向输出链表
void reverseTrans_stack(PNODE pHead)	
{
	int val;
	Stack s = creat_stack();  //创建栈

	PNODE p = pHead->pNext;
	while(p != NULL)
	{
		stack_push(s, p->data); //节点从头到尾如入栈
		p = p->pNext;
	}

	while(s.top != s.base)  //元素再出栈
	{
		s.top --;
		val = *(s.top);
		printf("%d ", val);
	}
	printf("\n");

}

//创建栈
Stack creat_stack()
{
	Stack s;
	//申请一块区域，把s.base 和s.top都指向这个首地址
	s.base = (int *)malloc(sizeof(int) * SIZE); //分配栈空间
	s.top = s.base;
	return s;
}

//元素入栈
void stack_push(Stack &s, int val)
{
	if((s.top - s.base) > SIZE)
	{
		printf("栈满！");
		return;
	}
	else
	{
		*(s.top) = val;
		s.top ++;
	}
}

//反转链表，并遍历
//比较核心，，装逼解析开始
void reverseTrans_reverse(PNODE pHead)
{
	//反向链表的头结点
	PNODE pRever = (PNODE)malloc(sizeof(NODE));
	pRever->pNext = NULL;

	//先指向pHead->pNext
	PNODE p = pHead->pNext;

	//两个临时变量
	PNODE pMid = NULL;  
	PNODE pTail;

	while(p != NULL)
	{
		//刚开始pTail = mid = NULL
		pTail = pMid;
		//pMid移动到p的位置，把pTail留在原来的位置
		pMid = p;
		//p就跑了，让pMid在原来的房子，自己跑到下一个房子去了
		p = p->pNext;
		//这个是关键，pMid->pNext 的指向重新赋值，指向上面的尾部pTail
		//原来是这样子的1->2->3->4->5  ->NULL变成了NULL<-  1<-2<-3<-4<-5
		pMid->pNext = pTail;
	}

	//再把这个鸡头放上去就完美了
	pRever->pNext = pMid;

	//遍历链表
	traversing_linklist(pRever);

}