1025. 反转链表 (25)

时间限制

300 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

CHEN, Yue

给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为1→2→3→4→5→6，K为3，则输出应该为3→2→1→6→5→4；如果K为4，则输出应该为4→3→2→1→5→6，即最后不到K个元素不反转。

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 10⁵)、以及正整数K(<=N)，即要求反转的子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。

接下来有N行，每行格式为：

Address Data Next

其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。

输出格式：

对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 6 400000 4 9999900100 1 1230968237 6 -133218 3 0000099999 5 6823712309 2 33218

输出样例：

00000 4 3321833218 3 1230912309 2 0010000100 1 9999999999 5 6823768237 6 -1 个人感觉这道题在乙级算比较难的，主要是考虑的细节多。首先节点乱序输入，我的想法是通过map预处理，最终通过vector来存储。说实话现在让我写C简直是煎熬，写oj还是C++大法好。 这道题比较坑的一点是有一个测试点包含“远离人群”的节点，就是一个无效节点然后一直卡在那里，百度别人解法，一开始还不信，我是觉得这样不太好，说要考虑周全这种事，这个corner case有点隐秘，贴过了的代码，还有话想说。

1 #include 
      
        2 #include 
       
         3 #include
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
             8 9 using namespace std;10 11 struct xi {12 int a, b, c;13 xi(int a,int b,int c):a(a),b(b),c(c){}14 };15 16 17 int main(void)18 {19 map
             
               > l;20 vector
              
                v;21 int root, n, m;22 cin >> root >> n >> m;23 //int next = root;24 for (int i = 0;i < n;i++)25 {26 int add, val, next;27 cin >> add >> val >> next;28 if (add == root)29 {30 root = next;31 v.push_back(xi(add, val, next));32 }33 else l[add] = make_pair(val, next);34 }35 36 for (root = v[v.size() - 1].c;root != -1;root = l[root].second)37 {38 auto &p = l[root];39 v.push_back(xi(root, p.first, p.second));40 }41 n = v.size();//这里记得更新42 int i;43 for (i = m - 1;i < n;i+=m)44 {45 for (int j = 0;j < m;j++)46 {47 if (i + 1 == m&&0 == j)printf("%05d %d ", v[i].a, v[i].b);48 else {49 printf("%05d\n%05d %d ", v[i - j].a, v[i - j].a, v[i - j].b);50 }51 }52 }53 if (i + 1 - m != n)54 {55 i -= m - 1;56 for(;i

而且我个人就我个人的写法，如果有效节点小于n，那应该在vector越界访问了，然而报错显示答案错误？？？预处理后把v.size()赋给n就过了。再刷几道开始刷甲级了。现在每天也不敢 多刷，感觉不看书只刷oj很虚

转载于:https://www.cnblogs.com/schsb/p/8764664.html

你可能感兴趣的文章