动态存贮【描述】创建 n 个节点的单向链表按顺序存储 1~n 。请用动态分配内存的方式创建节点。遍历输出每个节点的值。【输入格式】一个正整数n【输出格式】输出单向链表每个节点的值数值之间用空格隔开。【输入样例】10【输出样例】1 2 3 4 5 6 7 8 9#includeiostreamusingnamespacestd;structnode{intdata;// 数据node*next;// 指向后继节点的指针};intmain(){intn;cinn;// 1、创建第一个节点头指针指向这个节点node*headnewnode;// 动态分配内存head-data1;//新结点的数据head-nextNULL;//初始化指针// 2、插入值为2~n的新节点(在尾部插入)inti2;node*phead;// 新节点总是插入p后一个位置for(inti2;in;i){// 分配新结点snode*snewnode;s-datai;// 新结点存储数字is-nextNULL;//初始化指针// 把s插入p后面p-nexts;// p后移1pp-next;}// 3、正序遍历输出phead;//p指向头节点while(p!NULL){coutp-data ;pp-next;// 指向后继节点}coutendl;return0;}/* 【输入用例2】 1 【输出用例2】 1 【输入用例3】 3 【输出用例3】 1 2 【输入用例4】 5 【输出用例4】 1 2 3 4 【输入用例5】 20 【输出用例5】 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 【输入用例6】 99 【输出用例6】 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 */双向链表创建【描述】创建一个包含整数的双向链表自定义输入双向链表的元素个数与元素输出最后的循环链表元素。【输入描述】输入为两行第一行表示元素个数n其中n0,第二行表示n个元素【输出描述】输出最后的循环链表元素【样例输入】51 2 3 4 5【样例输出】循环链表元素: 1 2 3 4 5#includeiostreamusingnamespacestd;// 定义循环链表的节点结构体structNode{intdata;Node*next;};// 功能根据给定数组创建循环链表// 参数arr - 存储数据的整型数组n - 数组的大小节点数量// 返回值循环链表的头节点指针若n0则返回nullptrNode*createCircularList(intarr[],intn){if(n0)returnnullptr;// 处理空数组情况无节点时返回空指针// 创建头节点数据为数组第一个元素next初始化为空Node*headnewNode{arr[0],nullptr};Node*tailhead;// 尾指针初始指向头节点后续会移动到最后一个节点// 从数组第二个元素开始依次创建新节点并连接到链表尾部for(inti1;in;i){tail-nextnewNode{arr[i],nullptr};// 创建新节点数据为当前数组元素next暂为空tailtail-next;// 尾指针移动到新节点成为新的尾节点}tail-nexthead;// 关键操作将尾节点的next指向头节点形成循环链表returnhead;// 返回链表的头节点}// 功能遍历循环链表并输出所有节点的数据// 参数head - 循环链表的头节点指针voidtraverseCircular(Node*head){if(!head)return;// 空链表直接返回无节点可遍历Node*phead;// 定义游标指针p初始指向头节点do{coutp-data ;// 输出当前节点的数据pp-next;// 游标指针移动到下一个节点}while(p!head);// 循环终止条件游标回到头节点确保遍历完整个环coutendl;// 输出换行符格式化显示}intmain(){intn;cinn;// 输入数组的大小即循环链表的节点数量int*arrnewint[n];// 动态分配数组内存存储用户输入的数值for(inti0;in;i){// 循环读取n个整数存入数组cinarr[i];}Node*listcreateCircularList(arr,n);// 调用函数创建循环链表cout循环链表元素: ;traverseCircular(list);// 调用函数遍历并输出循环链表的所有元素return0;}/* 【输入用例2】 1 5 【输出用例2】 循环链表元素: 5 【输入用例3】 3 10 20 30 【输出用例3】 循环链表元素: 10 20 30 【输入用例4】 8 1 2 3 4 5 6 7 8 【输出用例4】 循环链表元素: 1 2 3 4 5 6 7 8 【输入用例5】 0 【输出用例5】 循环链表元素: 【输入用例6】 6 9 8 7 6 5 4 【输出用例6】 循环链表元素: 9 8 7 6 5 4 */合并循环链表【描述】将两个升序循环链表合并为新的循环链表然后将循环链表输出。【输入描述】输入为四行第一行代表第一个链表输入元素的个数n1第二行输入n1个元素第三行代表第二个链表输入元素的个数n2第四行输入n2个元素n1与n2均大于0【输出描述】输出合并后的链表元素按照元素大小顺序排列【样例输入】51 2 3 4 531 2 3【样例输出】合并后的循环链表: 1 1 2 2 3 3 4 5#includeiostreamusingnamespacestd;// 定义循环链表节点结构体不使用头节点structNode{intdata;Node*next;Node(intval):data(val),next(nullptr){}};// 合并两个有序循环链表的函数Node*mergeCircularLists(Node*list1,Node*list2){if(!list1)returnlist2;if(!list2)returnlist1;// 找到list1和list2的尾节点Node*tail1list1;while(tail1-next!list1){tail1tail1-next;}Node*tail2list2;while(tail2-next!list2){tail2tail2-next;}// 断开循环形成两个有序的非循环链表tail1-nextnullptr;tail2-nextnullptr;// 创建一个新的头节点Node*newHeadnewNode(-1);// 哨兵节点Node*tailnewHead;Node*plist1;Node*qlist2;// 合并过程while(pq){if(p-dataq-data){tail-nextp;pp-next;}else{tail-nextq;qq-next;}tailtail-next;}// 处理剩余节点if(p){tail-nextp;}else{tail-nextq;}// 找到新链表的尾节点Node*newTailtail;while(newTail-next){newTailnewTail-next;}// 形成新的循环链表newTail-nextnewHead-next;// 删除哨兵节点Node*tempnewHead;newHeadnewHead-next;deletetemp;returnnewHead;// 返回新循环链表的头节点}// 创建循环链表不使用头节点Node*createCircularList(intarr[],intn){if(n0)returnnullptr;Node*headnewNode(arr[0]);Node*tailhead;for(inti1;in;i){tail-nextnewNode(arr[i]);tailtail-next;}tail-nexthead;// 形成循环returnhead;}// 打印循环链表voidprintCircularList(Node*head){if(!head)return;Node*phead;do{coutp-data ;pp-next;}while(p!head);coutendl;}// 手动输入数组并创建循环链表Node*createCircularListFromInput(intn){if(n0)returnnullptr;int*arrnewint[n];for(inti0;in;i){cinarr[i];}Node*headcreateCircularList(arr,n);delete[]arr;// 释放临时数组内存returnhead;}intmain(){intn1,n2;// 输入第一个链表cinn1;Node*list1createCircularListFromInput(n1);// 输入第二个链表cinn2;Node*list2createCircularListFromInput(n2);// 合并并打印结果Node*mergedmergeCircularLists(list1,list2);cout合并后的循环链表: ;printCircularList(merged);return0;}/* 【输入用例2】 1 1 1 2 【输出用例2】 合并后的循环链表: 1 2 【输入用例3】 3 1 3 5 2 2 4 【输出用例3】 合并后的循环链表: 1 2 3 4 5 【输入用例4】 2 1 2 2 3 4 【输出用例4】 合并后的循环链表: 1 2 3 4 【输入用例5】 0 3 10 20 30 【输出用例5】 合并后的循环链表: 10 20 30 【输入用例6】 4 5 10 15 20 3 6 12 18 【输出用例6】 合并后的循环链表: 5 6 10 12 15 18 20 */约瑟夫环问题【描述】约瑟夫环问题是一个经典的数学问题描述如下N个人围成一圈从某个指定的人开始报数数到K的那个人就被淘汰接着下一个人重新从1开始报数直到所有人都被淘汰。请你用链表相关知识求最后一个幸存者的初始位置。【输入描述】输入两个数n与m其中n表示人数m表示间隔【输出描述】输出最后剩下的人号码【样例输入】10 2【样例输出】最后剩下的人是: 5#includeiostreamusingnamespacestd;// 定义循环链表节点结构体structNode{intdata;Node*next;Node(intval):data(val),next(nullptr){}};// 创建循环链表Node*createCircularList(intn){if(n0)returnnullptr;Node*headnewNode(1);// 创建头节点Node*tailhead;for(inti2;in;i){tail-nextnewNode(i);tailtail-next;}tail-nexthead;// 尾节点指向头节点形成环returnhead;}// 约瑟夫环问题求解函数intjosephus(Node*head,intm){if(!head)return-1;// 空链表直接返回-1Node*phead;// 找到尾节点用于判断循环结束Node*tailhead;while(tail-next!head){tailtail-next;}// 模拟淘汰过程while(p-next!p){// 当链表中只剩一个节点时结束// 移动m-1步找到要淘汰的节点for(inti1;im;i){pp-next;tailtail-next;// 尾节点同步移动}// 淘汰当前节点Node*tmpp-next;p-datatmp-data;// 用下一个节点的数据覆盖当前节点p-nexttmp-next;// 跳过下一个节点deletetmp;// 释放被淘汰节点的内存// 如果淘汰的是尾节点需要更新尾节点if(tmptail){tailp;}}intresp-data;// 最后剩下的节点数据deletep;// 释放最后一个节点returnres;}// 打印循环链表用于调试voidprintCircularList(Node*head){if(!head)return;Node*phead-next;while(p!head){coutp-data ;pp-next;}coutendl;}intmain(){intn,m;cinnm;//输入人数n和间隔m// 创建循环链表Node*listcreateCircularList(n);// 求解约瑟夫环问题intlastPersonjosephus(list,m);cout最后剩下的人是: lastPersonendl;return0;}/* 【输入用例2】 1 1 【输出用例2】 最后剩下的人是: 1 【输入用例3】 5 2 【输出用例3】 最后剩下的人是: 3 【输入用例4】 7 3 【输出用例4】 最后剩下的人是: 4 【输入用例5】 10 1 【输出用例5】 最后剩下的人是: 10 【输入用例6】 6 4 【输出用例6】 最后剩下的人是: 5 */删除双向链表倒数第k个节点【描述】自定义设计一个程序将双向链表中某一个元素删除后然后将该链表元素正向、反向输出。【输入描述】输入分三行第一行表示输入双向链表的元素个数n,n0第二行输入n个整数用空格分隔第三行输入要删除的倒数第k个节点的k值【输出描述】分别输出删除后的正向与反向的链表元素【样例输入1】51 2 3 4 52【样例输出1】正向: 1 2 3 5反向: 5 3 2 1【样例输入2】51 2 3 4 56【样例输出2】k值超过链表长度无法删除正向: 1 2 3 4 5反向: 5 4 3 2 1#includeiostreamusingnamespacestd;// 定义双向链表节点结构体structDNode{intdata;DNode*prev;DNode*next;DNode(intval):data(val),prev(nullptr),next(nullptr){}};// 删除双向链表倒数第k个节点的函数voiddeleteKthFromEnd(DNode*head,intk){if(!head||k0)return;// 处理空链表或无效k值DNode*fasthead-next;// 从第一个实际节点开始DNode*slowhead-next;DNode*tailhead-prev;// 获取尾节点// 快指针先走k步for(inti0;ik;i){fastfast-next;if(fasthead){// k超过链表长度coutk值超过链表长度无法删除endl;return;}}// 同时移动快慢指针直到快指针回到头节点while(fast!head){fastfast-next;slowslow-next;}// 删除slow节点if(slowhead-next){// 如果要删除的是第一个实际节点head-nextslow-next;slow-next-prevhead;}elseif(slowtail){// 如果要删除的是最后一个节点tailslow-prev;tail-nexthead;head-prevtail;}else{// 删除中间节点slow-prev-nextslow-next;slow-next-prevslow-prev;}deleteslow;// 释放被删除节点的内存}// 创建双向链表带头节点DNode*createDoublyList(intarr[],intn){if(n0)returnnullptr;DNode*headnewDNode(-1);// 哨兵节点DNode*tailhead;for(inti0;in;i){DNode*newNodenewDNode(arr[i]);tail-nextnewNode;newNode-prevtail;tailnewNode;}tail-nexthead;// 形成循环head-prevtail;// 头节点指向尾节点returnhead;}// 手动输入创建双向链表DNode*createDoublyListFromInput(){intn;cinn;//输入双向链表的元素个数DNode*headnewDNode(-1);// 哨兵节点DNode*tailhead;for(inti0;in;i)//输入 n 个整数用空格分隔{intval;cinval;DNode*newNodenewDNode(val);tail-nextnewNode;newNode-prevtail;tailnewNode;}tail-nexthead;// 形成循环head-prevtail;// 头节点指向尾节点returnhead;}// 打印双向链表从前往后voidprintForward(DNode*head){if(!head||head-nexthead){// 空链表或只有哨兵节点cout链表为空endl;return;}DNode*phead-next;cout正向: ;while(p!head){coutp-data ;pp-next;}coutendl;}// 打印双向链表从后往前voidprintBackward(DNode*head){if(!head||head-prevhead){// 空链表或只有哨兵节点cout链表为空endl;return;}DNode*phead-prev;cout反向: ;while(p!head){coutp-data ;pp-prev;}coutendl;}intmain(){// 手动输入创建双向链表DNode*listcreateDoublyListFromInput();intk;cink;//输入要删除的倒数第k个节点的k值// 删除并打印结果deleteKthFromEnd(list,k);printForward(list);printBackward(list);return0;}/* 【输入用例2】 1 10 1 【输出用例2】 k值超过链表长度无法删除 正向: 10 反向: 10 【输入用例3】 3 1 2 3 1 【输出用例3】 正向: 1 2 反向: 2 1 【输入用例4】 4 10 20 30 40 2 【输出用例4】 正向: 10 20 40 反向: 40 20 10 【输入用例5】 5 5 4 3 2 1 5 【输出用例5】 k值超过链表长度无法删除 正向: 5 4 3 2 1 反向: 1 2 3 4 5 【输入用例6】 3 7 8 9 5 【输出用例6】 k值超过链表长度无法删除 正向: 7 8 9 反向: 9 8 7 */