PAT Advanced 1074 Reversing Linked List (25) [链表]
题目
Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K = 3, then you must output 3→2→1→6→5→4; if K = 4, you must output 4→3→2→1→5→6.
Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (<= 105) which is the total number of nodes, and a positive K (<=N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by
-1.Then N lines follow, each describes a node in the format:
Address Data Next
where Address is the position of the node, Data is an integer, and Next is the position of the next node.
Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:
00100 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218
Sample Output:
00000 4 33218 33218 3 12309 12309 2 00100 00100 1 99999 99999 5 68237 68237 6 -1
题目分析
已知N个结点,以K为步长,反转链表
解题思路
- 定义结点,使用数组存储N个结点,使用order属性记录链表中结点出现序号
- 将链表分为n/k个段,对每个段进行反转
2.1 每个节点的next即为反转后的下一个结点地址
2.2 每个段最后一个节点的特殊处理:next为下一个段反转前最后一个结点
2.3 最后一个段的处理- 若n%k==0,说明n可以正好分为n/k个段,最后一个段反转,并将最后一个节点置为-1
- 若n%k!=0,说明最后一段小于k,开始下标为n/k*k,不需要反转,顺序打印,并将最后一个结点置为-1
知识点
- 将n个结点分为n/k个段,最后一段开始下标为n/k*k(下标从0开始)
- 链表反转,不一定非要对链表进行反转(即:更换每个结点next值),可以使用本题思想反向打印的办法
Code
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100010;
struct node {
int adr;
int data;
int next;
bool flag=false;//初始化为false
int order=maxn;
} nds[maxn];
bool cmp(node &n1,node &n2) {
return n1.order<n2.order;
}
int main(int argc,char *argv[]) {
int hadr,n,k,adr;
scanf("%d %d %d",&hadr,&n,&k);
for(int i=0; i<n; i++) {
scanf("%d",&adr);
scanf("%d %d",&nds[adr].data,&nds[adr].next);
nds[adr].adr=adr;
}
int count=0;
for(int i=hadr; i!=-1; i=nds[i].next) {
// nds[i].flag=true;
nds[i].order=count++;
}
sort(nds,nds+maxn,cmp);
n=count;
// for(int i=0; i<n; i++) {
// printf("%05d %05d %05d\n",nds[i].adr,nds[i].data,nds[i].next);
// }
for(int i=0; i<n/k; i++) {
for(int j=(i+1)*k-1; j>i*k; j--) {
printf("%05d %d %05d\n",nds[j].adr,nds[j].data,nds[j-1].adr);
}
printf("%05d %d",nds[i*k].adr,nds[i*k].data);
if(i<n/k-1) {
printf(" %05d\n",nds[(i+2)*k-1].adr);
} else {
if(n%k==0)printf(" -1\n"); //正好可以分为n/k块,并且打印最后一块
else {
printf(" %05d\n",nds[(i+1)*k].adr);
for(int j=n/k*k; j<n; j++) {
printf("%05d %d",nds[j].adr,nds[j].data);
if(j<n-1)printf(" %05d\n",nds[j+1].adr);
else printf(" -1\n");
}
}
}
}
return 0;
}
最新文章
- ASP.NET MVC 在控制器中获取某个视图动态的HTML代码
- 2.5---链表来进行加法,链式A+B(CC150)
- 关闭Ubuntu 12.04的内部错误提示
- ArcGIS三大文件格式解析
- require.js学习笔记(内容属于转载总结)
- 《第一行代码--Android》阅读笔记之界面设计
- WPF.UIShell UIFramework之自定义窗口的深度技术 - 模态闪动(Blink)、窗口四边拖拽支持(WmNCHitTest)、自定义最大化位置和大小(WmGetMinMaxInfo)
- 学习Hadoop的资料
- 1319-n皇后问题
- 网站开发常用jQuery插件总结(13)定位插件scrollto
- 解决embed标签显示在div上层【转藏】
- 符合搜索引擎SEO规则的HTML代码
- Docker终极指南:为什么Docker能做这么多事
- java大牛list
- 跨平台移动框架iMAG开发入门
- 使用Entify Framework 6.x的事务操作
- Oracle数据库中插入日期型数据(to_date的用法)(转载)
- Url校验正则
- Html和Css学习笔记-css基础知识
- confluence6.3.1升级最新版本(6.15.1)
热门文章
- 四十七、在SAP中,把功能区块整合成一个函数,通过调用函数的办法使代码简洁明了
- echarts 柱状图的选中模式实现-被选中变色和再次选中为取消变色
- Docker 容器shell
- 一、VIP课程:互联网工程专题 05-快速掌握Jenkins原理与核心功能
- Mapper method &#39;com.xxxx.other.dao.MyDao.getNo attempted to return null from a method with a primitive return type (int)
- HDU 5464:Clarke and problem
- POJ 1068:Parencodings
- C++基础--函数模板
- springboot + shiro+登录 微信登录 次数验证资料
- cf 444C.