PTA（链表）2-7 h0321. 反转链表

2-7 h0321. 反转链表

分数 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 行，每行描述一个节点的信息，格式如下：

1
Address Data Next

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

输出格式:

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

输入样例:

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

输出样例:

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

逻辑

记忆

  • 记以下五个要点:
    • 先定义Pretail，判断是否满足K个，不满足就退出，再定义NewTail，Current，NextHead，这是找此次反转的头部和尾部，再就是反转该链表，用的是三指针法:curr,prev,next

1.PreTail

  • 初始是定义PreTail: 总是指向当前要逆转段的前一个结点（即上一段的尾结点或头结点 L）

2.检查段长

  • 在开始逆转一段之前，先从 PreTail->Next 开始向后检查 K 个结点是否存在。如果不存在 K 个结点，则这段不进行逆转，直接退出循环。

3.NewTail Current NextHead定位段的头部和尾部（把整体的找到先）:

  • NewTail: 逆转后新段的尾结点，即逆转前老段的头结点 PreTail->Next。
  • Current: 用于遍历 $K$ 个结点，并辅助逆转操作。
  • NextHead: 逆转后新段的头结点（即逆转前老段的第 $K$ 个结点）。

4.prev curr next K 个结点的原地逆转:

  • 三指针法

5.连接新的段:

  • prev 现在指向逆转后的新段的头结点 (即原段的第 K 个结点)

  • 将上一段的尾结点连接到逆转后的新段的头结点：PreTail（上一段的尾结点）的 Next 应该指向逆转后的新段的头结点 NextHead (prev)。

  • 更新 PreTail 指向新逆转段的尾结点，即 NewTail，以便开始下一段的逆转。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <iomanip>

using namespace std;


// 定义链表结点的结构体
struct Node {
    int addr; // 存储自身的地址
    int data; // 存储数据
    int next; // 存放指向结点的地址
} nodes[100000];

int main() {
    int head, N, K; // 定义头节点地址，总结点数量，反转的长度
    cin >> head >> N >> K;

    // 读取数据
    for (int i = 0; i < N; ++i) {
        int addr, data, next;
        cin >> addr >> data >> next;
        nodes[addr].addr = addr;
        nodes[addr].data = data;
        nodes[addr].next = next;
    }

    // 开始分段逆转
    int dummy = -1; // 虚拟头节点dummy，此题无头节点，可以简化代码
    int preTail = dummy; // 指向当前要逆转段的前一个结点,用于连接各个段
    int current = head; // 当前开始遍历的结点（这里先定义的current）
    while (1) {
        // 判断此次逆转的长度是否有K个
        int p = current; // 用于遍历
        int count = 0;
        while (p != -1 && count < K) {
            p = nodes[p].next;
            count++;
        }
        if (count < K) { // 说明链表遍历完了，计数器还没到达K，直接退出
            break;
        }
        // 逆转该段
        int newTail = current; // 反转后这段的尾节点（原首节点）
        int newHead = p;

        // 逆转K个结点的三指针法
        int curr = current;
        int prev = newHead;
        int next = NULL;
        for (int i = 0; i < K; i++) {
            next = nodes[curr].next; // 先保存下一个结点
            nodes[curr].next = prev;
            prev = curr;
            curr = next;
        }
        // 连接新的段
        // prev 现在指向逆转后的新段的头结点 (即原段的第 K 个结点)

        // 将上一段的尾结点连接到逆转后的新段的头结点

        // 这里要分情况考虑，因为这里没有头节点
        if (preTail == dummy) {
            head = prev; // 头指针指向新的第一个节点
        } else {
            nodes[preTail].next = prev;
        }
        current = curr; // 移动到下一段


        // 更新 PreTail 到新逆转段的尾结点
        // NewTail 是逆转后的尾结点
        preTail = newTail;
    }

    // 打印
    current = head;
    while (current != -1) {
        cout << setw(5) << setfill('0') << current << " "
             << nodes[current].data << " ";
        if (nodes[current].next == -1) {
            cout << -1 << endl;
        } else {
            cout << setw(5) << setfill('0') << nodes[current].next << endl;
        }
        current = nodes[current].next;
    }

}