《数据结构》单链表反转

前端之家收集整理的这篇文章主要介绍了《数据结构》单链表反转前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
单链表反转
题目描述:
/*
设计一个算法,通过一趟遍历,将链表中所有的链接方向反转,
仍利用原表的空间
*/

思想:
先将链表的头结点指针域置空,p指向链表的第一个结点;
q指向*p的后继,然后将*p插入到头结点的后面。
void TurnList(LinkList &L){
	struct LNode *p;
	p=L->next;
	L->next=NULL;
	while(p){
		struct LNode *q;
		q=p->next;//q指向*p的后继 
		p->next=L->next;
		L->next=p;//将*p插入到头结点之后 
		p=q;
	}
}

具体实现:

#include<stdio.h>
#include<iostream>
using namespace std;
#define MAX 100

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

int InitList(LinkList &L){
	L=new LNode;
	L->next=NULL;
	return 1;
}

void TraveList(LinkList L){
	struct LNode *p;
	p=L->next;
	printf("遍历链表:\n");
	while(p){
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}

//前插法创建单链表 
void CreateList(LinkList &L,int n){
	L=new LNode;
	L->next=NULL;
	for(int i=n;i>0;--i){
		printf("请输入第%d个元素的值:",i);
		struct LNode *p;
		p=new LNode;
		scanf("%d",&p->data);
		p->next=L->next;
		L->next=p;
	}
}

/*
思想:
先将链表的头结点指针域置空,p指向链表的第一个结点;
q指向*p的后继,然后将*p插入到头结点的后面。 
*/
void TurnList(LinkList &L){
	struct LNode *p;
	p=L->next;
	L->next=NULL;
	while(p){
		struct LNode *q;
		q=p->next;//q指向*p的后继 
		p->next=L->next;
		L->next=p;//将*p插入到头结点之后 
		p=q;
	}
}

int main(){
	LinkList L;
	
	if(InitList(L)){
		printf("链表初始化成功!\n");
	}else{
		printf("链表初始化失败!\n");
	}
	
	printf("请输入链表的长度:\n");
	int n;
	scanf("%d",&n);
	CreateList(L,n);
	TraveList(L);
	
	printf("反转后的链表:\n");
	TurnList(L);
	TraveList(L);
}


原文链接:https://www.f2er.com/datastructure/382547.html

猜你在找的数据结构相关文章