PAT甲級1074

1074. Reversing Linked List (25)

時間限制

400 ms

記憶體限制

65536 kB

代碼長度限制

16000 B

判題程式

Standard

作者

CHEN, Yue

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

#include<stdio.h>
#include<algorithm>
#include<stack>
using namespace std;
struct Node
{
  int data;
  int next;
}node[100000];//定義靜态連結清單節點
struct record
{
  int address;
  //int next;
};//用于反轉連結清單
int main()
{
  for (int i = 0; i < 100000; i++)
  {
    node[i].data = 0;
    node[i].next = -1;
  }//初始化
  int head, N, K;
  scanf("%d%d%d", &head, &N, &K);
  int address, data, next;
  while (N--)
  {
    scanf("%d%d%d", &address, &data, &next);
    node[address].data = data;
    node[address].next = next;//連結各節點
  }
  int count = 0;//計數器
  int addressNow = head;
  int pre;
  stack<record> sta;//用于暫存要被逆轉連接配接的節點
  record temprecord;//儲存節點位址,本來以為要儲存下一個節點的位址，其實根本不需要，也不想改了就這樣吧
  int oldLast;//上一次逆轉後指向最後一個節點的指針
  while (addressNow!= -1)
  {
    temprecord.address = addressNow;
    //temprecord.next = node[addressNow].next;
    sta.push(temprecord);
    pre = addressNow;
    addressNow = node[addressNow].next;
    count++;
    if (count%K == 0)
    {  
        if (count == K)
          head = pre;//第一個開始反轉的節點成為頭了
        if (!sta.empty())
        {
          sta.pop();
        }
        if (pre != head)
        {
          node[oldLast].next = pre;
        }//如果不是第一個那麼需要将上一次反轉後的最後一個節點的下個位址做修改
        //将樣例中的K由4改為2你就知道為什麼了
      for (int i = 0; i < K-1; i++)
      {
        node[pre].next = sta.top().address;//逆轉連結清單
        pre = sta.top().address;
        if (!sta.empty())
        {
          sta.pop();
        }
      }
      node[pre].next = addressNow;//修改反轉節點的最後一個節點的下一個位址，
      //若後面不會再反轉，那麼就是目前掃描的節點的位址，注意我是先計數後又把指針
      //往後移一位了
      oldLast = pre;//儲存反轉節點的最後一個節點的位址
    }
  }
  addressNow = head;
  while (addressNow!= -1)
  {
    if(node[addressNow].next!=-1)
    printf("%05d %d %05d\n", addressNow, node[addressNow].data, node[addressNow].next);
    else
      printf("%05d %d %d\n", addressNow, node[addressNow].data, node[addressNow].next);
    addressNow = node[addressNow].next;
  }
  return 0;
}
/*注意把每次反轉後的節點的下一個位址修改正确，
比如說1 2 3 4 5 6，反轉個數K為2時，應該是
2 1 4 3 6 5，這時要記得把1跟4連上，3跟6
連上。*/