//真题：将带头节点的链表逆置，不能占用额外的空间。
#include "stdio.h"
#include<stdlib.h>
typedef struct Node{ //结构体
int data;
Node *next;
}Node;
void init(Node *&p){ //初始化
p->next = NULL;
}
void listCreate(Node *&p,int n){ //参数：头节点，数据
Node *q = (Node *)malloc(sizeof(Node));
//****头插法建立（插入）链表*********(后进先出)
q->data = n;
q->next = p->next;
p->next = q;
//****************
}
void Traversal(Node *&p){ //遍历
Node *q = p->next;
while (q != NULL)
{
printf("%d ",q->data);
q = q->next;
}
}
//思路：让q=p；p每前进一个节点，就让q等于p，然后将这个节点插入到头节点之后
//p在前面跑，q紧跟其后，将q放到头节点的后面
void reverse(Node *&h)//将原链表就地倒置
{
Node *p = h->next;
Node *q;
h->next = NULL; //把头节点和后面的链表割裂
while (p != NULL)
{
q = p;
p = p->next;
q->next = h->next;
h->next = q;
}
}
int main(){
Node *head = (Node *)malloc(sizeof(Node));
init(head);
for(int i=0;i<5;i++){
listCreate(head,i);
}
//reverse5(head);
Traversal(head);
//printf("%d",head->data);
getchar();
return 0;
}