2019年真题：路线图L=(A1，a2，a3，A(N-2 )，A(N-1 )，a (a (n-1 )，a (n ) ) ) ) ) ) ) 65空间重叠
typedef struct node { int data； struct node *next； } NODE； 思路分析：首先找到链表的中心节点，使用两个指针p，每次p进一步，q进两步。 当q到达链表的最后时，p正好在链表的中心节点。 将链表的后半部分当场倒置。 在单链表的前后两段依次各取一个节点，进行排序。
node*reverselist(node*head ) /翻转所有指针NODE* pre=NULL； 节点* cur=head； node * tmp=空； 记录//cur的下一个节点while (cur！=null(//记录当前节点的下一个节点tmp=cur-next； //然后将当前节点指向precur-next=pre； //pre和cur节点都前进1位，pre=cur； cur=tmp； }return pre； }voidchangelist(node*head ) {NODE *p，*q，*temp； p=q=head； //1，找到中间节点while (q-next！=null(p=p-next； q=q-next； if(q-next )！=null(//q进两步。 用if再判断一次是为了防止进一步后来到队伍的结尾，出现NULL-next异常q=q-next； (//此时p指向链表l的中心节点n/2，向下舍入。 //2，后半链表反转。 node*back=reverselist(p-next )； //反向后半部分链表，back指向后半部分链表中的第一个节点。 NODE *pre=head-next； //pre指的是前半部分链表中的第一个节点。 //3、前半部分的链表和后半部分的链表依次取一个节点。 while(e！=null}{temp=back-next； 用于back指针后，back-next=pre-next； 前下一步=后退； 预=back-next； //pre指针后返回=temp； //back指针向后移动}请务必手动模拟链表中的算法问题。 其中链表翻转部分的参考输入按钮： https://leet code-cn.com/problems/reverse-linked-list/solution/dong-Hua-Yan-Shi-2000
2018年真题：给定包含n(n=1)个整数的数组，设计一个在时间上尽可能高效的算法以找到数组中未出现的最小正整数。 例如，数组{-5、3、2、3}中未出现的最小正整数为1； 数组{ 1，2，3 }中未出现的最小正整数为4。
思路分析：基于map思想，建立数组等长mapint、int，遍历数组，生成map[i]； 再次遍历map，第一次出现的map[i]！=0时的键I输出为最小正整数。 但是，408不使用STL，所以用数组代替map。
1、创建动态数组：
堆中打开一个n*sizeof(int )大小的内存空间(因为int是32位，所以这里打开了n * 4位的存储空间)；
指针b指向此内存空间的起始地址，即数组中的第一个元素。
malloc前面的(int* )用于强制类型转换，指示此空间用于存储int类型数组。
int*b=(int* ) malloc ) n*sizeof ) int )； free(b )； void*malloc(size_tsize )； //其中size_t size参数表示动态内存分配空间的大小(以字节为单位)。 malloc的返回值是指针。 voidfree(void*ptr )； 如果不是在使用malloc )函数申请的区域之后，则需要释放此内存区域。 2、统一代入初始值。 将0代入数组b的n个元素。
memset(b，0，n*sizeof ) int )； void*memset(void*s，int v，size_t n )； //这里s可以是数组名，也可以是指向某个内在空间的指针； //v是要填充的值//n是要填充的字节数； 完整代码：
# include iostream # include string.husingnamespacestd； /*数组中未出现的最小正整数*/intfindmissmin(inta[]，int n ) (int nb=) int* ) malloc ) n*sizeof ) int )； //创建动态数组并分配存储空间memset(B，0，n*sizeof ) int )； //初始值int i； for(I=0； i n； I () if (
A[i] > 0 && A[i] < n){// 仅对数组A中的值为1~n的元素进行处理B[ A[i]- 1 ]++;}}for(i = 0; i < n; ++i) {if(B[i] == 0){break;}} free(B);return i + 1;}int main(){int a[3] = {1,2,3}, c[4] = {-5,3,2,3};cout<<"{1,2,3}中未出现的最小正整数："<<findMissMin(a, 3)<<endl; cout<<"{-5,3,2,3}中未出现的最小正整数："<<findMissMin(c, 4)<<endl;return 0;} 2010年真题（顺序表）（循环左移p位）设将n(n>1)个整数存放到一维数组R中，设计一个在时间和空间方面都尽可能高效的算法。将R中的序列循环左移p (0<p<n) 个位置，即将R中的数据由{Xo，X, …， Xn-1}变换为{Xp，Xp+1, … Xn-1, X0，X1, …，Xp-1}。
思路分析：用a表示数组的前p个元素，用b表示余下的(n-p)个元素。本题将数组ab转换为ba，则考虑对a、b分别逆置后，在对整体逆置，即可得到循环左移后的序列。(类似线代的可逆矩阵）
#include <iostream>using namespace std;#define n 10 //数组最大长度为10void Reverse(int R[], int l, int r){int i, j, temp;for(i = l, j = r; i < j; ++i, --j){temp = R[i];R[i] = R[j];R[j] = temp;}}int main(){int p = 7; //循环左移7位 int *R = (int *)malloc(sizeof(int) * n);for(int i = 0; i < n; ++i){R[i] = i + 1;} Reverse(R, 0, p-1); // 前p位逆序为：7 6 5 4 3 2 1 Reverse(R, p, n-1); //余下n-p位逆序为： 10 9 8Reverse(R, 0, n-1);// 整体逆序为：8 9 10 1 2 3 4 5 6 7 for(int i = 0; i < n; ++i){cout<<R[i]<<" ";} return 0;}效率分析：时间复杂度在于Reverse函数，为O(n)，空间复杂度O(1) 。
2011年真题（顺序表）（升序序列取中值）一个长度为L（L>=1）的升序序列S,处在第[L/2]个位置的数称为S的中位数。例如，若序列S1=(11,13,15,17,19)，则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2,4,6,8,20)，则S1和S2的中位数为11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。
思路分析：考虑归并排序中merge函数的思想，从两个升序序列的首部通过比较依次取出较小值，取出的第L个数即为整体中值。本方法的时间复杂度为O(n)，但胜在思路与代码简单，另还有较复杂的优化的O(logn)方法。
#include <iostream>using namespace std;#define n 3int findMid(int A[], int B[], int L){int i = 0, j = 0; int mid;while(i + j < L){//当i+j=L时跳出循环，取中值 if(A[i] < B[j]) {mid = A[i++];}else {mid = B[j++];}}return mid;}int main(){int A[n] = {1, 3, 5};int B[n] = {2, 4, 6};cout<<findMid(A,B,n);return 0;} 2009年真题（单链表）（查找倒数第k个数） typedef struct node{/*结点类型定义*/ElemType data;/*结点的数据域*/struct node *next;/*结点的指针域*/}LNode,*LinkList;int Search_K(LinkList L, ElemType k){//查找倒数第k个结点 LNode *p = L->next;LNode *q = L->next;while(p != NULL) {if(k > 0) k--;//p先行走k步 else q = q->next;p = p->next;}if(k > 0){//p遍历完了k仍为减到0，查找失败 return 0;}else{cout<<q->data<<endl;return 1; }}