1074. Reversing Linked List (25)-蒲公英云

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

题目大意：

代码：

#include<stdio.h>
#include<stack>
#include<vector>
using namespace std;
struct node
{
    int id;
    int data;
    int next;
}List[100001];
vector<struct node> v;
int main()
{
    int i,j,n,m,k,t,first,id,data,next,index,second,num=0;
    scanf("%d %d %d",&first,&n,&k);
    for(i=0;i<n;i++)
    {
        scanf("%d %d %d",&id,&data,&next);
        List[id].id=id;
        List[id].data=data;
        List[id].next=next;
    }
    stack<struct node> s;
    t=0;
    //printf("\n");
    second=first;
    while(second!=-1)
    {
        second=List[second].next;
        num++;
    }
    while(first!=-1)
    {
        if(num%k!=0&&(num-t<=num%k))
        {
        v.push_back(List[first]);
        }
        else
        {
        s.push(List[first]);
        t++;
        if(t%k==0)
        {
            while(!s.empty())
            {
                struct node tmp=s.top();
                s.pop();
                v.push_back(tmp);
            }
        }
        }
        first=List[first].next;
    }
    for(i=0;i<v.size();i++)
    {
        if(i==v.size()-1)
        {
            printf("%05d %d -1\n",v[i].id,v[i].data);
        }
        else
        {
            printf("%05d %d %05d\n",v[i].id,v[i].data,v[i+1].id);
        }
    }
    return 0;
}