目录

题目

思路

代码

数据结构

头插法

尾插逆置法

STL

题目

题目描述

建立长度为n的单链表，然后将其数据元素逆置，即第1个元素变为最后一个元素，第2个元素变为倒数第2个元素，以此类推，最后一个元素变为第1个元素。（处理的数据类型为字符型。必须使用链表完成。）

 输入

第一行为链表长度n； 第二行为链表中的n个数据元素的值。

输出

逆置后的原始的值。

 

样例输入

10
ABCDEFGHIJ

样例输出

J I H G F E D C B A

思路

这里有一种投机取巧的方式：就是直接用头插法，因为头插本就是逆置插入的。

头插介绍

//头插 
void LinklistCreate(Linklist* &L) {int n;cin>>n;Linklist *p=L;while(n--) {Linklist *q;LinklistInit(q);cin>>q->data;q->next=p->next;p->next=q;}
}

正常尾插逆置的话，可以先遍历链表，把链表每个节点的data储存在一个数组中，然后循环 建立新的节点q，让q的data逆序依次表示之前每一个节点的data。顺便尾插节点q即可

//逆置单链表
int a[10005];//储存每个节点的data
void LinklistReverse(Linklist* &L) {Linklist *p1=L;//地址p1用来遍历储存节点Linklist *p2=L;//地址p2用来逆置尾插p1=p1->next;//跳过头节点//遍历存储节点int j=0;while(p1!=NULL) {a[++j]=p1->data;p1=p1->next;}//尾插for(int i=j;i>=1;i--) {Linklist *q;LinklistInit(q);q->data=a[i];p2->next=q;p2=q;}
}

代码

链表模板

数据结构

头插法

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
//定义链表
typedef struct LNode {char data;LNode* next;
}Linklist;
// 初始化链表
void LinklistInit(Linklist* &L) {L=(Linklist*)malloc(sizeof(Linklist));L->next=NULL;
}
// //创建链表，输入数据(头插)
void LinklistCreate(Linklist* &L) {int n;cin>>n;Linklist *p=L;while(n--) {Linklist *q;LinklistInit(q);cin>>q->data;q->next=p->next;p->next=q;}
}
//输出数据，打印链表
void LinklistPrint(Linklist* &L) {L=L->next;while(L!=NULL) {cout<<L->data<<" ";L=L->next;}
}
int main() {Linklist *L;LinklistInit(L);LinklistCreate(L);LinklistPrint(L);return 0;
}

尾插逆置法

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
//定义链表
typedef struct LNode {char data;LNode* next;
}Linklist;
// 初始化链表
void LinklistInit(Linklist* &L) {L=(Linklist*)malloc(sizeof(Linklist));L->next=NULL;
}
void LinklistCreate(Linklist* &L) {Linklist *p=L;int n;cin>>n;while(n--) {Linklist *q;LinklistInit(q);cin>>q->data;p->next=q;p=q;}
}
//逆置单链表
int a[100005];
void LinklistReverse(Linklist* &L) {Linklist *p1=L;Linklist *p2=L;p1=p1->next;int j=0;while(p1!=NULL) {a[++j]=p1->data;p1=p1->next;}for(int i=j;i>=1;i--) {Linklist *q;LinklistInit(q);q->data=a[i];p2->next=q;p2=q;}
}
//输出数据，打印链表
void LinklistPrint(Linklist* &L) {L=L->next;while(L!=NULL) {cout<<L->data<<" ";L=L->next;}
}
int main() {Linklist *L;LinklistInit(L);LinklistCreate(L);LinklistReverse(L);LinklistPrint(L);return 0;
}

STL

#include <iostream>
#include <algorithm>
#include <list>
using namespace std;
list<char>a;
int main(){int n;cin>>n;char x;while(cin>>x,a.push_back(x),--n);reverse(a.begin(),a.end());list<char>::iterator it=a.begin();for(it=a.begin();it!=a.end();it++) cout<<*it<<" ";return 0;
}