第1章第2节练习题11 就地逆置单链表

时间:2023-02-22 21:40:15

问题描述

试编写在带头结点的单链表就地逆置,所谓“就地”是指辅助空间为O(1)

算法思想1

将头结点摘下,然后从第一个结点开始,依次插入到头节点的后面(类似与头插法创建单链表),直到最后一个结点为止,实现了链表的逆置。如下图所示:

第1章第2节练习题11 就地逆置单链表

算法描述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域指向前驱结点即可完成一次逆置过程;但是因为需要逆置整条单链表,因此将这三个指针分别后移,继续重复上一次的过程,具体如下图所示:

第1章第2节练习题11 就地逆置单链表

算法描述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");
}