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:
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 <stdlib.h>

//定义数据结构
typedef struct Node *PolyNode;
struct Node {
int data;
int next;
PolyNode Next;
};
void append(int addr, int data, int next, PolyNode *pRear) {
PolyNode P;
P = (PolyNode)malloc(sizeof(struct Node));
P->data = data;
P->next = next;
P->Next = NULL;
(*pRear)->Next = P;
*pRear = P;
}//链表尾的插入操作，测试没问题

PolyNode P;
P = (PolyNode)malloc(sizeof(struct Node));
P->data = data;
P->next = next;
}//链表头的插入操作

//对输入数据按照地址前后排序，测试后没问题
PolyNode sortList(PolyNode P, int firstAddr, int N) {
PolyNode Pp, Rear, t;
PolyNode p;
p = P;
Pp = (PolyNode)malloc(sizeof(struct Node));
Pp->Next = NULL;
Rear = Pp;
int end;
while (first != -1) {
while (p) {
Rear->Next = p;
first = p->next;
break;
}
else
p = p->Next;
}
p = P;
}
Rear->Next = NULL;
t = Pp; Pp = Pp->Next; free(t);
return Pp;
}
void PrintPoly(PolyNode P) {
while (P) {
if(P->next == -1)
printf("%05d %d %d\n", P->addr, P->data, P->next);
else
printf("%05d %d %05d\n", P->addr, P->data, P->next);
P = P->Next;
}
}//结果的打印，测试无问题

//对链表按照要求逆转操作，可能有问题？
PolyNode Function(PolyNode P, int N, int K) {
if (K > N) return NULL;
PolyNode temp, tt;
temp = P;
PolyNode tP, rear, t;
tP = (PolyNode)malloc(sizeof(struct Node));//tP是一个空de头结点
tP->Next = NULL;
rear = tP;
tt = rear;
int team = N / K;
int i;
PolyNode ttemp;
while (team) {
if (!tP) {
temp = temp->Next;
tt = rear;
}
for (i = 0; i < K-1; i++) {
ttemp = tt;
temp = temp->Next;
tt = ttemp;
}
team = team - 1;
tt = rear;
}
if (N%K != 0) {
rear->Next = temp->Next;
}
t = tP; tP = tP->Next; free(t);
return tP;
}

int main() {
PolyNode P, Rear, t;
PolyNode result;
P = (PolyNode)malloc(sizeof(struct Node));
P->Next = NULL;
Rear = P;
int first, N, K;
scanf_s("%d %d %d", &first, &N, &K);
int i = N;
while (i) {
scanf_s("%d %d %d", &addr, &data, &next);
i = i - 1;
}
t = P; P = P->Next; free(t);
result = sortList(P, first, N);

PrintPoly(Function(result, N, K));
getch();
return 0;
}

|
4月前
|

37 0
|
C++
【PAT甲级 - C++题解】1133 Splitting A Linked List
【PAT甲级 - C++题解】1133 Splitting A Linked List
69 0
|
C++
【PAT甲级 - C++题解】1074 Reversing Linked List
【PAT甲级 - C++题解】1074 Reversing Linked List
66 0
|

【PAT甲级 - C++题解】1052 Linked List Sorting
【PAT甲级 - C++题解】1052 Linked List Sorting
75 0
|

LeetCode 141. 环形链表 Linked List Cycle
LeetCode 141. 环形链表 Linked List Cycle
98 0
LeetCode 237. 删除链表中的节点 Delete Node in a Linked List
LeetCode 237. 删除链表中的节点 Delete Node in a Linked List
83 0

68 0
|

103 0
|
Python
LeetCode 234. 回文链表 Palindrome Linked List
LeetCode 234. 回文链表 Palindrome Linked List
66 0
LeetCode 206. 反转链表 Reverse Linked List
LeetCode 206. 反转链表 Reverse Linked List
64 0