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$ (\le 10^5≤10​5​​) which is the total number of nodes, and a positive $K$ ($\le 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 Nextis 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 "stdio.h" using namespace std; struct Node { int data; int next; }; Node pointer[100001]; int step = 0; int rel; int first, last; // 按规定反转链表 int reverse(int k, int start) { step++; int cnt = 1; int now, old, temp; now = start; //指向反转后链表的头节点 old = pointer[now].next; //指向还未反转的链表的头结点 while (cnt < k) { temp = pointer[old].next; // 指向还未反转的链表的头结点的下一个节点 pointer[old].next = now; now = old; old = temp; temp = pointer[temp].next; cnt++; } if (step == 1) { /* 第一次反转 */ rel = now; /* 记下反转链表新的头节点 */ } pointer[start].next = old; /* 将其先指向第n*k+1个数 再在下一次逆序的时候 修改这个值*/ if (step != 1) { pointer[last].next = now; /* 修改值~~ */ } last = start; /*更新此刻已完成逆序的链表的最后一个元素last*/ return old; } int main() { int addr, data, nex; int start, n, k; int len = 0; cin >> start >> n >> k; while (n--) { //建立链表 cin >> addr >> data >> nex; pointer[addr].data = data; pointer[addr].next = nex; } int cnt = start; while (cnt != -1) { /* 因为老师说会有不在链表中的多余节点 计算链表中的真正节点 */ len++; cnt = pointer[cnt].next; } int s; s = len / k; rel = start; int now = start; for (int i = 0; i < s; i++) { //反转链表 now = reverse(k, now); } while (rel != -1) { if (pointer[rel].next != -1) printf("d %d d\n", rel, pointer[rel].data, pointer[rel].next); else printf("d %d %d\n", rel, pointer[rel].data, pointer[rel].next); rel = pointer[rel].next; } }