第1章第2节练习题11 就地逆置单链表
最后更新于：2022-04-01 19:51:00
## 问题描述
> 试编写在带头结点的单链表就地逆置，所谓“就地”是指辅助空间为O(1)
## 算法思想1
> 将头结点摘下，然后从第一个结点开始，依次插入到头节点的后面（类似与头插法创建单链表），直到最后一个结点为止，实现了链表的逆置。如下图所示：
## 算法描述1
~~~
void RverList(LNode *head){
LNode *p=head->next;
LNode *q=p->next;
head->next=NULL;
while(p){
q=p->next;
p->next=head->next;
head->next=p;
p=q;
}
}
~~~
具体代码见附件1。
## 算法思想2
> 引用三个指针，分别为指向当前结点的指针p，指向前驱结点的指针pre，指向后继结点的指针q。首先单独摘下头节点，然后让指针p所指结点的next域指向前驱结点即可完成一次逆置过程；但是因为需要逆置整条单链表，因此将这三个指针分别后移，继续重复上一次的过程，具体如下图所示：
## 算法描述2
~~~
void RverList(LNode *head){
LNode *pre=head;
LNode *p=pre->next;
LNode *q=p->next;
p->next=NULL;
while(q){
pre=p;
p=q;
q=q->next;
p->next=pre;
}
head->next=p;
}
~~~
具体代码见附件2。
## 附件1
~~~
#include
#include
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
LinkList CreatList(LNode*);
void RverList(LNode*);
void Print(LNode*);
int main(int argc, char* argv[])
{
LNode *head;
head=(LNode*)malloc(sizeof(LNode));
head->next=NULL;
head=CreatList(head);
Print(head);
RverList(head);
Print(head);
return 0;
}
//头插法建立单链表
LinkList CreatList(LNode *head)
{
LNode *L;
ElemType x;
scanf("%d",&x);
while(x!=999){
L=(LNode*)malloc(sizeof(LNode));
L->data=x;
L->next=head->next;
head->next=L;
scanf("%d",&x);
}
return head;
}
//就地逆置单链表
void RverList(LNode *head){
LNode *p=head->next;
LNode *q=p->next;
head->next=NULL;
while(p){
q=p->next;
p->next=head->next;
head->next=p;
p=q;
}
}
//打印全部结点
void Print(LNode *head)
{
LNode *p=head->next;
while(p){
printf("%4d",p->data);
p=p->next;
}
printf("\n");
}
~~~
## 附件2
~~~
#include
#include
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
LinkList CreatList(LNode*);
void RverList(LNode*);
void Print(LNode*);
int main(int argc, char* argv[])
{
LNode *head;
head=(LNode*)malloc(sizeof(LNode));
head->next=NULL;
head=CreatList(head);
Print(head);
RverList(head);
Print(head);
return 0;
}
//头插法创建单链表
LinkList CreatList(LNode *head)
{
LNode *L;
ElemType x;
scanf("%d",&x);
while(x!=999){
L=(LNode*)malloc(sizeof(LNode));
L->data=x;
L->next=head->next;
head->next=L;
scanf("%d",&x);
}
return head;
}
//就地逆置单链表
void RverList(LNode *head){
LNode *pre=head;
LNode *p=pre->next;
LNode *q=p->next;
p->next=NULL;
while(q){
pre=p;
p=q;
q=q->next;
p->next=pre;
}
head->next=p;
}
//打印全部结点
void Print(LNode *head)
{
LNode *p=head->next;
while(p){
printf("%4d",p->data);
p=p->next;
}
printf("\n");
}
~~~
';