单链表的若干问题
（1）.试编写算法将带头结点单链表就地逆置，所谓“就地”是指辅助空间为O(1)
【解析】
此问题有两种解法。
a 把头节点摘下来，然后用头插法建链表就形成所谓的就地逆置
b 依次遍历将指针反转，不过最后一个节点需要注意一下
两算法时间复杂度都是O(n)，空间都是O(1)
【算法】
第一种算法：
#include<stdio.h>#include<malloc.h>typedef struct Node{int data;struct Node *next;}LinkList;//就地反转int LinkListRerverse(LinkList *head){LinkList *q,*p;p = head->next;head->next = NULL;while(p != NULL){q = p->next;p->next = head->next;head->next = p;p = q;}return 0;}//输出数据int LinkListPrintf(LinkList *head){LinkList *p;p = head;while(p->next){p = p->next;printf("%d ",p->data);}printf("\n");return 0;}//创建链表int LinkListCreate(LinkList *head,int n){LinkList *p,*newNode;head->next = NULL;p = head;//输入数据for(int i = 0;i < n;i++){//创建节点newNode = (LinkList*)malloc(sizeof(LinkList));scanf("%d",&newNode->data);newNode->next = p->next;p->next = newNode;p = newNode;}return 0;}int main(){int n;while(scanf("%d",&n) != EOF){LinkList *head;head = (LinkList*)malloc(sizeof(LinkList));//创建链表(n个节点)LinkListCreate(head,n);//输出已建链表LinkListPrintf(head);//就地反转LinkListRerverse(head);//输出反转后结果LinkListPrintf(head);}return 0;}