传送门

02-线性结构3 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 (≤10​^5​​ ) 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 <iostream>
#include <cstdlib>
#include <cstdio>
#define MAX 100000

using namespace std;

typedef struct _node {
    int num;
    int next;
} Node;

Node a[MAX];
Node* reverse(Node *p, int k);

int main(int argc, char const * argv[])
{
    int head, n, k;
    cin >> head >> n >> k;
    int add;
    for ( int i=0; i<n; i++ ) {
        cin >> add;
        cin >> a[add].num >> a[add].next;
    }
    Node nodep;
    nodep.next = head;
    head = reverse(&nodep,k)->next;
    int flag = 1;
    do {
        printf("%05d %d ", head, a[head].num);
        if ( a[head].next == -1 ) {
            printf("-1");
            flag = 0;
        }
        else printf("%05d\n", a[head].next);
        head = a[head].next;
    } while ( flag );
    return 0;
}

Node* reverse(Node *p, int k)
{
    int now, old, temp;
    now = p->next;
    old = a[now].next;
    if ( old == -1 ) return p;
    temp= a[old].next;
    if ( temp== -1 ) {
        if ( k==2 ) {
            a[old].next = now;
            a[now].next = -1;
            p->next = old;
            return p;
        }
        else return p;
    }
    bool f = 0;
    for ( int cnt=1; cnt<k; cnt++ ) {
        if ( cnt==k-1 && a[old].next==-1 ) f=1;
        a[old].next = now;
        now = old;
        old = temp;
        temp= a[temp].next;
    }
    Node rep = {0, p->next};
    if ( f ) a[p->next].next = -1;
    else a[p->next].next = old;
    
    p->next = now;
    
    if ( f ) return p;
    
    int cnt = 0;
    temp = old;
    
    while ( a[old].next!=-1 ) {
        old = a[old].next;
        cnt++;
        if ( cnt==k-1 ) break;
    }
    if ( cnt==k-1 ) {
        //p.next = temp;
        reverse(&a[rep.next], k);
    }
    return p;
}