7-1 两个有序链表序列的合并
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。
输入格式:
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。
输出格式:
在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。
输入样例:
1 3 5 -1
2 4 6 8 10 -1
输出样例:
1 2 3 4 5 6 8 10
实现代码：
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>> st;
int main(){
int n,cnt=0;
bool flag=0;
while(cin>>n&&n!=-1){
st.push(n);
cnt++;
}
int m;
while(cin>>m&&m!=-1){
st.push(m);
cnt++;
}
if(st.size()==0) cout<<"NULL";
while(st.size()){
if(flag==0) cout<<st.top();
else cout<<" "<<st.top();
st.pop();
flag=flag+1;
}
return 0;
}
7-2 两个有序链表序列的交集
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。
输入格式:
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。
输出格式:
在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。
输入样例:
1 2 5 -1
2 4 5 8 10 -1
输出样例:
2 5
实现代码：
#include<bits/stdc++.h>
using namespace std;
vector<int> st;
vector<int> at;
int main(){
int n;
while(cin>>n&&n!=-1){
st.push_back(n);
}
int m;
while(cin>>m&&m!=-1){
at.push_back(m);
}
int i=0,j=0;
int sum=0;
while(i<st.size()&&j<at.size()){
if(st[i]==at[j]){
if(sum==0) cout<<st[i];
else cout<<" "<<st[i];
i++,j++,sum++;
}
else if(st[i]>at[j]){
j++;
}
else {
i++;
}
}
if(sum==0) cout<<"NULL";
return 0;
}
7-3 重排链表
给定一个单链表 L1→L2→⋯→Ln−1→Ln，请编写程序将链表重新排列为 Ln→L1→Ln−1→L2→⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。
输入格式：
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤105)。结点的地址是5位非负整数，NULL地址用−1表示。
接下来有N行，每行格式为：
Address Data Next
其中Address是结点地址；Data是该结点保存的数据，为不超过105的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。
输出格式：
对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例：
68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1
实现代码：
#include<bits/stdc++.h>
using namespace std;
struct Node{
int next,data;
}node[100001];
int main(){
int start_address,num,temp;
scanf("%d %d",&start_address,&num);
for(int i=0;i<num;i++){
scanf("%d",&temp);
scanf("%d %d",&node[temp].data,&node[temp].next);
}
int order[num];
order[0]=start_address;
for (int i=1;;i++){
if(node[order[i-1]].next==-1){
num=i;
break;
}
order[i]=node[order[i-1]].next;
}
int flag=-1,a=0,b=num-1;
for(int i=1;i<num;i++,flag*=-1){
if(flag==-1){
node[order[b–]].next=order[a];
}
else{
node[order[a++]].next=order[b];
}
}
node[order[a]].next=-1;
temp=order[num-1];
for(int i=1;i<num;i++){
printf("%05d %d %05d\\n",temp,node[temp].data,node[temp].next);
temp=node[temp].next;
}
printf("%05d %d %d\\n",temp,node[temp].data,node[temp].next);
return 0;
}
7-4 约瑟夫环
N个人围成一圈顺序编号，从1号开始按1、2、3……顺序报数，报p者退出圈外，其余的人再从1、2、3开始报数，报p的人再退出圈外，以此类推。 请按退出顺序输出每个退出人的原序号。
输入格式:
输入只有一行，包括一个整数N(1<=N<=3000)及一个整数p(1<=p<=5000)。
输出格式:
按退出顺序输出每个退出人的原序号，数据间以一个空格分隔，但行尾无空格。
输入样例:
在这里给出一组输入。例如：
7 3
输出样例:
3 6 2 7 5 1 4
实现代码：
#include<bits/stdc++.h>
using namespace std;
queue<int> st;
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
st.push(i);
}
int fa=0;
while(st.size()){
for(int i=1;i<=m;i++){
if(i<m){
int t=st.front();
st.pop();
st.push(t);
}
if(i==m){
int t=st.front();
st.pop();
if(fa==0){
cout<<t;
fa++;
}
else{
cout<<" "<<t;
}
}
}
}
return 0;
}
7-5 单链表的创建及遍历
读入n值及n个整数，建立单链表并遍历输出。
输入格式:
读入n及n个整数。
输出格式:
输出n个整数，以空格分隔（最后一个数的后面没有空格）。
输入样例:
在这里给出一组输入。例如：
2
10 5
输出样例:
在这里给出相应的输出。例如：
10 5
实现代码：
#include<bits/stdc++.h>
using namespace std;
queue<int> s;
int main(){
int n,m;
bool flag=0;
cin>>n;
for(int i=0;i<n;i++){
cin>>m;
s.push(m);
}
while(s.size()){
if(flag==0) cout<<s.front();
else cout<<" "<<s.front();
flag=flag+1;;
s.pop();
}
return 0;
}
7-6 链表去重
给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。
输入格式：
输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤105，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。
随后 N 行，每行按以下格式描述一个结点：
地址 键值 下一个结点
其中地址是该结点的地址，键值是绝对值不超过104的整数，下一个结点是下个结点的地址。
输出格式：
首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。
输入样例：
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
输出样例：
00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1
实现代码：
#include<bits/stdc++.h>
using namespace std;
int start,n;
const int N=1e5+10;
int fir[N],sec[N],rep[N];
struct node{
int data,next;
}a[N];
int main(){
cin>>start>>n;
while(n–){
int q,w,e;
cin>>q>>w>>e;
a[q].data=w;
a[q].next=e;
}
int len1=0,len2=0;
for(int i=start;i>-1;i=a[i].next){
int data=fabs(a[i].data);
if(rep[data]==0){
rep[data]=1;
fir[len1++]=i;
}
else{
sec[len2++]=i;
}
}
for(int i=0;i<len1;i++){
printf("%05d %d ",fir[i],a[fir[i]].data);
if(i==len1-1) cout<<"-1"<<endl;
else printf("%05d\\n",fir[i+1]);
}
for(int i=0;i<len2;i++){
printf("%05d %d ",sec[i],a[sec[i]].data);
if(i==len2-1) cout<<"-1"<<endl;
else printf("%05d\\n",sec[i+1]);
}
return 0;
}
7-7 单链表就地逆置
输入多个整数，以-1作为结束标志，顺序建立一个带头结点的单链表，之后对该单链表进行就地逆置（不增加新结点），并输出逆置后的单链表数据。
输入格式:
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试输入多个整数，以-1作为该组测试的结束（-1不处理）。
输出格式:
对于每组测试，输出逆置后的单链表数据（数据之间留一个空格）。
输入样例:
1
1 2 3 4 5 -1
输出样例:
5 4 3 2 1
实现代码：
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
int data;
struct node *next;
}lnode;
lnode *created(){
lnode *head,*p,*tail;
int n;
head=(node*)malloc(sizeof(lnode));
head->next=NULL;
tail=head;
while(scanf("%d",&n)!=EOF&&n!=-1){
p=(node*)malloc(sizeof(lnode));
p->data=n;
tail->next=p;
tail=p;
p->next=NULL;
}
return head;
}
void nizhi(lnode *head){
struct node *p,*q;
p=head->next;
head->next=NULL;
q=p->next;
while(p){
p->next=head->next;
head->next=p;
p=q;
if(q)
q=q->next;
}
}
void shuchu(lnode *head){
lnode *p;
p=head->next;
if(!p)cout<<"NULL";
while(p){
cout<<p->data;
if(!p->next)
cout<<"\\n";
else cout<<" ";
p=p->next;
}
}
int main(){
int t;
lnode *head;
cin>>t;
for(int i=0;i<t;i++){
head=created();
nizhi(head);
shuchu(head);
}
return 0;
}
7-8 带头节点的双向循环链表操作
本题目要求读入一系列整数，依次插入到双向循环链表的头部和尾部，然后顺序和逆序输出链表。
链表节点类型可以定义为
typedef int DataType;
typedef struct LinkedNode{
DataType data;
struct LinkedNode *prev;
struct LinkedNode *next;
}LinkedNode;
链表类型可以定义为
typedef struct LinkedList{
int length; /* 链表的长度 */
LinkedNode head; /* 双向循环链表的头节点 */
}LinkedList;
初始化链表的函数可声明为
void init_list(LinkedList *list);
分配节点的函数可声明为
LinkedNode *alloc_node(DataType data);
头部插入的函数可声明为
void push_front(LinkedList *list, DataType data);
尾部插入的函数可声明为
void push_back(LinkedList *list, DataType data);
顺序遍历的函数可声明为
void traverse(LinkedList *list);
逆序遍历的函数可声明为
void traverse_back(LinkedList *list);
输入格式:
输入一行整数（空格分隔），以-1结束。
输出格式:
第一行输出链表顺序遍历的结果，第二行输出逆序遍历的结果。
输入样例:
在这里给出一组输入。例如：
1 2 3 4 5 6 -1
输出样例:
5 3 1 2 4 6
6 4 2 1 3 5
实现代码：
#include<bits/stdc++.h>
using namespace std;
vector<int>a,b;
int main(){
int x,i;
while(cin>>x,x!=-1)
a.push_back(x);
for(i=a.size()-1;i>=0;i–)
if(i%2==0){
cout<<a[i]<<" ";
b.push_back(a[i]);
}
for(i=0;i<a.size();i++){
if(i%2!=0){
cout<<a[i];
b.push_back(a[i]);
if(a.size()%2==0){
if(i!=a.size()-1)
cout<<" ";
else
cout<<endl;
}
else{
if(i!=a.size()-2)
cout<<" ";
else
cout<<endl;
}
}
}
for(i=b.size()-1;i>=0;i–){
cout<<b[i];
if(i!=0)
cout<<" ";
else
cout<<endl;
}
return 0;
}
7-9 头插法创建单链表、遍历链表、删除链表
输入一系列自然数（0和正整数），输入-1时表示输入结束。按照输入的顺序，用头插法建立单链表，并遍历所建立的单链表，输出这些数据。注意 -1 不加入链表。
输入格式:
第一行是一个正整数k，表示以下会有k组测试数据。
每组测试数据是一系列以空格隔开的自然数（0和正整数）。数列末尾的 -1 表示本组测试数据结束。按照输入的顺序，用头插法建立单链表，并遍历所建立的单链表，输出这些数据。注意 -1 不加入链表。
输出格式:
对于每组测试数据，输出链表中各节点的数据域。每个数据后有一个空格。每组测试数据的输出占1行。
输入样例:
3
1 2 3 4 5 -1
30 20 10 -1
4 2 2 1 1 2 0 2 -1
输出样例:
在这里给出相应的输出。例如：
5 4 3 2 1
10 20 30
2 0 2 1 1 2 2 4
注意：对每组测试数据，创建链表，遍历链表输出之后，一定要删除链表，否则会出现“内存超限”。
实现代码：
#include<bits/stdc++.h>
using namespace std;
int n;
stack<int> st;
int main(){
cin>>n;
while(n–){
int a;
while(cin>>a&&a!=-1){
st.push(a);
}
while(st.size()){
int t=st.top();
st.pop();
cout<<t<<" ";
}
cout<<endl;
}
return 0;
}
