问题描述
试编写在带头结点的单链表就地逆置,所谓“就地”是指辅助空间为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<stdio.h>
#include<stdlib.h>
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<stdio.h>
#include<stdlib.h>
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");
}