学步园

【来源】

1025. 反转链表（25）

【分析】

题目给出一系列链表的节点，要求将链表中每K个节点翻转。最后不到K个元素不反转。

和本题类似的题目有：Advanced Level 中的 1052. Linked List Sorting (25)，处理的思路是一样的。

对这种地址空间较小的题目，通用的做法是开一个大一点的Vector，然后把Vector的index映射为节点的地址。这样处理起来速度较快。

另外，处理的过程中无需考虑节点Next的值的正确性。处理完毕后从头遍历链表节点修改Next指针即可。

步骤大致如下：

1. 从头节点开始，先找出整条链表，用Vector按顺序存放（注意有的节点可能不包含在链表中的情况）；
2. 从头开始每K个节点将这些节点倒序输入到新的Vector中；
3. 如果整条链表节点个数不是K的整数倍，需要把剩余的节点按原来的顺序输入到新的Vector；
4. 修改节点的Next指针：遍历节点，把当前节点的Next指针值设为下个节点的Address；
5. 输出。

需要注意的是链表头地址为-1的情况，另外不要忘了修改最后一个节点的Next指针为-1。

【代码】

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

struct Node{
  int addr;
  int value;
  int next;
};
int main()
{
  int FirstAddr, N, K;
  scanf("%d%d%d", &FirstAddr, &N, &K);


  vector<Node> nodes(100000);
  for(int i = 0; i < N; ++i){
    Node node;
    scanf("%d%d%d", &node.addr, &node.value, &node.next);
    nodes[node.addr] = node;
  }

  if(FirstAddr == -1){
    printf("-1\n");
  }
  else{
    vector<Node> aftersort;
    int NextAddr = FirstAddr;
    while(NextAddr != -1){
      aftersort.push_back(nodes[NextAddr]);
      NextAddr = nodes[NextAddr].next;
    }

    vector<Node> final;
    int lastindex = K-1;
    while(lastindex < aftersort.size()){
      for(int i = lastindex; i > lastindex-K; --i){
        final.push_back(aftersort[i]);
      }
      lastindex += K;
    }
    for(int i = lastindex-K+1; i < aftersort.size(); ++i){
      final.push_back(aftersort[i]);
    }
    for(int i = 0; i < final.size()-1; ++i){
      final[i].next = final[i+1].addr;
    }

    int i;
    for(i = 0; i < final.size()-1; ++i){
      printf("%05d %d %05d\n", final[i].addr, final[i].value, final[i].next);
    }
    printf("%05d %d %d\n", final[i].addr, final[i].value, -1);
  }

  system("pause");
  return 0;
}

【点评】

此题为2014.3.1 PAT 春季考试最后一题，考察链表的相关知识，稍难。不过只要思路正确，也是很快可以写出AC的代码的。