点击查看代码
struct ListNode*reverse(struct ListNode*head){
struct ListNode*prev = NULL;
struct ListNode*current = head;
struct ListNode*next = NULL;
while(current!= NULL){
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
线性表A,B顺序存储合并
题目:https://pintia.cn/problem-sets/1855808612225744896/exam/problems/type/7?problemSetProblemId=1855808768018968577
解答:
点击查看代码
#include <bits/stdc++.h>
#include<iostream>
using namespace std;
const int MAXSIZE = 20;
typedef int ElemType;
typedef struct arrList{
ElemType *elem;
int length;
}SqList;
void creatArrList(SqList*L){
L->elem = (ElemType *)malloc(MAXSIZE*sizeof(ElemType));
if(!L->elem){
}
L->length = 0;
}
void ListInsert(SqList * L ,int i,ElemType e){
if(L->length == MAXSIZE){
}
if(i<1||i>L->length+1){
}
if(i<=L->length){
for(int k = L->length;k>=i-1;k--){
L->elem[k+1] = L->elem[k];
}
}
L->elem[i-1]=e;
L->length++;
}
void Output(SqList&L){
for(int i = 0;i<L.length;i++){
if(i!=L.length - 1){
cout<<L.elem[i]<<",";
}else{
cout<<L.elem[i];
}
}
}
void mergeLists(SqList*La,SqList*Lb,ElemType*arr,int&totalLength){
for(int i = 0;i<La->length;i++){
arr[i]=La->elem[i];
}
for(int i = 0;i<Lb->length;i++){
arr[La->length+i] = Lb->elem[i];
}
totalLength = La->length+Lb->length;
}
int main(){
SqList La,Lb;
creatArrList(&La);
creatArrList(&Lb);
while(true){
int num;
cin>>num;
if(num== -1)break;
ListInsert(&La,La.length+1,num);
}
int lena =La.length;
while(true){
int num;
cin>>num;
if(num==-1)break;
ListInsert(&Lb,Lb.length+1,num);
}
int lenb = Lb.length;
int arr[MAXSIZE*2]={0};
int totalLength;
mergeLists(&La,&Lb,arr,totalLength);
sort(arr,arr+totalLength);
bool allsame = true;
for(int i = 1;i<totalLength;i++){
if(arr[i]!=arr[0]){
allsame = false;
break;
}
}
if(allsame){
cout<<arr[0];
}else{
int temp = -1;
for(int i = 0;i<totalLength;i++){
if(temp!=arr[i]){
cout<<arr[i];
if(i<totalLength-1){
cout<<",";
}
temp = arr[i];
}
}
}
free(La.elem);
free(Lb.elem);
}
双向循环链表应用
题目:https://pintia.cn/problem-sets/1855808612225744896/exam/problems/type/7?problemSetProblemId=1855808768018968578
解答:
点击查看代码
#include <bits/stdc++.h>
using namespace std;
// 节点结构
struct Node {
int data;
Node* prior;
Node* next;
Node(int value) : data(value), prior(nullptr), next(nullptr) {}
};
// 创建双向链表
Node* createList(const vector<int>& elements) {
if (elements.empty()) return nullptr;
Node* head = new Node(elements[0]);
Node* current = head;
for (int i = 1; i < elements.size(); i++) {
current->next = new Node(elements[i]);
current->next->prior = current;
current = current->next;
}
// 形成循环
current->next = head;
head->prior = current;
return head;
}
// 打印
void printList(Node* head) {
if (!head) return;
Node* current = head;
do {
cout << current->data;
current = current->next;
} while (current != head);
cout << endl;
}
// 交换p节点与其前驱节点
void swap(Node* p) {
if (!p || !p->prior) return;
Node* previous = p->prior;
// 数据交换
swap(p->data, previous->data);
// // 连接交换
// Node* pNext = p->next;
// Node* prevNext = previous->next;
// // 调整指针
// if (prevNext != p) {
// previous->next = pNext;
// p->next = prevNext;
// if (pNext) pNext->prior = previous;
// if (prevNext) prevNext->prior = p;
// }
// // 调整前驱指针
// previous->prior = p;
// p->prior = previous->prior;
}
// 释放内存
void freeList(Node* head) {
if (!head) return;
Node* current = head;
do {
Node* toDelete = current;
current = current->next;
delete toDelete;
} while (current != head);
}
int main() {
int n;
cin >> n;
vector<int> elements(n);
for (int& elem : elements) {
cin >> elem;
}
int num;
cin >> num;
Node* head = createList(elements);
Node* current = head;
bool found = false;
// 遍历寻找目标
do {
if (current->data == num) {
swap(current);
found = true;
break;
}
current = current->next;
} while (current != head);
if (found) {
printList(head);
} else {
cout << "未找到" << num << endl;
}
// 释放内存
freeList(head);
return 0;
}
修改数组(蓝桥杯)
题目:https://pintia.cn/problem-sets/1855808612225744896/exam/problems/type/7?problemSetProblemId=1855808768018968579
解答:
define _CRT_SECURE_NO_WARNINGS 1
include <bits/stdc++.h>
using namespace std;
const int MAX = 1000005;
int N;
int fat[MAX+1]; //并查集父节点
bool vis[MAX+1]; //判断每位数字是否出现过
//父节点查找
int find(int x) {
//在不断查找过程中压缩路径
if (fat[x] == x) return x;
else return fat[x] = find(fat[x]);
}
int main() {
//初始化
memset(vis, false, sizeof(vis));
for (int i = 1; i <= MAX; i++) {
fat[i] = i;
}
cin >> N;
int x;
for (int i = 1; i <= N; i++) {
cin >> x;
if(x > 10e6 || x < 1){
cout<<"error"<<endl;
return 0;
}
//如果数字出现过,则找到它的根节点 加 1
if (vis[x]) x = find(x) + 1;
//输出 标记
cout << x << " ";
vis[x] = true;
//判断数字前后是否连续
if (vis[x - 1] && x != 1) {
fat[x - 1] = x;
}
if (vis[x + 1]) {
fat[x] = x + 1;
}
}
return 0;
}
思路:将出现过的连续数字都构造到一棵树里,然后将每一个数的父节点直接标记为与它连续的且前面出现过的最大数,那么在之后读入数据的时候如果这个数已经出现过,就可以直接找它的父节点,将这个数修改为父节点的数字加一输出。 如:输入数据为: 2 1 6 7 5 4 5 可以获得树 1-2 与 456 - 7 此时,再读入 5 时,便可以直接找到 5 的根节点 7,再 7 + 1 = 8 ;此时,我们有两个问题: 1. 树不是直接就构造成这样的,涉及到了并查集的路径压缩 2. 如果在上述例子中再读入一个 3 ,那么两棵树就会合并,合并成一个所有元素的父节点都是 8 的样子,所以在读入元素修改过后,还要判断修改数的前后数字是否出现过,也就是看树能不能合并。 所以我们共需要 fat 和vis 两个数组来分别储存每个数的父节点以及判断数字是否出现过,之后循环查找对应x便解决。
补充:https://blog.csdn.net/qq_59700927/article/details/123075547