2020考研数据结构之单链表

编写算法将带头结点的单链表就地逆置，所谓“就地”逆置就是空间复杂度为O(1)

---

---

画图说明：

 

---

完成了从123到213，往后照此操作即完成了头插法倒序

---

代码：

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct LNode{
	ElemType data;
	struct  LNode * next;
}LNode ,*LinkList;
/*编写算法将带头结点的单链表就地逆置，所谓“就地”逆置就是空间复杂度为O(1)*/
LinkList reverse(LinkList &L){
	LNode *p,*r;
	p=L->next;
	L->next=NULL; 
	while(p!=NULL){
		r=p->next;
		p->next=L->next;
		L->next=p;
		p=r;
	}
	return L; 
}
LinkList createLinkListStern(LinkList &L){
	ElemType x,n;
	L=(LinkList)malloc(sizeof(LNode));
	if(L==NULL){
		printf("内存分配失败");
	 
	}
	L->next=NULL;
	printf("输入单链表的长度:");
	scanf("%d",&n);
	LNode *s,*r=L;//r指向尾指针  
	for(int i=0;i<n;i++){
		printf("输入第%d个元素:",(i+1));
		scanf("%d",&x);
		s=(LinkList)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;
		r= s;
	}
	r->next=NULL; 
	return L;	
} 
/*
	遍历展示单链表的值 
*/
void display(LinkList &L){
	LinkList p;
	printf("输出单链表元素:\n");
	for(p=L->next;p!=NULL;p=p->next){
		int i=1;
		printf("第%d个元素为%d\n",i++,p->data); 
	}
} 
int main(){
	LNode *L;
	createLinkListStern(L);
	display(L);
	reverse(L);
	display(L); 
	return 0;
}

截图：