考研数据结构练习-19真题41
单链表操作
#include<bits/stdc++.h>
using namespace std;
typedef struct LNode{
int data;
struct LNode *next;
}LNode, *LinkList;
LinkList init(LinkList &L, int n){ // 头插法
LNode *s;
L = (LinkList)malloc(sizeof(LNode));
L -> next = NULL;
for(int i = n; i >= 1; i -- ){
s = (LNode *)malloc(sizeof(LNode));
s -> data = i;
s -> next = L -> next;
L -> next = s;
}
return L;
}
void show(LinkList L){
LNode *p = L -> next;
while(p != NULL){
cout << p -> data << " ";
p = p -> next;
}
cout << endl;
}
void change(LinkList L){
LNode *p, *q, *r, *s;
p = q = L;
while(q -> next != NULL){ // 找mid
p = p -> next;
q = q -> next;
if(q -> next != NULL) q = q -> next;
}
//逆序
q = p -> next;
p -> next = NULL;
while(q != NULL){
r = q -> next;
q -> next = p -> next;
p -> next = q;
q = r;
}
// 插入
q = p -> next;
p -> next = NULL;
s = L -> next;
while(q != NULL){
r = s -> next;
s -> next = q;
q = q -> next;
s = s -> next;
s -> next = r;
s = r;
}
}
int main(){
int n;
cin >> n;
LinkList h;
init(h, n);
show(h);
cout << "变化后" << endl;
change(h);
show(h);
return 0;
}