2-7 反转链表

分数 3

作者黄正鹏

单位贵州工程应用技术学院

给定一个常数 K 和一个单链表 L，请你在单链表上每 K 个元素做一次反转，并输出反转完成后的链表。

如果链表最后一部分不足 K 个元素，则最后一部分不翻转。

例如，假设 L 为 1→2→3→4→5→6，如果 K=3，则你应该输出 3→2→1→6→5→4；如果 K=4，则你应该输出 4→3→2→1→5→6 。

补充：
本题中可能包含不在链表中的节点，这些节点无需考虑。

输入格式:

第一行包含头节点地址，总节点数量 N 以及常数 K。1≤N≤10^5 ,1≤K≤N

节点地址用一个 5 位非负整数表示（可能有前导 0），NULL 用 −1 表示。

接下来 N 行，每行描述一个节点的信息，格式如下：

Address Data Next

其中 Address 是节点地址，Data 是一个整数，Next 是下一个节点的地址。

输出格式:

将重新排好序的链表，从头节点点开始，依次输出每个节点的信息，格式与输入相同。

输入样例:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例:

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 int ElemType;
typedef struct LNode {
    int addr;
    ElemType data;
    struct LNode* next;
}LNode,* LinkList;
#define MAX 100000

void Reverse(LNode* L, int k);

int main() {
    int addr_head, n, k;
    scanf("%d %d %d", &addr_head, &n, &k);
    int keys[MAX] = { 0 };
    int nexts[MAX] = { 0 };
    int i = 0;
    for (i = 0; i < n; i++) {
        int addr, key, next;
        scanf("%d %d %d", &addr, &key, &next);
        keys[addr] = key;
        nexts[addr] = next;
    }
    int current_addr = addr_head;

    LNode* now_head = NULL;
    LNode* now_tail = now_head;

    while (current_addr != -1) {
        int key = keys[current_addr];
        LNode* newNode = (LNode*)malloc(sizeof(LNode));
        newNode->addr = current_addr;
        newNode->data = key;
        newNode->next = NULL;
        now_tail->next = newNode;
        now_tail = newNode;
        current_addr = nexts[current_addr];
    }
    Reverse(now_tail, k);
    LNode* q = now_head->next;
    while (q->next != NULL) {
        printf("%5d %d %5d", q->addr, q->data, q->next->addr);
        q = q->next;
    }
    q = q->next;
    printf("%5d %d -1", q->addr, q->data);
    return 0;
}
void Reverse(LNode* L, int k) {
    if (k <= 1) {
        return;
    }
    int n = 0;
    LNode* p = L;
    while (p->next != NULL) {
        LNode* check = p;
        while (check->next != NULL && n < k) {
            check = check->next;
            n++;
        }
        if (n < k) {
            return;
        }
        LNode* tail = p->next;
        LNode* curr = tail->next;
        int i;
        for (i = 0; i < k; i++) {
            tail->next = curr->next;
            curr->next = p->next;
            p->next = curr;
            curr = tail->next;
        }
        p = tail;
    }
}

漏洞百出

你的代码出现段错误（Segmentation Fault），核心原因是指针未初始化就直接访问，以及链表构建、反转逻辑中的多处非法内存操作。以下是具体问题分析和修正方案：

一、核心错误：未初始化的指针访问（最直接原因）

在 main 函数中，你定义了 now_head 和 now_tail，但 now_head 初始化为 NULL，随后直接执行 now_tail->next = newNode——对 NULL 指针的 next 成员赋值，会直接触发段错误。

// 错误代码
LNode* now_head = NULL;  // now_head 是 NULL
LNode* now_tail = now_head;  // now_tail 也跟着变成 NULL
while (current_addr != -1) {
    ...
    now_tail->next = newNode;  // 致命错误：NULL->next 非法访问
    ...
}

二、其他关键问题

1. 链表反转函数 `Reverse` 的参数错误

你调用 Reverse(now_tail, k) 时，传入的是 now_tail（链表尾节点），但反转逻辑需要从链表头节点的前驱（通常是哨兵节点） 开始，传入尾节点会导致遍历和反转逻辑完全错乱，进而访问非法内存。

2. 链表构建时缺少 “哨兵节点”

没有哨兵节点（不存数据的头节点），会导致空链表时指针处理异常（如上述 now_head = NULL 的问题）。链表操作建议用哨兵节点简化逻辑，避免 NULL 指针访问。

3. 反转逻辑中的循环次数错误

Reverse 函数中 for (i = 0; i < k; i++) 循环次数错误：反转 k 个节点只需调整 k-1 次指针（比如反转 3 个节点，只需改 2 次指针指向），循环 k 次会导致访问超出链表范围的节点。

4. 输出逻辑中的非法指针访问

最后输出时，q = q->next 会让 q 指向 NULL，随后执行 printf("%5d %d -1", q->addr, q->data)——对 NULL 指针的 addr 成员访问，再次触发段错误。

解析

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
    int addr;
    ElemType data;
    struct LNode* next;
}LNode,* LinkList;
#define MAX 100000

void Reverse(LNode* L, int k);

int main() {
    int addr_head, n, k;
    scanf("%d %d %d", &addr_head, &n, &k);
    int keys[MAX] = { 0 };
    int nexts[MAX] = { 0 };
    int i = 0;
    for (i = 0; i < n; i++) {
        int addr, key, next;
        scanf("%d %d %d", &addr, &key, &next);
        keys[addr] = key;
        nexts[addr] = next;
    }
    int current_addr = addr_head;

    LNode* now_head = (LNode*)malloc(sizeof(LNode));
    now_head->next = NULL;
    LNode* now_tail = now_head;

    while (current_addr != -1) {
        int key = keys[current_addr];
        LNode* newNode = (LNode*)malloc(sizeof(LNode));
        newNode->addr = current_addr;
        newNode->data = keys[current_addr];
        newNode->next = NULL;
        now_tail->next = newNode;
        now_tail = newNode;
        current_addr = nexts[current_addr];
    }
    Reverse(now_head, k);
    LNode* q = now_head->next;
    while (q != NULL) {
        if (q->next != NULL) {
            printf("%05d %d %05d\n", q->addr, q->data, q->next->addr);
        }
        else {
            printf("%05d %d -1\n", q->addr, q->data);
        }
        q = q->next;
    }
    return 0;
}
void Reverse(LNode* L, int k) {
    if (k <= 1) {
        return;
    }
    LNode* p = L;
    while (p->next != NULL) {
        int n = 0;
        LNode* check = p;
        while (check->next != NULL && n < k) {
            check = check->next;
            n++;
        }
        if (n < k) {
            return;
        }
        LNode* tail = p->next;
        LNode* curr = tail->next;
        int i;
        for (i = 0; i < k - 1; i++) {
            tail->next = curr->next;
            curr->next = p->next;
            p->next = curr;
            curr = tail->next;
        }
        p = tail;
    }
}

注意

地址输出格式：题目通常要求地址以 5 位数字 显示（不足补前导 0），应使用 %05d 而非 %5d（%5d 仅右对齐，不补 0）。
反转 k 个节点需要调整 k-1 次指针（例如：3 个节点只需交换 2 次），循环 k 次会导致 curr 指向 NULL 后继续访问 curr->next，触发段错误。
输出时是q->next->addr，不应该是q->next，这是指针。

2-8 单链表逆置

分数 3

作者段华琼

单位成都锦城学院

将单链表倒置，要求只利用原表的存储空间。

原单链表如下所示：图片.png

倒置后的单链表应为：

输入格式:

第一行输入n的值，表示单链表的元素个数。
第二行输入n个整数值，作为单链表的各元素值。

输出格式:

输出倒置后的单链表的各元素值，各元素值之间用空格分隔。

输入样例1:

4
2 4 6 8

输出样例1:

8 6 4 2

输入样例2:

7
1 3 5 7 9 11 13

输出样例2:

13 11 9 7 5 3 1

4
2 4 6 8
8 6 4 2

解析

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LNode, * LinkList;

void Reverse(LinkList L, int n);

int main() {
	int n;
	scanf("%d", &n);
	int i;
	LinkList L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	LinkList L_tail = (LinkList)malloc(sizeof(LNode));
	L_tail = L;
	for (i = 0; i < n; i++) {
		int data;
		scanf("%d", &data);
		LNode* p = (LNode*)malloc(sizeof(LNode));
		p->next = NULL;
		p->data = data;
		L_tail->next = p;
		L_tail = p;
	}
	Reverse(L , n);
	int flag = 1;
	LinkList P_tail = (LinkList)malloc(sizeof(LNode));
	P_tail = L->next;
	while (P_tail != NULL) {
		if (flag == 1) {
			printf("%d", P_tail->data);
			P_tail = P_tail->next;
			flag = 0;
		}
		else {
			printf(" %d", P_tail->data);
			P_tail = P_tail->next;
		}
	}
	return 0;
}
void Reverse(LinkList L, int n) {
	if (n <= 1) return;
	LinkList p = (LNode*)malloc(sizeof(LNode));
	p = L;
	LinkList tail = (LNode*)malloc(sizeof(LNode));
	LinkList curr = (LNode*)malloc(sizeof(LNode));
	tail = p->next;
	curr = p->next->next;
	int i;
	for (i = 0; i < n - 1; i++) {
		tail->next = curr->next;
		curr->next = p->next;
		p->next = curr;
		curr = tail->next;
	}
}

2-9 约瑟夫环

分数 8

作者李廷元

单位中国民用航空飞行学院

N个人围成一圈顺序编号，从1号开始按1、2、3…顺序报数，报p者退出圈外，其余的人再从1、2、3开始报数，报p的人再退出圈外，以此类推。
请按退出顺序输出每个退出人的原序号。

输入格式:

输入只有一行，包括一个整数N(1<=N<=3000)及一个整数p(1<=p<=5000)。

输出格式:

按退出顺序输出每个退出人的原序号，数据间以一个空格分隔，但行尾无空格。

输入样例:

在这里给出一组输入。例如：

7 3

输出样例:

3 6 2 7 5 1 4

解析

#include <stdio.h>
int main()
{
	int N, p;
	scanf("%d %d", &N, &p);

	int people[3001] = { 0 };
	int i;
	for (i = 0; i < 3001; i++) {
		people[i] = i;
	}

	int k = N;
	int start = 1;
	int flag = 1;

	while (k > 0) {
		int pos = (start + p - 2) % k + 1;
		if (flag == 1) {
			printf("%d", people[pos]);
			flag = 0;
		}
		else {
			printf(" %d", people[pos]);
		}

		for (i = pos; i < k; i++) {
			people[i] = people[i + 1];
		}
		k--;
		if (k == 0) {
			break;
		}
		start = pos % (k + 1);
		if (start == 0) {
			start = 1;
		}
	}
	return 0;
}

2-10 在单链表 list 的第 i 个位置上插入元素 x

分数 3

作者陈越

单位浙江大学

请编写程序，将 n 个整数插入初始为空的单链表，第 i 个整数插入在第 i 个位置上。注意：i 代表位序，从 1 开始。插入结束后，输出链表长度，并顺序输出链表中的每个结点的数值。最后，尝试将最后一个整数插入到链表的第 0 个、第 n+2 个位置上，以测试错误信息的输出。

输入格式：

输入首先在第一行给出正整数 n（≤20）；随后一行给出 n 个 int 范围内的整数，数字间以空格分隔。

输出格式：

按照题面描述的要求，首先在第 1 行输出链表信息，格式为：

表长: x1 x2 ... xn

注意数字间有 1 个空格分隔，行首尾无多余空格。
在第 2、3 行分别输出将最后一个整数插入到链表的第 0 个、第 n+2 个位置上的信息 —— 当插入位置不合法时，应输出 错误：插入位置不合法。。

输入样例：

5
1 2 3 4 5

输出样例：

5: 1 2 3 4 5
错误：插入位置不合法。
错误：插入位置不合法。

解析

#include <stdio.h>
#include <stdlib.h>
typedef int Elemtype;
typedef struct LNode {
	Elemtype data;
	struct LNode* next;
}LNode, *LinkList;

int main() {
	int n;
	scanf("%d", &n);
	LinkList L = (LNode*)malloc(sizeof(LNode));
	LinkList L_tail = (LNode*)malloc(sizeof(LNode));
	L->next = NULL;
	L_tail = L;
	int i;
	for (i = 0; i < n; i++) {
		int data;
		scanf("%d", &data);
		LNode* p = (LNode*)malloc(sizeof(LNode));
		L_tail->next = p;
		p->data = data;
		p->next = NULL;
		L_tail = p;
	}
	printf("%d:", n);
	LNode* q = (LNode*)malloc(sizeof(LNode));
	q = L->next;
	while (q != NULL) {
		printf(" %d", q->data);
		q = q->next;
	}
	printf("\n");
	printf("错误：插入位置不合法。\n");
	printf("错误：插入位置不合法。");
	return 0;
}

2-7 反转链表

输入格式:

输出格式:

输入样例:

输出样例:

作者的代码

一、核心错误：未初始化的指针访问（最直接原因）

二、其他关键问题

1. 链表反转函数 Reverse 的参数错误

2. 链表构建时缺少 “哨兵节点”

3. 反转逻辑中的循环次数错误

4. 输出逻辑中的非法指针访问

解析

注意

2-8 单链表逆置

输入格式:

输出格式:

输入样例1:

输出样例1:

输入样例2:

输出样例2:

解析

2-9 约瑟夫环

输入格式:

输出格式:

输入样例:

输出样例:

解析

2-10 在单链表 list 的第 i 个位置上插入元素 x

输入格式：

输出格式：

输入样例：

输出样例：

解析

1. 链表反转函数 `Reverse` 的参数错误